분할 정복

1. 문제 제시 : 가짜 동전 찾기

• n개의 동전들 중에 가짜 동전이 하나 포함되어 있다. 가짜 동전은 진짜 동전에 비해 아주 조금 가볍다. 진짜 동전들의 무게가 동일하다고 할 때 양팔 저울을 이용해서 가짜 동전을 찾아보자.
• 양팔 저울을 최소로 사용해서 가짜 동전을 찾는 방법은 무엇인가?
• 예를 들어 동전이 24(진짜 23, 가짜 1)개 있다면?

---

2. 분할 정복 기법

• 설계 전략
  • 분할(Divide) : 해결한 문제를 여러 개의 작은 부분으로 나눕니다.
  • 정복(Conquer) : 나눈 작은 문제를 각각 해결한다.
  • 통합(Combine): (필요하다면) 해결된 해답을 모은다.

---

3. 거듭 제곱

---

4. 병합 정렬(Merge Sort)

• 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식입니다.
• 분할 정복 알고리즘 활용
  • 자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻어냅니다.
  • top-down 방식
• 시각 복잡도
  • O(n long n)