3장. 분할정복법

실습_3. 분할정복법

재귀호출을 이용한 문제 해결

• 재귀함수의 올바른 디자인 및 해석 ** 재귀함수를 디자인 하기 위한 세 가지 단계
  1. 함수의 정의를 명확히 한다
  2. 기저 조건에서 함수가 제대로 동작하게 작성한다
  3. 함수가 제대로 동작한다고 가정하고 함수를 완성한다

분할정복법

• 문제를 소문제로 분할
• 각각의 소문제를 해결

• 소문제의 해결 결과를 이용해 전체 문제를 해결

• 어렵다

• 수학적 문제 해결 능력이 가장 중요
• 키보드 대신에 노트와 펜을 들고 생각

대표 예제

• 합병정렬
• 퀵정렬
• 거듭제곱 구하기
• 연속 부분 최대합
• 가장 가까운 두 점 찾기
• 히스토그램

---

• 코딩 능력 != 문제 해결 능력