[알고리즘] Divide&Conquer

Divide&Conquer 알고리즘

문제를 해결하기 쉽도록 여러 개의 작은 부분으로 나눈 뒤, 문제를 각각 해결 한 후 답을 모음.

• Top-down VS Bottom up
  • Top-down: 기능을 하향식으로 여러 개의 작은 부분으로 문제를 나누어 구체화하여 해결책을 찾는 방법 EX) 분할 정복 설계 전략, 절차 지향 프로그래밍
  • Botton-up: 구체적인 데이터들 간의 상호 관계를 정의함으로써 상향식으로 해결책을 찾는 방법 EX) 상호 관계 정의 설계 전략, 객체 지향 프로그래밍
• 설계 전략: 재귀적 방법으로 분할하고 정복하여 해결함
  • 분할: 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다.
  • 정복: 나눈 작은 문제를 각각 해결한다.
  • 통합: 해결된 해답을 모은다

Divide&Conquer 종류

• 이분 검색(Binary Search): 크기가 n인 정렬된 배열 S에 x가 있는 지를 결정하는 문제
  • 배열을 반으로 쪼개가며 범위 내에 x가 있는 지를 확인하므로, 시간 복잡도 O는 $logn$
• Selection: k번째 작은 원소를 찾는 문제
  • 방법 1: 숫자들을 오름차순으로 정렬한 후, k번째 원소를 찾는다. 시간 복잡도 O는 $nlogn$
  • 방법 2: n개의 데이터들 중에서 가장 작은 최소 숫자를 K번 찾는다. 시간 복잡도 O는 $kN$
  • 방법 3: Partition 알고리즘을 이용하여 k번째 원소를 찾는다.
    • 최적 해의 경우 시간 복잡도 O는 $n$
    • 최악 해의 경우 시간 복잡도 O는 $n^2$
• 정렬 알고리즘: 수를 비 내림차순으로 정렬하는 문제
  • 평균적으로 시간 복잡도 O가 $n^2$이 소요되는 알고리즘( 변화가 없음 )
    • 선택 정렬 / 버블 정렬 / 삽입 정렬
  • 평균적으로 시간 복잡도 O가 $nlogn$이 소요되는 알고리즘 (일부 변화 있음)
    • 합병 정렬: 배열을 더 이상 쪼개지지 않을 때까지 자르고 합치며 정렬. O는 $nlogn$
    • 퀵 정렬: 특정 수를 선정하고 크고 작음으로 나누며 정렬
      • 최적 해의 경우 시간 복잡도 O는 $nlogn$
      • 최악 해의 경우 시간 복잡도 O는 $n^2$
    • 힙 정렬: 변화 없이 시간 복잡도 $nlogn$