분할정복
분할정복(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);
}- 위 함수는 전체 배열(
vec)과 부분 배열의 시작(s)과 끝(e)을 인자로 받는다. - 부분 배열을 왼쪽(
L)과 오른쪽(R)을 재귀호출로 나눌 수 없을 때까지 쪼갠다. - 더 이상 나눌 수 없다면(크기가 1인 부분배열) 현재 가리키는 원소를 리턴한다.
- 리턴받은
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;
}- 여기서
M은 위split함수를 통해 얻어지는데, 둘로 나눈 부분 배열의mid를 기준으로 왼쪽으로/오른쪽으로 점진적으로 이동하며 최대값을 찾아낸다. mid기준 왼쪽 최댓값(lMax)과 오른쪽 최댓값(rMax)를 더해 최종적으로 겹친 부분의 최댓값을 리턴한다.- 위의 과정으로 배열을 결합하고 마지막으로 배열
vec의L과R,M을 비교하여 최대 부분 배열의 원소의 합을 도출해낼 수 있다.
tik tok