• ํŒจ์ŠคํŠธ์บ ํผ์Šค ์ฑŒ๋ฆฐ์ง€ 1์ผ์ฐจ

    2021. 11. 1.

    by. JuneBee

    728x90
    ๋ฐ˜์‘ํ˜•

    ๋‚ ์งœ : 2021 ๋…„ 11์›” 1 ์ผ
    ์‹œ์ฒญ ๊ฐ•์˜ : ๋™์  ๊ณ„ํš๋ฒ•๊ณผ ๋ถ„ํ•  ์ •๋ณต, ๋ณ‘ํ•ฉ ์ •๋ ฌ (1), ๋ณ‘ํ•ฉ ์ •๋ ฌ (2)

    ๋™์  ๊ณ„ํš๋ฒ•๊ณผ ๋ถ„ํ•  ์ •๋ณต

    ๋™์  ๊ณ„ํš๋ฒ• (DP)

    1. ์ž…๋ ฅ ํฌ๊ธฐ๊ฐ€ ์ž‘์€ ๋ถ€๋ถ„์„ ํ•ด๊ฒฐํ•˜์—ฌ ํฐ ๋ฌธ์ œ ํ•ด๊ฒฐ์— ์ ์šฉํ•˜๋Š” ๋ฐฉ์‹
    2. ์ƒํ–ฅ์‹ (sub problems -> main problem )
    3. Memoization ๊ธฐ๋ฒ• ์‚ฌ์šฉ

    Memoization ์ด๋ž€, ์ด์ „ ๊ฐ’์„ ๊ธฐ์–ตํ•˜์—ฌ runtime์ด๋‚˜ memory ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•ด์ค€๋‹ค. -> ๋ฐฑ์ค€ ๋ฌธ์ œ์—์„œ ์œ ์šฉํ•˜๊ฒŒ ์‚ฌ์šฉ

    ๋ถ„ํ•  ์ •๋ณต (Divide and Conquer)

    1. ๋ฌธ์ œ๋ฅผ ๋‚˜๋ˆŒ ์ˆ˜ ์—†์„๋•Œ๊นŒ์ง€ ๋‚˜๋ˆ„์–ด ํ‘ผ ํ›„, ํ•ด๋‹ต์„ ํ•ฉ์นœ๋‹ค
    2. ํ•˜ํ–ฅ์‹ (main problem -> sub problems)

    DP vs ๋ถ„ํ•  ์ •๋ณต ์š”์•ฝ

      DP ๋ถ„ํ• ์ •๋ณต
    common ๋ฌธ์ œ๋ฅผ ์ชผ๊ฐœ์–ด (๋‚˜๋ˆ„์–ด) ํ’€์ดํ•œ๋‹ค
    Differences sub-problems: ์ค‘๋ณต๋˜๋ฉฐ, ์ด sub-problems๋กœ ์ƒ์œ„ ๋ฌธ์ œ๋ฅผ ํ’€ ์ˆ˜ ์žˆ๋‹ค. ๋ถ€๋ถ„ ๋ฌธ์ œ๋“ค์€ ์ค‘๋ณต๋˜์ง€ ์•Š๋Š”๋‹ค
    Memoization์„ ํ†ตํ•ด ์ค‘๋ณต๋˜๋Š” ์—ฐ์‚ฐ ๊ธฐํ”ผ ๋”ฐ๋ผ์„œ, Memo๋ฅผ ํ•  ํ•„์š”๊ฐ€ ์—†๋‹ค

    DP Example

    DP ์˜ ๊ฐ€์žฅ ๋Œ€ํ‘œ์ ์ธ ์˜ˆ์‹œ๋กœ๋Š” ํŒฉํ† ๋ฆฌ์–ผ, ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด, ๋„ต์„น ๋“ฑ์ด ์žˆ๋‹ค.
    ์ด์ค‘ ๋น„๊ต์  ๊ฐ„๋‹จํ•œ ํŒฉํ† ๋ฆฌ์–ผ๋กœ ์˜ˆ์‹œ๋ฅผ ๋“ค๊ณ ์ž ํ•œ๋‹ค.

     

    Previously,
    ์žฌ๊ท€๋ฅผ ํ†ตํ•ด์„œ ํŒฉํ† ๋ฆฌ์–ผ์„ ํ‘ธ๋Š” ๋ฐฉ์‹์ด ๋ณดํŽธ์ ์ด๋‹ค
    ์žฌ๊ท€๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ํŒฉํ† ๋ฆฌ์–ผ์„ ์—ฐ์‚ฐํ•˜๊ฒŒ ๋˜๋ฉด, ๋งค๋ฒˆ ๊ฐ’์„ ๊ณ„์‚ฐํ•ด์•ผ ํ•ด์„œ ์ค‘๋ณต๋˜๋Š” ๊ณ„์‚ฐ๋“ค์ด ๋งŽ์•„์ง„๋‹ค.
        public static int recursive(int number) {
            if(number == 1) return 1;
            return recursive(number-1)*number;
        }

    With DP,
    DP๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ํ’€๋ฉด, ์ด์ „ ๊ฐ’๋“ค์ด ์ €์žฅ๋˜๊ธฐ ๋•Œ๋ฌธ์— ์ค‘๋ณต ์—ฐ์‚ฐ์ด ์—†์–ด์ง„๋‹ค

        /**
         * Dynamic Programming 
         * Memoization์„ ์‚ฌ์šฉํ•œ๋‹ค
         * ํ•œ๋ฒˆ ๊ณ„์‚ฐํ•œ ๊ฐ’์€, D[current_index]์— ์ €์žฅ๋˜๊ธฐ ๋•Œ๋ฌธ์— ๋‹ค์‹œ ๊ณ„์‚ฐ๋  ํ•„์š” ์—†๋‹ค
         * */
        public static int dynamic(int number) {
            //Step 1 : D[] ๋ฐฐ์—ด ์ƒ์„ฑ
            Integer[] D = new Integer[number+1];
            //Step 2 : Initialize init_values
            D[0] = 0;
            D[1] = 1;
            //Step 3 : for loop๋ฅผ ๋Œ๋ฉด์„œ ๊ฐ ๋ฐฐ์—ด์— ๊ฐ’์„ ์—…๋ฐ์ดํŠธ (ํ˜„์žฌ๊ฐ’์€ ์ด์ „๊ฐ’์„ ์ฐธ๊ณ ํ•˜์—ฌ ์—…๋ฐ์ดํŠธํ•œ๋‹ค)
            for(int i = 2 ; i<= number ; i ++) {
                D[i] = D[i-1] * i;//์ด์ „๊ฐ’ * ํ˜„์žฌ๊ฐ’
            }
            return D[number]; //๋งจ ๋งˆ์ง€๋ง‰ ๋ฐฐ์—ด์˜ ์›์†Œ๊ฐ€ ์ตœ์ข…๊ฐ’์ž„
        }

    Example - ๋ถ„ํ•  ์ •๋ณต

    ๋ณ‘ํ•ฉ ์ •๋ ฌ์ด ๊ฐ€์žฅ ๋Œ€ํ‘œ์ ์ธ ๋ถ„ํ•  ์ •๋ณต์˜ ์˜ˆ๋กœ ๋“ค ์ˆ˜ ์žˆ๋‹ค.

    ๋ณ‘ํ•ฉ ์ •๋ ฌ (Merge Sort)

    ๋ณ‘ํ•ฉ ์ •๋ ฌ์€ ์žฌ๊ท€ ์šฉ๋ฒ•์„ ์ด์šฉํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ,

    6 5 1 2 7 4 5

    ์œ„์™€ ๊ฐ™์€ ๋ฐฐ์—ด์ด ์žˆ์„ ๋•Œ ์ตœ์†Œ์˜ ๋‹จ์œ„๋กœ ๋‚˜๋ˆ„์–ด์งˆ ๋•Œ ๊นŒ์ง€ ๋ฐ˜์œผ๋กœ ๊ณ„์† ๋‚˜๋ˆ„๊ณ  (divide)

    ์žฌ์กฐ๋ฆฝ ๋  ๋•Œ ์ •๋ ฌ(sort)ํ•˜์—ฌ ํ•ฉ์น˜๋Š”(merge) ๋ฐฉ์‹์ด๋‹ค.

    Step 1: Divide

    mid = 7/2 = 3

    6 5 1 2
    7 4 5

    Step 2 : Divide

    mid = 4/2 = 2, 3/2 = 1

    6 5
    1 2
    7 4
    5

    Step 3: Divide (Completed)

    6
    5
    1
    2
    7
    4
    5

    Step 4 : Merge - index 0๊ณผ 0๋ผ๋ฆฌ ๋น„๊ต

    left array:

    5 6

    right array:

    1 2

    left array 2:

    4 7

    right array 2:

    5

    Step 5 : Merge - index 01 ~ 01 ๋ผ๋ฆฌ ๋น„๊ต

    Array 1๋ผ๋ฆฌ ๋น„๊ต

    index 0 vs 0 : 5 > 1

    1      

    index 0 vs 1 : 5 > 2

    1 2    

    left Array๋งŒ ๋‚จ์•˜๊ธฐ ๋•Œ๋ฌธ์— left Array๋ฅผ sorted array ๋’ค์— ๋ถ™ํžŒ๋‹ค

    1 2 5 6

    Array 2 ๋ผ๋ฆฌ ๋น„๊ต

    index 0 vs 0 : 4 < 5

    4    

    index 1 vs 0 : 7 > 5

    4 5  
    4 5 7

    Step 5 :

    Array 1 vs Array 2

    1 2 5 6
    4 5 7

    sorted array :

    1            

    1 2 5 6
    4 5 7

    sorted array :

    1 2          

    1 2 5 6
    4 5 7

    sorted array :

    1 2 4        

    1 2 5 6
    4 5 7

    sorted array :

    1 2 4 5      

    1 2 5 6
    4 5 7

    sorted array :

    1 2 4 5 5    

    1 2 5 6
    4 5 7

    sorted array :

    1 2 4 5 5 6  

    1 2 5 6
    4 5 7

    sorted array :

    1 2 4 5 5 6 7

    ์œ„์—์„œ MergeSort ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ดํŽด๋ณด์•˜๋‹ค.**

    ์ด์ œ, ์žฌ๊ท€๋ฅผ ํ†ตํ•ด Merge Sort๋ฅผ ๊ตฌํ˜„ํ•ด๋ณด๋ฉด,**

    import java.util.Arrays;
    
    /**
     * @author June Park
     * @date 11/01/2021
     * Merge Sort ๊ตฌํ˜„
     * ์žฌ๊ท€๋กœ ๊ตฌํ˜„
     * */
    public class MergeSort {
        static int N = 10;
        static int [] sorted = new int[N];
    
        public static void main(String[] args) {
            //Create an random array
            int[] given = new int [N];
            for(int i = 0 ; i < N ; i ++) {
                given[i] = (int) (Math.random()*100)+1;
            }
    
            split(given,0,N-1); //0~N-1 (์ด N๊ฐœ) ๊นŒ์ง€ ์ชผ๊ฐค ๊ฒƒ
            for(int i : given) {System.out.print(i+ " ");}
        }
    
        /**
         * Split Method 
         * Splits arrays to half (start ~ mid, mid ~ end ) whereas mid = start+end / 2
         * Splits until start < end -> splits everyeach elements
         * Merge the split array
         * 
         * */
        private static void split(int[] given, int start, int end) {
            if(start < end ) {                            //stops the recursion when its all split
                int mid = (start + end ) /2 ;
    
                //Recursive:
                split(given, start , mid );//0~half
                split(given, mid+1, end); //half ~ end
    
                //merge the split array
                merge(given, start, mid, end);
            }
    
        }
    
        /** Case 1 : left side ์™€ right side array ๊ฐ€ ๋‘˜ ๋‹ค ์ค€์žฌํ•  ๋•Œ :
         *  given[startpointer] ์™€ given[endpointer] ๋ฅผ ๋น„๊ตํ•˜์—ฌ sort ํ•œ ํ›„, ์‚ฌ์šฉํ•œ ํฌ์ธํ„ฐ๋Š” ++ํ•˜์—ฌ ๋‹ค์Œ์œผ๋กœ ๋„˜๊ฒจ์คŒ
         *  
         *  Case 2 : left ๋งŒ ๋‚จ์Œ 
         *  sorted array์— left๋ฅผ ๋ถ™์ž„
         *  
         *  Case 3 : right ๋งŒ ๋‚จ์Œ
         *  sorted array์— right ๋ถ™์ž„
         * */
        private static void merge(int[] given, int start, int mid, int end) {
            int startPointer = start;
            int index = start;
            int endPointer = mid+1;
    
            //๋‘ ๋ฐฐ์—ด ์ค‘ ํ•˜๋‚˜๋ฅผ ๋‹ค ์˜ฎ๊ธธ ๋•Œ ๊นŒ์ง€ ๋ฐ˜๋ณต
            //Case 1 : 
            while(startPointer <= mid &&  endPointer<= end) {
                if(given[startPointer] < given[endPointer]){     //startPointer๊ฐ€ ๋” ์ž‘์œผ๋ฉด, startpointer++
                    sorted[index] = given[startPointer];
                    startPointer ++;
                }
                else {
                    sorted[index] = given[endPointer];
                    endPointer ++;
                }
                index++;                                         //sorted array์˜ ์ธ๋ฑ์Šค๋ฅผ ํ•œ ์นธ ์˜ฎ๊น€
                }
            //Case 2 and 3 : Case 1์ด ๋๋‚˜๊ณ , left ๋‚˜ right ์—๋งŒ ๋‚จ์Œ
            if(startPointer > mid ) {                                    //right ๋งŒ ๋‚จ์Œ            
                for(int i = endPointer ; i <= end ; i ++) {     //endpointer ~ end ๊นŒ์ง€ sorted ์— ๋”ํ•จ
                    sorted[index] = given[i];
                    index++;
                }
            }
            else {                                                //left ๋งŒ ๋‚จ์Œ
                for(int i = startPointer ; i<= mid ; i++) {        //startpointer ~ mid ๊นŒ์ง€ sorted์— ๋”ํ•จ
                    sorted[index] = given[i];
                    index++;
                }
            }
    
            //์ •๋ ฌ๋œ ๋ฐฐ์—ด์„ ์‚ฝ์ž…
            for(int i = start ; i <= end ;i ++) {
                given[i] = sorted[i];                            //given ์— ํ˜„์žฌ sorted process๋ฅผ ํ•ด๋†“์•„์•ผ๋งŒ, split์ด ๋‹ค์Œ merge๋ฅผ ๋ถˆ๋ €์„ ๋•Œ current process๊ฐ€ ์œ ์ง€
            }
            System.out.println(Arrays.toString(given));
        }
    }
    

    ์žฌ๊ท€๋ฅผ ํ†ตํ•ด ๋ฐฐ์—ด์„ ๋ฐ˜์œผ๋กœ ๋ถ„ํ•  ํ•œ ํ›„, sort ์‹œํ‚ค๋Š” ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•˜์—ฌ ๊ตฌํ˜„ํ•ด ๋ณผ ์ˆ˜ ์žˆ๋‹ค.

     

     


    ํŒจ์ŠคํŠธ์บ ํผ์Šค ํ™˜๊ธ‰ ์ฑŒ๋ฆฐ์ง€ ๋ฐ”๋กœ๊ฐ€๊ธฐ๐Ÿ‘‰ https://bit.ly/3FVdhDa

     

    ์ˆ˜๊ฐ•๋ฃŒ 100% ํ™˜๊ธ‰ ์ฑŒ๋ฆฐ์ง€ | ํŒจ์ŠคํŠธ์บ ํผ์Šค

    ๋”ฑ 5์ผ๊ฐ„ ์ง„ํ–‰๋˜๋Š” ํ™˜๊ธ‰์ฑŒ๋ฆฐ์ง€๋กœ ์ˆ˜๊ฐ•๋ฃŒ 100% ํ™˜๊ธ‰๋ฐ›์œผ์„ธ์š”! ๋” ๋Šฆ๊ธฐ์ „์— ์ž๊ธฐ๊ณ„๋ฐœ ๋ง‰์ฐจ ํƒ‘์Šน!

    fastcampus.co.kr

    ๋ณธ ํฌ์ŠคํŒ…์€ ํŒจ์ŠคํŠธ์บ ํผ์Šค ํ™˜๊ธ‰ ์ฑŒ๋ฆฐ์ง€ ์ฐธ์—ฌ๋ฅผ ์œ„ํ•ด ์ž‘์„ฑ๋˜์—ˆ์Šต๋‹ˆ๋‹ค.

    728x90
    ๋ฐ˜์‘ํ˜•

    ๋Œ“๊ธ€