알고리즘 | 분할정복(Divide and Conquer)

분할 정복 알고리즘은 다양한 알고리즘 설계에서 핵심 원칙으로 사용되고 있다. 

자주 접하는 개념 중에선 Quick Sort, Merge Sort가 분할 정복 알고리즘을 응용한 대표적인 예시이다. 고속 푸리에 변환(FFT)도 분할 정복 알고리즘 기반이라고 한다. 

 

---

분할 정복 알고리즘 

개념

분할 정복(Divide and Conquer)은 큰 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 설계 전략이다. 

 

Divide and Conquer라는 이름의 어원은 원래 정치와 군사 전략에서 사용되던 용어로, 큰 적 또는 문제를 작은 부분으로 나누어 각각을 해결함으로써 전체를 제어하는 전략을 의미한다고 한다. (나무위키에 따르면 제국주의 시절 유럽 식민제국이 식민지인들의 단결을 막기 위해 주로 사용한 방법으로 유명한 분할통치 (Divide and Rule)에서 비롯되었다고 한다.)

 

어원에서 알 수 있듯 아이디어 자체는 오래 전부터 존재했으며, 이를 20세기 중반부터 컴퓨터 과학에서 활용하기 시작했다고 한다. 

 

핵심 아이디어

분할 정복 전략의 핵심 아이디어는 큰 문제를 해결하기 어렵다면, 그 문제를 더 작고 관리하기 쉬운 부분 문제로 나누어 각각 해결하고, 그 해결책들을 결합하여 원래의 문제를 해결하는 것이다.

 

이를 단계별로 구체화하면 다음과 같다: 분할 (Divide) -> 정복 (Conquer) -> 결합 (Combine)

1. 분할 (Divide): 현재의 문제와 동일하되 입력의 크기가 더 작은 다수의 부분 문제로 분할한다.
2. 정복 (Conquer): 부분 문제를 재귀적으로 풀어서 정복한다. 부분 문제의 크기가 충분히 작으면 직접적인 방법으로 푼다. 
3. 결합 (Combine): 부분 문제의 해를 결합해 원래 문제의 해가 되도록 만든다. 

(출처: Introduction to Algorithms)

 

출처: https://www.javatpoint.com/divide-and-conquer-introduction

 

 

장점 및 단점

장점:

1. 문제 단순화: 복잡한 문제를 더 작고 관리하기 쉬운 부분 문제로 나눌 수 있다. 
2. 재사용성: 부분 문제들은 종종 동일한 형태를 가지므로, 하나의 해결 방법을 여러 번 재사용할 수 있다. 
3. 효율성: 문제를 나누는 전략을 통해 문제의 크기를 기하 급수적으로 줄일 수 있다. 이로 인해 일부 알고리즘에서는 더 빠른 실행 시간을 달성할 수 있다. 
4. 병렬 처리 용이: 분할된 부분 문제들은 독립적으로 해결될 수 있으므로, 멀티 코어나 분산 환경에서의 병렬 처리에 적합하다고 한다. 

 

단점:

1. 오버헤드: 문제를 나누고 결과를 합치는 과정에서 추가적인 오버헤드가 발생할 수 있다. (ex. 해결책 병합 과정에서 추가 연산 필요)
2. 메모리 사용량: 재귀적 호출을 사용하면 깊은 재귀에 빠지는 경우 스택 메모리의 사용량이 급증할 수 있다. (ex. 끝 없는 부분 배열 생성)
3. 알고리즘 복잡성: 일반적인 방법보다 복잡한 알고리즘이 될 수 있으며, 설계 및 구현이 어려울 수 있다.

 

대표적인 활용 예시

병합 정렬 (Merge Sort)

• 원리: 배열을 두 부분으로 나눈 다음 각 부분을 재귀적으로 정렬하고, 정렬된 두 부분 배열을 병합한다.
• Merge Sort 장점: 항상 O(nlogn)의 시간 복잡도를 가진다.
• Merge Sort 단점: 추가적인 메모리 공간이 필요하다. (임시 배열 생성 및 값복사, 재귀 호출)

퀵 정렬 (Quick Sort)

• 원리: 배열에서 피벗(pivot) 원소를 선택하고 피벗보다 작은 원소와 큰 원소로 배열을 두 부분으로 나눈다. 이후 각 부분을 재귀적으로 정렬한다. 
• Quick Sort 장점: 평균적인 경우 O(nlogn)의 시간 복잡도를 가진다. 추가 메모리가 거의 필요하지 않다.
• Quick Sort 단점: 이론상, 최악의 경우 O(n^2)의 시간 복잡도를 가질 수 있다.