저번 글에서 Recursion을 공부한 것을 토대로 이번 시간에는 Recursion을 사용한다는 점에서 Dynamic Programming과 유사하지만 약간 다른 Divide and Conquer을 배워보도록 하겠습니다.
그리고 분할 정복 알고리즘을 이용하여 해결할 수 있는 가장 대표적인 문제인 하노이의 탑도 풀이해보겠습니다.
1. Divide and Conquer(분할 정복) 알고리즘
Divide and Conquer를 2문장으로 나눠서 설명하자면,
1. algorithm design paradigm(방법) - 즉, 하나의 알고리즘 디자인 패러다임입니다.
2. based on multi-branched recursion - 여러 갈래의 재귀에 기반합니다.
저번 글에서 factorial을 recursion으로 풀었던 문제는 singile-branced recursion이라고 할 수 있다면,
분할 정복 알고리즘은 다음과 같은 그림으로 multi-branched recursion이라고 할 수 있습니다.
분할 정복은 다음과 같은 과정으로 진행됩니다.
- 어떤 문제를 풀 때, size가 n인 문제를 n/2인 문제 두 개로 나눈다.(recursion)
- 또 다시, 방금 나눈 두 문제를 n/4 짜리 문제 4개로 나누고 -> 또 둘씩 나눠지는 것이 반복된다.
- 그래서 나누어져서 size가 작아진 문제들을 하나씩 해결한다.
- 위 사진의 방법은 2-branched-recursion임. (두 갈래로 나뉘기 때문)
여기서 Dynamic Programming과의 차이점이 나오는데, Dynamic Programming도 분할 정복과 유사하게 큰 문제를 작은 문제로 나눠서 해결한다는 비슷한 관점을 가지고 있지만 DP는 single-branced recursion(소문제가 종속적이다) 분할 정복은 multi-branched recursion(소문제가 독립적이다)라는 핵심적인 차이점을 가지고 있다.
2. divide-and-conquer approch (분할 정복 접근)
- 몇가지의 original problem과는 유사하지만 size는 더 작은 subproblem들로 쪼갠다.(Divide - 분할)
- 각각의 subproblem들을 recursively(재귀적으로) 해결한다.(Conquer - 정복)
- 그 후, original problem을 해결하기 위한 solution을 만들기 위해 위 결과로 나온 solution들을 결합한다.
(Combine - 결합)
정리하자면, The divide-and-conquer 패러다임은 다음과 같은 세 가지 단계(recursion의 각 레벨)를 수반한다고 생각하면 됩니다.
- 같은 문제의 더 작은 instances의 수많은 sub-problem들로 Divide 한다.
- 그들을 재귀적으로 풀어냄으로써 작은 문제들을 정복한다.
- 작은 문제들에 대한 솔루션을 결합하여 original problem에 대한 솔루션을 만들어낸다.
3. 분할정복의 큰 틀
<psuedo code>
function F(x):
if F(x)의 문제가 간단 then :
return F(x)를 직접 계산한 값
else:
x를 y1, y2로 분할
F(y1);
F(y2);
return F(y1), F(y2)로부터 F(x)를 구한 값; 즉 문제의 정의!!
큰 문제를 2개 이상의 작은 문제로, 즉 y1과 y2로 나누고 만약 y1 또는 y2가 바로 계산할 수 있다면 (base case의 경우) 계산한 값을 반환함으로써 작은 문제를 하나씩 해결해 나가면서 큰 문제를 해결할 수 있다!
위 코드는 분할 정복이나 재귀 문제를 구현하기 전에 미리 짜 보면 좋은 psuedo code 입니다.
어떤 문제를 위와 같이 먼저 구성해 보면 좋은 것이 여기서DP(다이나믹 프로그래밍)로도 파생이 되는 경우 약간만 수정하면 적용이 됩니다.
또한 재귀, 백트래킹, 분할 정복에서 가장 중요하고 가장 먼저 생각해야 하는 것은 base case를 찾는 것임을 명심합시다.
Q) size에 따라 iterative 방법과 recursive 방법이 더 좋은 것이 있을 것인데 이를 어떻게 판단하는가?
A) 각각의 장단점이 존재하고 무엇을 쓸 지에 대한 명확한 기준은 없으나 프로그래머가 판단했을 때 몇 줄만에 코드가 끝나고 size가 적당하다면 recursive를 사용하지만 data의 size가 너무 크면 iterative를 사용한다.
4. 하노이의 탑
https://www.acmicpc.net/problem/11729
백준 11729번, 재귀를 사용해 문제를 해결하는 대표적인 예제이다.
하노이의 탑에 관련된 배경 지식들은 인터넷 링크를 아래에 공유해두었다.
# 하노이의 탑 코드
def hanoi_tower(n,start,end):
if n==1: # Base case_ 엔딩 상황
print(start,end)
return
hanoi_tower(n-1,start,6-start-end)
# 시작 지점에서 시작과 최종 지점을 제외한 유일한 막대에 N-1개의 원반을 놓아야한다.
print(start,end)
# 시작 지점에 남아있는 마지막 제일 큰 원반을 최종 지점에 놓아준다.
hanoi_tower(n-1,6-start-end,end)
# N-1 개를 옮긴 막대에서 끝지점으로 옮겨준다.
n= int(input())
print(2**n-1) # 원반에 개수에 따라 시행되는 횟수가 규칙적으로 정해진다
hanoi_tower(n,1,3)
원반을 이동시킨 횟수에서 알 수 있듯이 이 코드의 시간 복잡도를 big-O로 표현하게 된다면 O(2**n)이 된다!
* Reference
[자료구조와 알고리즘 | 파이썬] Recursion and Backtracking(재귀 & 백트래킹) + Divide and Conquer(분할정복)
1. Recursion 우리는 목표를 달성하기 위해 어떠한 메소드 안에서 또 다른 메소드를 호출할 수 있다는 사실을 알고 있습니다. 이와 유사하게 메소드는 자기 스스로 또한 호출할 수 있습니다. Recursion
cdragon.tistory.com
https://study-all-night.tistory.com/6
[백준 11729번] 하노이 탑 이동순서 - Python(파이썬) 자세한 풀이
1. 문제 백준 11729번 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓
study-all-night.tistory.com
https://namu.wiki/w/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98%20%ED%83%91#s-3.6
하노이의 탑
파일:external/437a6637b1f6834a74146f6e51b7360fa64116c23c3c0c7fd546
namu.wiki
'자료구조,알고리즘(Python)' 카테고리의 다른 글
7. Abstract Data Types(ADT) (1) | 2024.09.15 |
---|---|
5. Brute Force(완전 탐색), Back tracking (1) | 2024.09.13 |
3. Recursion (0) | 2024.09.08 |
2. Searching(탐색)_Linear, Binary (0) | 2024.09.03 |
1. Python에서의 객체(Object) (2) | 2024.09.01 |