분할 정복 (Devide & Conquer)

분할 정복 (Devide & Conquer) 이란?

• 한 번에 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 알고리즘.
• 분할하여 푼 문제들을 다시 합병하여 문제의 답을 얻음
• 주로 재귀함수로 구현하여 나눌수 없는 순간까지 나눔.
• 분할 방법에 따라 시간 복잡도는 천차만별. 구현 방법에 따라 시간 복잡도가 다양하다.
• 입력범위 N이 큰 편이다.
• 재귀 함수를 구현할 때에는 무한루프에 빠지지 않도록 기저조건을 확실히 해야한다.

 

---

분할 정복의 순서

1. Devide: 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다.
2. Conquer: 나누어진 문제에 대해서 해결을 한다. 만약 더 쪼개질 수 있다면 Devide과정을 수행한다.
3. Combine: Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다.

문제를 제대로 나누어야 Conquer하는 과정이 편해진다.

분할 정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할 정복 알고리즘의 효율성을 깎아내릴 수 있다.

---

대표적인 사례 (Merge Sort)

합병 정렬(Merge Sort)은 분할 정복 알고리즘 문제의 대표적인 사례이다.

러닝타임은 O(nlogn).

 

합병 정렬은 주어진 수열을 쪼갤수 있는 최소한의 단위로 나누어 합치면서 수를 정렬하는 알고리즘이다.

Devide 과정에서는 쪼개는 일만 일어나고, Conquer 과정에서 비교를 통해 합쳐지는 것이 특징이다.

Merge Sort에 관한 자세한 내용

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

---

연관 문제

1629: 곱셈 - Sliver 1

2630: 색종이 만들기 - Sliver 3

10830: 행렬 제곱 - Gold 4

1244: 스위치 켜고 끄기 - Sliver 4