학습 일자 : 2023.

큰 문제를 작은 문제로 나눠서 푸는 하향식 접근 방식의 알고리즘

문제를 일단 분할 후 분할 된 작업을 해결(정복)하는 과정을 수행하는 알고리즘

• 분할(Divide) : 문제가 분할이 가능한 경우, 2개 이상의 하위 문제로 나누기
• 정복(Conquer) : 하위 문제가 여전히 분할이 가능한 경우 다시 분할 과정을 수행

분할 정복 과정

분할, 정복, 결합 순서로 문제를 해결한다.

1. 분할 : 문제가 분할이 가능한 경우 2개 이상의 하위 문제로 나눔
2. 정복 : 하위 문제가 또 다시 분할이 가능한 경우 1번(분할) 과정을 다시 수행, 분할이 불가능하다면 문제를 품
3. 결합 : 2번(정복)과정에서 푼 답을 가져온다.

[분할정복 예시]

<하노이 탑>

: 한쪽에 쌓에 였는 블럭 전체를 다른 쪽으로 옮기는 게임

게임 규칙

1. 한번에 1개의 블럭만 이동이 가능하다.
2. 블럭을 쌓을 때 자신보다 큰 블럭은 위로 쌓을 수 없다.

1. 분할 : n번째 블럭을 옮기기 위해서는 n-1번째 블럭을 다른쪽 위치(Auxiliary)로 이동시켜야 함.
2. 정복 : 원하는 블럭만 남으면, 원하는 블럭을 원하는 위치(Destination)로 이동함
3. 결합 : 모든 블럭이 원하는 위치(Destination)로 이동을 함

<하노이탑 프로그램>

👩‍💻 [소스 확인하기]