분할 정복 기법(Divide & Conquer)

이 포스트는 국민대학교 소프트웨어학부 '알고리즘' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다!

---

문제 해결 과정

1. 분할(Divide): 문제를 2개 이상의 같은 형식의 작은 문제들로 나눕니다.
2. 정복(Conquer): 나눠진 작은 문제들은 재귀적으로 해결합니다. 나눠서 문제를 해결할 필요가 없을 때까지 계속 분할해 나갑니다.
3. 통합(Combine): 풀어낸 작은 문제들의 해답들을 합쳐서 원래 문제의 해답으로 만듭니다.

위에 적은 과정이 주로 분할 정복 기법을 사용해 문제를 풀어나가는 과정입니다. 정복 과정에서 문제들을 재귀적으로 해결해 나가기 때문에 재귀를 이용해서 구현하게 됩니다. 따라서 재귀에 대해 어느 정도 아셔야 합니다.

이 처럼 하나의 큰 문제를 여러 개의 작은 문제들로 분할하는 방식을 Top-down 방식이라 부릅니다. 대표적으로 binary search 문제, merge sort, quick sort를 top-down 방식으로 해결할 수 있습니다.

시간 복잡도 계산

분할 정복 기법에서의 시간 복잡도는 사용하는 알고리즘에서 재귀식을 유도해낸 다음, 재귀식을 풀어서 계산합니다. 배열 내에서 최댓값을 찾는 문제를 예로 들어봅시다. 물론 이 문제를 분할 정복이 아닌 일반 반복문을 통해서 구할 수 있지만, 분할 정복 기법에 맞게 풀어봅시다.

최댓값 찾기

길이가 n(자연수)인 정수형 배열이 주어질 때, 이 배열에서의 최댓값을 찾는 문제를 푼다고 합시다.

예를 들어 길이가 10인 배열 {5, 7, 1, 3, 4, 9, 2, 8, 0, 6}이 들어왔다고 합시다. 이 배열을 절반씩 나눠봅시다. 그러면 {5, 7, 1, 3, 4} 배열과 {9, 2, 8, 0, 6} 배열로 나뉩니다. 그러면 각 배열에서의 최댓값을 구한 다음, 그 값들 중 큰 값을 최종적인 답으로 낼 수 있습니다. 이 아이디어면, {5, 7, 1, 3, 4} 배열의 최댓값도 {5, 7, 1} 배열과 {3, 4}의 배열의 최댓값을 비교해서 얻을 수 있습니다. 이렇게 계속 나뉘면 결국 배열의 길이가 1일 때가 생깁니다 ({5}, {7}, {1} 같은 원소가 하나만 들어있는 배열). 만약 배열의 길이가 1이면 원소 값이 최댓값과 같습니다. 따라서 배열의 길이가 1일 때가 base case가 됩니다. 이를 식으로 표현해보면 아래와 같습니다.

최대값 찾는 식

여기서 k는 배열을 절반으로 나누는 인덱스입니다. 이 알고리즘에서의 핵심 연산은 두 수를 비교하는 연산입니다. 따라서 위의 식을 비교하는 횟수로 바꿔서 표현할 수 있습니다. 길이가 n인 배열에서 최댓값을 찾을 때 수행되는 비교 연산 횟수를 T(n)이라고 합시다. 그러면 T(n)은 아래와 같이 나타낼 수 있습니다.

비교 연산 횟수로 표현한 식

n = 1일 때 0인 이유는 원소 값과 최댓값이 동일해지기 때문입니다. 그리고 n이 1보다 커지면 배열의 각 절반에 대한 연산 횟수들을 더하고 결과 값들을 한 번 비교하기 때문에 1이 더해집니다. 그럼 이 식을 가지고 n = 1일 때부터 5일 때까지 결과를 하나씩 살펴봅시다.

• n = 1, T(1) = 0
• n = 2, T(2) = T(1) + T(1) + 1 = 0 + 0 + 1 = 1
• n = 3, T(3) = T(1) + T(2) + 1 = 0 + 1 + 1 = 2
• n = 4, T(4) = T(2) + T(2) + 1 = 1 + 1 + 1 = 3
• n = 5, T(5) = T(2) + T(3) + 1 = 1 + 2 + 1 = 4

이를 보면 T(n) = n - 1이라 일반화할 수 있습니다. 이를 Big-O notation으로 표기하면 O(n)입니다.

이런 식으로 분할 정복 기법에 대한 시간 복잡도를 계산할 수 있습니다. 이 예시인 경우는 식이 간단했기 때문에 n = 1일 때부터 하나씩 확인해서 알아낼 수 있었지만 주로 점화식을 푸는 방법을 이용해서 계산합니다.