[개념 학습 및 정리] 분할 정복법

1. 분할 정복법

분할 정복법은 거의 대부분 재귀호출을 이용하여 해결하는 경우가 많다.

• 문제를 소문제로 분할 (합병 정렬, 퀵 정렬)
• 각각의 소문제를 해결
• 소문제의 해결 결과를 이용하여 전체 문제를 해결

 

 

 

2. 연속 부분 최대합

연속된 부분을 선택하여 그 합이 최대가 되게 하는 방법 (단, n은 1이상 100000이하)

2

1

-2

5

-10

3

2

5

-3

7

9

-10

 

문제 이해)

• 완전 탐색법으로 가능한 모든 경우의 수를 고려, 전체 시간은 O(n^3) 걸리기에 완전 탐색법은 불가능
• 분할 정복법으로 접근

 

알고리즘 개발)

우선 절반으로 나누어 각 소문제의 최대합을 찾아서 문제를 해결한다.

 

[소문제 1] 최대합은 6

2

1

-2

5

-10

3

 

[소문제 2] 최대합은 20

2

5

-3

7

9

-10

 

 

[자른 지점을 포함하는 부분]

자른 지점을 포함하는 연속 부분의 최대합을 고려해야한다. 자른 지점을 기준으로 왼쪽의 최대값과 오른쪽의 최대값의 합이 자른 지점의 최대값이다.

자른 지점을 포함하는 부분

 

마지막으로 왼쪽만 포함하는 경우(6)와 오른쪽만 포함하는 경우(20), 자른 자리를 포함하는 경우(23) 중 가장 최대값이 답이다.

 

알고리즘 증명) 모든 경우(왼쪽, 오른쪽, 자른 지점)를 고려

 

알고리즘 시간복잡도)

• T(n)은 N개의 숫자 중 연속 부분 최대합을 구하는데 걸리는 시간
• 왼쪽 T(n/2)
• 오른쪽 T(n/2)
• 자른지점 기준 왼쪽, 오른쪽 각각 O(n)
• T(n) = T(n/2) + T(n/2) + O(n)
• T(n) = 2T(n/2) + O(n)
• 즉, 시간복잡도는 O(n logn)

 

코드 작성)

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static int n;
    static int[] data;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        data = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            data[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(getSubMax(0, n-1));

        bw.flush();
        bw.close();
        br.close();
    }

    static int getSubMax(int s, int e) {

        if(s == e) return data[s];
        else {
            int mid = (s+e)/2;
            int left = getSubMax(s, mid); // 왼쪽 부분의 최대합
            int right = getSubMax(mid+1, e); // 오른쪽 부분의 최대합

            int leftMax = -987987987;
            int leftSum = data[mid];
            for(int i = mid-1; i >= 0; i--) {
                leftSum += data[i];

                if(leftMax < leftSum) leftMax = leftSum;
            }

            int rightMax = -987987987;
            int rightSum = 0;
            for(int i = mid+1; i <= e; i++) {
                rightSum += data[i];

                if(rightMax < rightSum) rightMax = rightSum;
            }

            int midMax = leftMax + rightMax;

            return Math.max(Math.max(left, right), midMax);
        }
    }

}
/*
예제 입력
12
2 1 -2 5 -10 3 2 5 -3 7 9 -10

예제 출력
23
 */