분할 정복(Divide and Conquer)

- 큰 문제를 작은 부부분 문제로 나누어 해결하는 방법  ex) 합병 정렬, 퀵 정렬, 이진 검색...

 

- 분할 정복 과정

1. 문제를 하나 이상의 작은 부분들로 분할
2. 부분들을 각각 정복
3. 부분들의 해답을 통합하여 원래 문제의 답을 구함

장점

- 문제를 나누어 처리하며 어려운 문제 해결 가능

- 병렬 처리에 이점이 있음

 

단점

- 메모리를 많이 사용(재귀 호출 구조)

 

 

 ❖ 분할해서 배열에서 최대 값 구하기

    public static int getMax(int[] arr, int left, int right) {
        int m = (left + right)/2;

        if(left == right) {
            return arr[left];
        }

        left = getMax(arr, left, m);
        right = getMax(arr, m+1, right);

        return (left > right) ? left : right;
    }

 

❖ 가장 큰 배열 합

 // 정수형 배열 nums에서
    // 연속된 부분 배열의 합 중 가장 큰 값을 출력하세요

    // nums : -5 0 -3 4 -1 3 1 -5 8
    // 출력 : 24
    public static int solution(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }

        return divideSubArrays(nums, 0, nums.length-1);
    }

    public static int divideSubArrays(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }

        int mid = left + (right - left) /2;
        int maxLeft = divideSubArrays(nums, left, mid);
        int maxRight = divideSubArrays(nums, mid+1, right);
        
        int maxArr = getMaxSubArray(nums, left, mid, right);

        return Math.max(maxLeft, Math.max(maxRight, maxArr));
    }

    public static int getMaxSubArray(int[] nums, int left, int mid, int right) {
        int sumLeft = 0;
        int maxLeft = Integer.MIN_VALUE;

        for(int i = mid; i>= left; i--) {
            sumLeft += nums[i];
            maxLeft = Math.max(maxLeft, sumLeft);
        }

        int sumRight = 0;
        int maxRight = Integer.MIN_VALUE;

        for(int i  = mid+1; i <= right; i++) {
            sumRight += nums[i];
            maxRight = Math.max(maxRight, sumRight);
        }

        return maxLeft + maxRight;
    }

 

❖ 링크드 리스트 합병

   // 2차원 정수형 배열 lists에는 각 링크드 리스트의 원소 정보가 들어 있고 오름차순으로 정렬된 상태
   // 모든 링크드 리스트를 하나의 정렬된 링크드 리스트로 합병하시오

   // lists : {{2, 3, 9}, {1, 5, 7}, {3, 6, 7, 11}}
   // 출력 : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 11
    
    public static Node solution(Node[] lists) {
        if(lists == null || lists.length == 0) {
            return null;
        }

        return divideList(lists, 0, lists.length-1);
    }

    public static Node divideList(Node[] lists, int left, int right) {
        if(left == right) {
            return lists[left];
        }

        int mid = left  + (right-left) /2;
        Node l1 = divideList(lists, left, mid);
        Node l2 = divideList(lists, mid + 1, right);

        return mergeList(l1, l2);
    }

    public static Node mergeList(Node l1, Node l2) {
        if(l1 == null) {
            return l2;
        }
        if(l2 == null) {
            return l1;
        }

        Node merge = new Node(0);
        Node cur = merge;
        
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else { 
                l2 = l2.next;
            }
            cur = cur.next;
        }

        if( l1 !=null) {
            cur.next = l1;
        } 
        if( l2 != null) {
            cur.next = l2;
        }

        return merge.next;
    }
    // 문제에 주어진 2차원 배열을 각각의 링크드 리스트로 구성
    public static void setUpLinkedList(Node[] node, int[][] lists) {
        for(int i = 0; i< lists.length; i++) {
            node[i] = new Node(lists[i][0]);
        }

        for(int i = 0; i< lists.length; i++) {
            Node cur = node[i];
            for(int j = 1; j< lists[i].length; j++) {
                cur.next = new Node(lists[i][j]);
                cur = cur.next;
            }
        }
    }

    public static void printList(Node node) {
        Node cur = node;
        while(cur.next != null) {
            System.out.print(cur.val + " -> ");
            cur = cur.next;
        }
        System.out.println(cur.val);
    }
    
    
    
    main
    	int[][] lists = {{2,3,9}, {1,5,7} , {3,6,7,11}};
        Node[] node = new Node[lists.length];
        setUpLinkedList(node, lists);
        Node combinedNode = solution(lists);    // 각가의 링크드 리스트를 하나로 합침
        printList(combinedNode);