[알고리즘]분할정복 (백준 10211번)

분할정복

---

분할정복(divide-and-conquer) 이란 문제를 더 작은 문제로 쪼개고 작은 문제에 대한 해를 찾고 결합하여 원 문제를 해결하는 알고리즘이다.

특징

• 어떤 문제를 같은 유형의 더 작은 문제로 해결 할 수 있을 때 사용할 수 있는 알고리즘이다.
• 큰 문제에서 시작해 작은 문제로 내려가는 하향식 접근 방법(top-down)이다. (동적 프로그래밍은 상향식 접근 방법)
• 주로 재귀적으로 구현하고, 함수 호출로 인한 오버헤드가 발생한다는 단점이 있다.

분할정복의 기본 알고리즘은 간단하게 아래처럼 나타낼 수 있다.

기본 알고리즘
1. 문제를 더 작은 문제로 분할한다.
2. 작은 문제를 재귀적으로 해결한다.
3. 작은 문제의 해결을 결합하여 큰 문제를 해결한다.

백준 10211번

---

(백준 10211번 : Maximum Subarray)

문제

• 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾고 원소의 합을 출력해라.

이 문제는 분할정복을 사용해 O(NlogN) 에 해결할 수 있다.

아이디어
1. 배열 X를 반으로 나누어 최대 부분 배열이 왼쪽에 있을 때, 오른쪽에 있을 때, 두 부분에 걸쳐있을 때. 총 3가지의 경우로 구분한다.
2. 배열을 더 이상 나눌 수 없을 때까지 재귀적으로 쪼갠다.
3. 위 3가지 경우를 계산하고 가장 큰 값을 리턴하면서 배열 X의 최대 부분 배열을 찾는다.

전체 코드

#include <iostream>
#include <vector>
using namespace std;

int split(vector<int>& vec, int L, int R, int mid)
{
	int sum = 0;
	int lMax = -99999;
	int rMax = -99999;
	for (int i = mid; i >= L; --i)
	{
		sum += vec[i];
		lMax = (sum > lMax) ? sum : lMax;
	}
	sum = 0;
	for (int i = mid + 1; i <= R; ++i)
	{
		sum += vec[i];
		rMax = (sum > rMax) ? sum : rMax;
	}
	
	return lMax + rMax;
}

int solve(vector<int>& vec, int s, int e)
{
	if (s == e) return vec[s];

	int mid = (s + e) / 2;
	int L = solve(vec, s, mid);
	int R = solve(vec, mid + 1, e);
	int M = split(vec, s, e, mid);
	
	return L > R ? (L > M ? L : M) : (R > M ? R : M);
}

int main()
{
	int T = 0;
	cin >> T;
	for (int t = 0; t < T; ++t)
	{
		int N = 0;
		cin >> N;
		vector<int> vec(N, 0);
		for (int i = 0; i < N; ++i)
		{
			cin >> vec[i];
		}

		cout << solve(vec, 0, N - 1) << "\n";
	}
}

---

해설

int solve(vector<int>& vec, int s, int e)
{
	if (s == e) return vec[s];

	int mid = (s + e) / 2;
	int L = solve(vec, s, mid);
	int R = solve(vec, mid + 1, e);
	int M = split(vec, s, e, mid);
	
	return L > R ? (L > M ? L : M) : (R > M ? R : M);
}

1. 위 함수는 전체 배열(vec)과 부분 배열의 시작(s)과 끝(e)을 인자로 받는다.
2. 부분 배열을 왼쪽(L)과 오른쪽(R)을 재귀호출로 나눌 수 없을 때까지 쪼갠다.
3. 더 이상 나눌 수 없다면(크기가 1인 부분배열) 현재 가리키는 원소를 리턴한다.
4. 리턴받은 L과 R과 M을 비교하여 가장 큰 변수를 리턴한다.

int split(vector<int>& vec, int L, int R, int mid)
{
	int sum = 0;
	int lMax = -99999;
	int rMax = -99999;
	for (int i = mid; i >= L; --i)
	{
		sum += vec[i];
		lMax = (sum > lMax) ? sum : lMax;
	}
	sum = 0;
	for (int i = mid + 1; i <= R; ++i)
	{
		sum += vec[i];
		rMax = (sum > rMax) ? sum : rMax;
	}
	
	return lMax + rMax;
}

5. 여기서 M은 위 split함수를 통해 얻어지는데, 둘로 나눈 부분 배열의 mid를 기준으로 왼쪽으로/오른쪽으로 점진적으로 이동하며 최대값을 찾아낸다.
6. mid기준 왼쪽 최댓값(lMax)과 오른쪽 최댓값(rMax)를 더해 최종적으로 겹친 부분의 최댓값을 리턴한다.
7. 위의 과정으로 배열을 결합하고 마지막으로 배열vec의 L과 R, M을 비교하여 최대 부분 배열의 원소의 합을 도출해낼 수 있다.