분할 정복 알고리즘
📍 분할 정복 알고리즘, Divide and conquer algorithm
그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법.
보통 재귀 함수로 자연스럽게 구현한다.
def F(x):
if F(x)의 문제가 간단 then:
return F(x)을 직접 계산한 값
else:
x를 y1, y2로 분할
F(y1)과 F(y2)를 호출
return F(y1), F(y2)로부터 F(x)를 구한 값이때 else 부분에 해당되는 작은 부문제로 분할할 경우에 부분제를 푸는 알고리즘까지 재귀호출로 해버리면 오버헤드 때문에 실행 속도가 늦어져 재귀 호출이 아닌 스택, 큐 등의 자료구조를 쓰기도 한다.
예시
이 세가지가 분할정복 방법중 가장 유명하다. 모두 블로그에 정리 해 놓았다.
백준 문제
| 문제 | 풀이 |
|---|---|
| 백준 11729 - 하노이 탑 이동 순서 | ✖풀이예정✖ |
| 백준 1992 - 쿼드 트리 | ✖풀이예정✖ |
| 백준 2447 - 별찍기 - 10 | ✖풀이예정✖ |
| 백준 2448 - 별 찍기 - 11 | ✖풀이예정✖ |
| 백준 1517 - 버블 소트 | ✖풀이예정✖ |
참고자료
🔥https://devyuseon.github.io/ 로 이사중 입니다!!!!!🔥