[key word] 동적계획법, 다이나믹, 최적해, 재귀호출, 리카시브, 엔나치
파이썬 실습창을 열 수 있습니다.실습창 열기

저 높은 곳까지
계단 오르기

한 번에 최대 3계단을 오를 수 있는 사람이
5개의 계단을 올라가는 방법은 13가지가 있습니다.
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
그렇다면 10개의 계단을 올라가는 방법은 몇가지일까요?
1. 문제 분석및 알고리듬 설계
문제해결 방법이 쉽게 생각나지 않습니다.
이러한 경우에는 문제를 단순하게 만들어서 해결하여 보면 좋은 방법이 생각나는 경우가 있습니다.
- 한 번에 최대 3계단을 오를 수 있는 사람이 있습니다.
- 1개의 계단을 올라가는 방법의 수는?
1가지
그냥 한 계단 올라갑니다. - 2개의 계단을 올라가는 방법의 수는?
2가지
(1,1) 또는 (2) ==>한계단 한계단 또는 2계단 - 3개의 계단을 올라가는 방법의 수는?
4가지.
(1,1,1), (1,2), (2,1), (3) - 4개의 계단을 올라가는 방법의 수는?
7가지.
(1,1,1,1), (1,1,2),(1,2,1),(1,3),(2,1,1),(2,2,),(3,1)
여기서 잠깐!
좋은 생각이 떠올랐습니다.

