03. 분할 정복 알고리즘

• 알기쉬운 알고리즘(양성봉 저, 생능 출판) 책을 바탕으로 작성한 내용이다.

---

03. 분할 정복 알고리즘

• 주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘이다.

• 분할된 입력의 문제(부분문제, Subproblem)에 대해 동일한 알고리즘을 적용하여 부분해를 얻으며, 이를 취합해서 원래 문제의 해를 얻는다.

  • 더 이상 분할할 수 없을 때까지 계속 부분문제로 분할한다.

• 문제 : 크기가 n인 입력을 3개로 분할하고, 각각 분할된 부분문제의 크기가 n/2이라고 할 때, 총 몇 번 분할하여야 더 이상 분할할 수 없는 크기인 1이 될까?

  • 총 분할 횟수를 k라고 하면, n/2^k = 1이므로 k는 log₂n이 된다.

분할 정복 알고리즘의 분류

• 문제가 a개로 분할되고, 부분문제의 크기가 1/b로 감소하는 알고리즘

  a	b	알고리즘
  2	2	합병 정렬(3.1절), 최근접 점의 쌍 찾기(3.4절), 공제선 문제(연습문제 25번)
  3	2	큰 정수의 곱셈(연습문제 21)
  4	2	큰 정수의 곱셈(연습문제 20)
  7	2	스트라센의 행렬 곱셈(연습문제 22)

• 문제가 2개로 분할되고, 부분문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘

  • 퀵 정렬(3.2절)

• 문제가 2개로 분할되나, 그중에 1개의 부분문제는 고려할 필요가 없고 부분문제의 크기가 1/2로 감소하는 알고리즘

  • 이진탐색(1.2절)

• 문제가 2개로 분할되나, 그중에 1개의 부분문제는 고려할 필요가 없고 부분문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘

  • 선택 문제 알고리즘(3.3절)

• 부분문제의 크기가 1, 2개씩 감소하는 알고리즘

  • 삽입 정렬(6.3절)

  • 피보나치 수의 계산(3.5절)

---

3.1 합병 정렬 (Merge Sort)

3.2 퀵 정렬 (Quick Sort)

3.3 선택 문제 (Selection Problem)

3.4 최근접 점의 쌍 찾기(Closest Pair)

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

• 만약 분할될 때마다 분할된 부분문제의 입력 크기의 합이 기존의 입력 크기보다 매우 커진다면 분할 정복 알고리즘을 적용하는게 부적절할 수 있다.

  • 예를 들어 n번째 피보나치 수를 구할 때 재귀 호출을 사용하면, 분할 후 입력 크기가 거의 2배씩 늘어나므로 반복문을 사용하는게 효율적이다.

• 분할 뿐만 아니라 취합 과정에도 신경을 써야 효율적인 알고리즘이 탄생한다.