Algorithm - 계단 오르기(동적 계획법)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[계단 오르기(동적계획법)]

 

철수는 계단을 오를 때, 한 번의 한 계단 또는 두 계단씩 올라간다.

만약, 총 4개의 계단을 올라간다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2로 5가지이다.

철수가 총 N개의 계단을 올라갈 때, 올라갈 수 있는 모든 방법의 수를 구하는 프로그램을 작성하시오.

 

 

 

*입력 설명

첫 번째 줄에 계단의 개수인 자연수 N(3 ≤ N ≤45)이 주어진다.

 

*출력 설명

첫 번째 줄에 올라가는 방법의 수를 출력한다.

 

 

---

 

 

풀이(Python)

답안(1) : Bottom-Up

import sys
sys.stdin = open('AA/input_74.txt', 'rt')

n = int(input())
dy = [0]*(n+1)

dy[1] = 1
dy[2] = 2

for i in range(3, n+1):
    dy[i] = dy[i-1] + dy[i-2]
    
print(dy[n])

# 출력 : 21

 

답안(2) : Top-Down(재귀함수 & 메모이제이션)

import sys
sys.stdin = open('AA/input_74.txt', 'rt')

def DFS(len):
    if dy[len] > 0:         # 메모이제이션(컷엣지)
        return dy[len]
    if len == 1 or len == 2:
        return len
    else:
        dy[len] = DFS(len-1) + DFS(len-2)
        return dy[len]

if __name__ == "__main__":
    n = int(input())
    dy = [0] * (n+1)
    print(DFS(n))
    
# 출력 : 21

 

input_74.txt(입력)

7

 

 

중요내용

1. 일반적으로 동적 계획법이라고 하면, 바텀업 방식을 의미하지만 큰 의미로 본다면 탑다운 방식도 동적 계획법으로 볼 수 있다.
2. 네트워크선 자르기 문제에서 설명한 것처럼 바텀업 방식은 점화식 ' f(n) = f(n-1) + f(n-2) '으로 문제에 접근하여 답을 도출한다.
3. 또한, 위와 동일하게 탑다운 방식은 재귀함수와 메모이제이션(컷엣지)을 사용하여 문제에 접근한 후 답을 도출한다.