개요

길이가 n인 계단이 있다. 해당 계단은 한번에 1 또는 2걸음으로 전진할 수 있다. n개의 계단을 갈 수 있는 총 개수를 구해야 한다.

이해한 부분

길이가 1인 계단은 1걸음으로 전부 올라갈 수 있으므로 1가지 방법밖에 없다.

그리고 길이가 2인 계단은 1걸음으로 2번, 2걸음으로 1번 올라갈 수 있으므로 2가지 방법이 있다.

즉 식으로 표현하면 아래와 같다.

result(1) = 1 // [1]
result(2) = 2 // [1, 1] [2]

해결 전략

해당 문제는 수열 처럼 문제를 나눌 수 있다. 길이가 1과 2는 나눌 수 없지만, 3부터는 달라진다.

3은 첫번째로 올라간 걸음의 종류에 따라 2가지로 나뉘게 된다.

3의 경우의 수 = (1 걸음 + 2계단의 경우의 수) + (2걸음 + 1계단의 경우의 수)

이를 식으로 표현하면 아래와 같다.

result(3) = result(2) + result(1)

4의 경우도 아래와 같이 문제를 분리할 수 있다. 첫 번째로 갈 수 있는 걸음은 1또는 2이므로 3의 경우와 마찬가지로 아래와 같이 표현된다.

result(4) = (1 + result(3)) + (2 + result(2))

현재 확정된 경우의 수는 result(1)과 result(2)밖에 없어서 result(3)도 나뉘게 되지만, 이미 구한 내용을 임시로 저장하게 되면 두번 계산할 필요 없이 바로 계산할 수 있게 된다. 이를 Memoization라고 한다. 즉, cache라는 임시 저장소를 만든다면 여러번 계산할 필요 없이 이미 계산한 내용을 갖다 쓸 수 있다.

즉, 코드는 아래와 같이 구성될 수 있다.

cache = {1:1, 2:2}  # 이미 계산한 초기 값

if n not in cache.keys():
    for step in range(3, n + 1): # include n
        cache[step] = cache[step - 1] + cache[step - 2] # 한번에 올라갈 수 있는 2가지 방법을 더한다.
return cache[n]

#coding-interview #dynamic-programming

개요

이해한 부분

해결 전략

Comments