분할정복(Divide & Conquer)

특정한 문제를 풀이함에 있어 큰 문제를 작은 문제로 나뉘어서 푸는 방법들에 대해서는 앞선 포스트들을 통해 계속해서 언급하였다. 오늘 다룰 분할정복(Divide & Conquer)은 그 패러다임을 가장 직관적으로 다루는 테크닉이라고 볼 수 있다.

 

주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해내는 것

분할정복은 아래의 세 구성요소로 다시 생각해볼 수 있다.

1. Divide : 문제를 더 작은 문제로 분할하기
2. Merge : 각 문제의 답을 원래 문제에 대한 답으로 병합
3. Base Case : 더 이상 분할하지 않고 곧장 풀 수 있는 매우 작은 문제

세 구성요소에 대해서는 부가적인 설명이 필요없을 것으로 보이나, 분할정복으로 특정 문제를 정복(?) 하기 위해서는 말 그대로 큰 문제가 작은 문제로 나눠질 수 있는가? 각 작은 문제의 답을 조합해 원래 문제의 답을 계산할 수 있는가? 를 고민해봐야만 한다.

 

행렬의 거듭제곱을 예시로 왜 분할정복이 의미가 있는가를 살펴보자.

행렬 곱셈 방식(이미지 출처: https://mathbang.net/562)

n x n 크기의 행렬 A를 m번 곱한 거듭제곱을 구한다고 했을 때, Brute Force를 이용한다면 O(n³m)의 시간 복잡도가 걸리게 된다. 단순히 행렬을 연산하는 과정에서 O(n³) 의 연산이 필요하고, 이를 m번 수행해야 하기 때문이다. N과 M의 크기가 커질수록 연산횟수가 기하급수적으로 늘어나는 것을 확인할 수 있다.

 

그럼 문제를 나눠서 생각해보자.

 

1. Divide: 문제를 더 작은 문제로 분할하기

Aⁿ = A ^ (2/n) * A ^ (2/n)

행렬의 곱셈에는 결합법칙을 적용할 수 있으므로 문제를 분할할 수 있다.

ABC  = (AB)C = A(BC) 

 

2. Merge: 각 문제의 답을 원래 문제에 대한 답으로 병합

앞서 1번에서 행렬의 곱셈에는 결합법칙이 적용됨을 얘기했으므로, 큰 문제의 답으로 병합하는 과정 역시 문제없이 적용할 수 있다.

 

3. Base Case: 더 이상 분할하지 않고 곧장 풀 수 있는 매우 작은 문제

특정 행렬의 0승은 단위 행렬을 의미하며, 1승은 해당 행렬 그 자체를 가리키므로 가장 작은 문제가 존재한다.

 

 

A⁴가 있을 때, A * A³ 이 아니라 A² * A² 으로, 즉 '좀 더 절반에 가깝게 나누는 것이 좋지 않을까'라고 생각할 수 있다.

실제로 문제의 크기가 절반에 가깝게 줄어들수록 우리는 기저 사례(Base Case)에 조금 더 빠르게 도달할 수 있다. 따라서, 분할정복 문제에서는 대개 가능한 한 절반에 가깝도록 문제를 나누고자 한다. 하지만 이것은 항상 정답이 될 수 없는데 만약 구하고자 하는 거듭제곱 m이 홀수라면 어떨까?

 

이미지 출처: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 1권_분할정복_180p_구종만 지음

홀수를 무작정 절반으로 나눠서 수행하는 것보다, 1을 빼서 짝수로 만든 다음 반갈죽 하는 것이 보다 효과적임을 알 수 있다. 왜냐하면 홀수를 절반으로 나눠서 수행할 경우, 절반으로 나눠진 m을 산정하는 과정에서 드는 추가적인 연산과 같은 결과를 만들어내기 위해 반복적으로 호출되는 함수의 횟수가 늘어나기 때문이다.

 

이 반복적으로 호출되는 함수의 횟수를 줄이기 위해 고안되고 사용되는 것이 직전 포스트인 '동적 계획법(Dynamic Programming)'이다.

 

정리하자면, 같은 분할정복 문제를 풀이하더라도, 어떻게 분할하느냐에 따라서 시간 복잡도 차이가 크게 차이가 날 수 있다. 문제를 어떻게 분할하였을 때 가장 효과적일지는 반복적인 연습을 통해 직관을 키우는 수 밖에 없다!

---

정리

• 문제를 더 작은 문제로 분할하는 것이 '분할정복'의 개념
• 어떻게 분할하느냐에 따라 시간 복잡도에 차이가 발생

---

참고문제

1. Silver 3 - 6580번 쿼드 트리

6580번: 쿼드 트리

2. Silver 2- 1780번 종이의 개수

 

1780번: 종이의 개수

3. Gold 4 - 10830번 행렬 제곱

10830번: 행렬 제곱

---

Reference

1.  프로그래밍 대회에서 배우는 알고리즘 문제해결전략 1권_분할정복_175p_구종만 지음