분할 정복 : Divide and Conquer

분할 정복은 큰 문제를 작은 문제로 나누어 해결하는 기법인데,
문제의 사이즈가 바뀔지언정 문제의 내용이 바뀌진 않다보니 재귀와 연관지어서 많이 공부하게 된다.

아주 간단한 분할 정복의 예제는 병합 정렬이 있다.

1. 병합 정렬은 기존의 정렬 대상으로 주어진 배열을 더 이상 나눌 수 없을 때까지 분할한다.
2. 더 이상 나눌 수 없는 경우부터 각 배열을 정렬한다.
3. 나눈 배열들을 병합하며 정렬된 형태로 마무리한다.

• 분할 정복의 시간 복잡도는 n logn이다. 효율적인 정렬 알고리즘 중 하나 이다.

전체적인 진행구조는 이렇게 된다 :

1. 분할 : 큰 문제를 여러 개로 나눈다.
2. 정복 : 나눠진 작은 문제를 각각 독립적으로 해결한다. 보통은 재귀함수를 사용한다.
3. 결합 : 작은 문제들의 해답을 모아 기존 문제의 해답을 도출한다.

특징은 이렇다.

1. 작은 문제들은 동일한 문제 형태를 가진다. 그럼에도 독립적이다.
2. 재귀랑 많이 연관지어서 구현된다.
3. 문제라는 단어 사용 특성 상 어떤 특정한 문제 해결에 국한되지 않고, 많은 부분에서 사용 될 수 있다.

분할 정복은 재귀랑 많이 엮이는 만큼 장단점도 재귀함수랑 많이 엮인다.

• 장점
  • 효율적이다. 복잡한 문제도 처리를 쉽게 생각 할 수 있다.
  • 각 하위 문제는 독립적이니 병렬 처리로써 계산 속도를 크게 향상 시킬 수 있다.
  • 특징에서도 언급했지만 특정한 문제 해결에 국한되지 않는다.
• 단점
  • 병합 과정에서 추가적인 비용이 발생 할 수 있다.
  • 같은 하위 문제를 여러 번 반복 할 수 있다. 이 부분의 경우, 이전 하위 문제의 결과를 기억한다거나 동적 계획법(DP)이 필요하다.