[Algorithm] 분할정복 알고리즘

이미 분할정복 알고리즘을 활용한 대표적인 문제를 몇개 블로그에 작성해놓았다.

여기에는 분할정복의 의미와 사용시에 주의할 점을 작성하고자 한다!

---

💡분할 정복 (Divide-and-Conquer) 알고리즘 ?

• 주어진 문제의 입력을 분할하여 문제를 해결 (정복) 하는 방식의 알고리즘
• 하향식 접근방법 (Top-down)
• 분할한 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하며, 이들의 해를 취합하여 원래의 문제의 해를 얻음.

1. Divide : 나누기
2. Conquer : 각 부분해를 해결
3. Combine : (필요하다면) 부문제의 해를 결합

 

🚫분할 정복을 적용하는데 있어서 주의할 점

• 분할 정복이 부적절한 경우 : 입력이 분할될 때마다 분할된 부분문제의 입력 크기의 합이 분할되기 전의 입력 크기보다 매우 커지는 경우 -> 동일한 일을 반복해서 수행
• 분할된 sub-instance의 크기가 분할 전 instance의 크기보다 크다면 Divide & Conquer 방식은 비효율적이다.

Ex) n 번째의 피보나치 수를 구하는 데, 

• F(n) = F(n-1) + F(n-2)로 정의되므로 재귀 호출을 사용하는 것이 자연스러워 보이나, 이 경우의 입력은 1개이지만, 사실상 n의 값 자체가 입력의 크기이다.
• 따라서, n이라는 숫자로 인해 2개의 부분문제인 F(n-1) , F(n-2)가 만들어지고, 2개의 입력크기의 합이 (n-1) + (n-2) =. (2n-3)이 되어서, 분할 후 입력 크기가 거의 2배로 늘어난다.
• F(5)를 구하기 위해서는 F(3)은 3번, F(2)는 5번이나 중복해서 계산해야한다.

➰효율적인 알고리즘으로 바꿔보자

FibNumber(n)
F(0) = 0;
F(1) = 1;
for i 2 to n
F[i] = F[i-1] + F[i-2]

• 중간 결과를 F배열에 저장해두고 이를 이용한다.
• 시간복잡도 O(n)
• 이처럼, 중간 결과를 배열에 저장해 보다 큰 크기의 instance에 대한 해결을 하는 것을 dynamic programming이라고 부른다.

 

---

분할 정복 알고리즘

1. 합병정렬 : 입력이 2개의 부분문제로 분할, 부분문제의 크기가 1/2로 감소하는 분할 정복 알고리즘
   • O(nlogn)
2. 퀵정렬 : 문제가 2개로 분할, 부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘
   • 최악 : O(n^2)
   • 최선 : O(nlogn)
   • 평균 : O(nlogn)
3. 이진탐색 : 문제가 2개로 분할, 그 중에 1개의 부분문제는 고려할 필요가 없으며, 부분문제의 크기가 1/2로 감소하는 알고리즘
4. 선택문제 알고리즘 : 문제가 2개로 분할, 그중에 1개의 부분문제는 고려할 필요가 없으며, 부분문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘
   • 최선 : O(n)
   • 최악 : O(n^2) (퀵정렬에서 일어나는 최악의 경우와 같음)
   • 평균 : O(n) (good 분할 vs. bad 분할)
5. 삽입정렬, 피보나치 수 : 부분문제의 크기가 1,2개씩 감소하는 알고리즘
6. 최근접점의 쌍 문제 알고리즘
   • O(nlog(^2)n) : y좌표에 대한 정렬을 합병과정에서 처리할 경우
7. 트로미노 타일로 체스판 채우기 알고리즘
   • 체스판 차원 n : O(n(^2)logn) = O(logn) x O(n^2)

 

 

---

Reference

서울과학기술대학교 컴퓨터공학과 알고리즘 수업