[알고리즘] Divide and Conquer

우노·2024년 5월 19일

Algorithm

목록 보기

9/10

Divide & Conquer

알고리즘의 기본이 되는 방법론 중 하나이며
한 번에 해결할 수 없는 큰 문제를 재귀적으로 서로 비슷한 작은 문제로 나누고 해결한 뒤 다시 합쳐 큰 문제의 답을 구하는 방법이다.
분할 정복으로 불리지만 실제로 수행하는 과정은 크게 3가지로 나뉜다.

Divide

큰 문제를 더 이상 나누어지지 않을 때까지 하위 문제로 나눈다.
각각의 하위 문제는 큰 문제의 부분이며 하위 문제의 해결 방식은 큰 문제의 해결 방식과 동일하다.

Conquer

하위 문제를 개별적/독립적으로 해결한다.
하위 문제가 충분히 작게 쪼개졌다면 재귀 없이 해결이 가능할 것이다.

Merge

해결된 하위 문제를 재귀적으로 합치고 다시 해결하기를 반복하면서 큰 문제의 해를 구한다.

장점

Solving difficult problems
쉽게 해결하기 어려운 큰 문제 해결
Algorithm efficiency
효율적인 알고리즘(퀵정렬, 병합정렬, 행렬곱 등)의 기반
보통 분할 O(logN), 비교 및 병합 O(N)으로 O(N logN)의 시간복잡도로 해결
Parallelism
서로 개별적/독립적으로 하위 문제를 실행하여 해결할 수 있으므로 다중 프로세서 시스템과 공유 메모리 시스템에 적합
Memory access
하위 문제를 개별적/독립적으로 실행할 수 있으므로 주 메모리에 접근하지 않고 메모리 캐시를 효율적으로 사용 가능
Roundoff control
반올림 계산에서 재귀 호출의 오버헤드가 존재하지만 더 정확한 결과 도출 가능

개선점

Recursion: 재귀 호출 오버헤드 + 잦은 재귀 호출로 재귀 스택 오버플로우 위험
⇒ Explicit stack: 재귀 호출을 피해서 스택, 큐 또는 우선순위 큐 같은 자료구조도 활용 가능
➕ 하위 문제를 잘 선정하는 것도 방법 !

활용 알고리즘과 문제

이 방법을 활용하는 대표적인 알고리즘으로는 퀵 정렬과 병합 정렬 등이 있다.

Merge Sort: 배열을 작은 부분 배열로 만들어 개별적으로 정렬하고 합치기를 반복
Median Finding: 숫자 집합을 재귀적으로 하위 집합으로 나누면서 중앙값을 효율적으로 도출
Min and Max finding: 배열을 반으로 나누고 각 반의 최소-최대 쌍을 비교하면서 하나의 배열에서 동시에 최대/최소를 구하는데 활용 가능
Matrix Multiplication: 행렬을 작은 행렬로 나누고 그 곱을 결합하여 큰 행렬에 필요한 곱셈 횟수를 줄임
Closest Pair problem: 다차원 공간의 점 집합에서 가장 가까운 두 점을 찾는 문제

Decrease & Conquer

분할 정복의 초기 모습이자 간소화 버전이라고 할 수 있으며 해결 과정의 각 단계에서 입력 데이터의 크기를 줄여 문제를 해결한다. 분할 정복과는 각 단계에서 입력 데이터의 크기가 줄어든다는 점에서 차이가 있다.

퀵 정렬, 병합 정렬
하위 문제로 분할하면 각 하위 문제를 해결
⇒ 하위 문제가 2개 이상이므로 분할 정복에 속함

이진 탐색
단순히 탐색 데이터의 크기를 줄이며 하위 문제(원소 탐색)은 하나로 동일
⇒ 감소 정복에 속함

vs Dynamic Programming

Dynamic Programming이 하위 문제로 나누고 이를 해결한 점을 저장하여 효율적인 계산을 돕는다는 점에서 어느 정도 Divide and Conquer의 확장이라고 할 수 있다.

피보나치 문제를 예를 들어보자.

int Fibonacci(int n) {
	if (n == 1)    return 1;
	if (n == 2)    return 1;
	return Fibonacci(n-1) + Fibonacci(n-2);
}
// main에서 호출
Fibonacci(n);
Divide and Conquer ⭕ 하위 문제로 나누어서 풀이
Dynamic Programming ❌ 기존 결과를 재활용하지 않음

int Fibonacci(int n) {
	vector<int> fibo(n+1, 0);
	fibo[0] = 0;  fibo[1] = 1;  fibo[2] = 1;
	for(int i=3; i<n+1; i++) {
		fibo[i] = fibo[i-1] + fibo[i-2];
	}
	return fibo[n];
}
Divide and Conquer ⭕ 하위 문제로 나누어서 풀이
Dynamic Programming ⭕ 기존 결과를 재활용 → Bottom-up 타뷸레이션 방식

vector<int> fibo(n+1, 0);
fibo[0] = 0;  fibo[1] = 1;  fibo[2] = 1;
int Fibonacci(int n) {
	if (fibo[n] == 0)
		memo[n] = Fibonacci(n-1) + Fibonacci(n-2);
	return memo[n];
}
Divide and Conquer ⭕ 하위 문제로 나누어서 풀이
Dynamic Programming ⭕ 기존 결과를 재활용 → Top-down 메모이제이션 방식