[알고리즘] DP 공부해보기

동적 계획법이라는 것에 대해 공부해보는 시간을 가졌습니다.

 

'완전탐색 < DP' 라고 합니다.

문제를 쪼개고, 작은 단위의 답을 구하고, 그걸 바탕으로 더 큰 문제의 답을 구하는 과정을 반복하는 방법입니다.

오늘은 맛보기로 DP의 대표작인 피보나치 수열에 대해 간단하게 알아보았습니다.

 

# recursive
def f(n):
    if n < 2:
        return n
    return f(n-1) + f(n-2)


# top - down
cache = [-1] * 37
def f2(n):
    if cache[n] != -1:
        return cache[n]

    cache[n] = n if n < 2 else f2(n-1) + f2(n-2)
    return cache[n]


# bottom - up
fibo = [-1] * 37
def f3(n):
    for i in range(37):
        fibo[i] = i if i < 2 else fibo[i-1] + fibo[i-2]
    return fibo[n]


print(f2(36))
print(f(36))
print(f3(36))

 

일단 이 코드 세개만 오늘은 외우는 것으로 마쳐보겠습니다. 

일단 외우고, 그 다음에 이해하는 방식으로 공부중이기 때문에, 일단 외워볼게요.