학습 목표

• 분할 정복 알고리즘의 원리와 필요성에 대해 이해하고 설명할 수 있음
• 합병 정렬 알고리즘의 원리를 이해하고 수행 과정을 도식화할 수 있음
• 퀵 정렬 알고리즘의 원리를 이해하고 수행 과정을 도식화할 수 있음
• 합병 정렬 알고리즘과 퀵 정렬 알고리즘을 실제로 구현하고 각 단계별 수행 과정을 확인할 수 있음

분할 정복 알고리즘 (보통 재귀적으로 구현함)

• 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘

  • 분할한 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산
  • 이들의 해를 취합하여 원래 문제의 해를 얻음

• 부분 문제와 부분 해

  • 입력 리스트에 대한 분할된 문제를 부분 문제라고 함
  • 부분 문제의 해를 부분 해라고 함
  • 부분 문제는 더 이상 분할할 수 없을 때까지 계속해서 분할함
  • 분할된 부분 문제들의 부분 해를 구하고, 부분 해들을 병합하여 더 큰 문제의 해를 구함(이 때, 부분 해를 병합하는 방법은 알고리즘별로 상이함)

  

분할 과정

• 크기가 n인 입력을 2개로 분할하고, 각각 분할된 부분 문제의 크기가 n/2일 경우의 분할 예

입력 크기가 n일 때 총 분할 횟수

정복 과정