한 번에 최대 3계단을 오를 수 있는 사람이 5개의 계단을 오르기 위하여 계단 앞에 서 있다고 합시다.
능력은 3칸을 올라갈 수 있지만 계단이 1개 밖에 없는 경우부터 5개까지 생각합니다.
- 1개인 경우: 한 계단을 올라간다. (1가지 방법)
- 2개인 경우: 처음에 할 수 있는 행동은 1칸을 오르거나, 2칸을 오른다.
1칸을 오른 경우, 남은 1칸을 오른다. 결국 (1칸, 1칸), (2칸)으로 오르는 (2가지 방법)이다. - 3개인 경우: 처음에 할 수 있는 행동은 1칸, 2칸, 3칸을 오를 수 있다.
> 1칸을 오른 경우, 남은 2칸을 올라가는 방법은 이미 구하여 두었다. (2가지 방법)
> 2칸을 오른 경우, 남은 1칸을 올라가는 방법도 이미 구하여 두었다. (1가지 방법)
> 3칸을 오른 경우, 남은 0칸을 올라가는 방법도 이미 구하여 두었다. (1가지 방법)
위의 경우를 모두 더하면 4. 즉, 3개의 계단인 경우, 4가지 방법으로 올라갈 수 있다. - 4개인 경우: 처음에 할 수 있는 행동은 1칸, 2칸, 3칸을 오를 수 있다.
> 1칸을 오른 경우, 남은 3칸을 올라가는 방법은 이미 구하여 두었다. (4가지 방법)
> 2칸을 오른 경우, 남은 2칸을 올라가는 방법도 이미 구하여 두었다. (2가지 방법)
> 3칸을 오른 경우, 남은 1칸을 올라가는 방법도 이미 구하여 두었다. (1가지 방법)
위의 경우를 모두 더하면 7. 즉, 4개의 계단인 경우, 7가지 방법으로 올라갈 수 있다.
이러한 방법으로 5개의 계단까지를 구하면 다음 표와 같다.
계단의 수 | 0 | 1 | 2 | 3 | 4 | 5 |
방법의 수 | 1 | 2 | 4 | 7 | 13 |
- 원리를 찾자.
방법의 수는 이미 구하여 둔 왼쪽 3칸의 값을 더하면 된다(원리를 이해하세요)
피보나치수열은 왼쪽의 2개씩을 더한 경우이고, 지금은 3개씩을 더하면 된다. 원리는 같다.
이러한 유형의 문제를 n-nacci 문제라고 한다. 이 문제는 3-nacci 문제이다. - 0계단을 오르는 방법의 수는?
3계단을 오르는 방법은 4가지인데 이것은 왼쪽 3개를 더한 것과 같아야 한다.
그러므로 0계단을 오르는 방법은 1가지가 있다고 생각한다.
범위를 넓혀서 생각하면 음수 계단을 오르는 방법은 0가지이다. - 더 빠른 계산은 바로 왼쪽의 것을 2배하고 왼쪽 4번째 것을 빼면 된다.
예) (6째 계단)=(5째 계단)*2 - (2번째 계단) 즉, 24=13*2-2 원리는 스스로 생각하라
2. 코딩하기
한 번에 최대 3계단을 오를 수 있는 사람이 10개의 계단을 올라가는 방법은 몇가지인가 구하여 봅시다.
stair,power=10,3 # 계단 수, 한번에 오를 수 있는 계단 수
a=[0]*(stair+1) # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
a[:power]=1,1,2 # [1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0]
for i in range(power,stair+1): # 계단수를 늘려 나감
a[i]=sum(a[i-power:i]) # 왼쪽 3개의 합
print(a) # [1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274]
'''
10개의 계단을 오르는 방법은 274가지입니다.
6번 줄을 print(a[stair]) 로 바꾸면 확인할 수 있습니다.
2번 줄: 표 준비
3번 줄: 처음 3개의 계단 오르는 방법은 수작업으로 구함
4번 줄: 계단 수가 3개인 경우를 구하고, 다음 4개인 경우 등으로 확대
5번 줄: 구하려는 계단 왼쪽 3개를 더함
'''
그런데 만약,
한 번에 최대 5계단을 오를 수 있는 사람이 10개의 계단을 올라가는 방법은 몇가지인가를 구하려고 하면 처음 5개를 수작업으로 계산하여야 할까요?
너무 힘들겠지요? 계단 수가 음수인 경우 올라가는 방법이 0가지인 것을 사용하면 수작업을 하지 않아도 됩니다. 음수 계단 오르는 방법이 0가지인 것은 0계단 오르는 방법과 같은 원리로 생각하면 됩니다.
다음과 같이 코딩하면 많은 계단을 올라갈 수 있는 경우도 쉽게 구할 수 있습니다.
stair,power=10,5 # 10개의 계단을 한번에 최대 5계단
a=[0]*(stair+1)
a[0]=1 # 0계단 오르는 방법만 저장
for i in range(1,stair+1): # 한 계단부터
s=0 if i-power<0 else i-power # 음수이면 0, 그외는 i-power
a[i]=sum(a[s:i]) # s부터 i 계단 앞까지의 합
print(a)
'''
결과는 다음과 같습니다.
[1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464]
10개의 계단을 한번에 최대 5계단 올라갈 수 있는 사람은 464가지 방법으로
계단을 오를 수 있습니다.
5번 줄을 다음과 같이 코딩할 수도 있습니다.
s = (i-power,0)[(i-power)<0]
'''
※ 동적 계획법
동적 계획법(Dynamic programming, 다이나믹 법 )은 어떤 계획의 목표를 최적으로 달성하기 위해 문제를 여러 단계로 나누어 점차적으로 단계를 올려가면서 풀어가는 방법입니다. 즉, 각 단계에서의 최적화의 구조는 전체 최적화의 구조보다 간단하기 때문에 한 번에 문제를 푸는 대신 비교적 간단한 문제를 여러 회에 걸쳐 풀어 나감으로써 계획 전체를 작성해 가는 방법입니다. 하나의 최적해(optimization)를 구합니다.
위의 문제해결 전략이 동적 계획법입니다. 다양한 해결 전략은 다음에 공부합니다.
3. 계단 오르는 방법 출력하기
계단 오르는 방법 자체를 출력할 수 없을까?
다음은 한 번에 최대 3계단을 오를 수 있는 사람이 10개의 계단을 올라가는 모든 방법입니다.
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 2 1
:
:
3 3 1 3
3 3 2 1 1
3 3 2 2
3 3 3 1
위의 결과는 다음 프로그램에 의해서 출력된 것입니다.
def climbing(n,s=''):
if n<0:return
if n==0:
print(s)
return
for i in range(1,power+1):
climbing(n-i,s+' '+str(i))
stair,power=10,3
climbing(stair)
'''
다음에 공부할 재귀호출 전략(recursive call strategy)으로 작성하였습니다.
'''
코드는 한편의 시(poetry)입니다.
시인은 감성의 시를 쓰고, 우리는 이성(rationality)의 시를 씁니다.
수고하셨습니다.
안녕!