그동안 BFS와 DFS 골드 문제들을 풀어보면서 알고리즘이 어떤 건지, 어떻게 활용하여 해결 할 수 있는지 감을 잡아갔습니다.

약 47일간 DFS와 BFS를 해결했으므로 하나만 계속해서 힘든 것도 있고 보다 다양한 알고리즘을 접하고자 오늘부터는 DP 알고리즘에 손대보려고 합니다.

DP란?

Dynamic Programming의 약자입니다.

def dp(N):
    if(N==1): return 1
    if(N==2): return 1
    return dp(N-1) + dp(N-2)
print(dp(10))

여기 피보나치 수열을 구하는 식이 있습니다.
이렇게 코딩을 작성하고 실행해보면

이러한 형식을 거쳐 재귀적으로 실행되겠죠.
그런데 위 실행 형식을 자세히 들여다보면

dp(8)도 두번 쓰이고

dp(7)도 두번 쓰이니 효율이 굉장히 떨어진다는 생각이 들지 않나요?
실제로 컴퓨터에서 위 코드 컴파일을 돌려보면

dp(10)같은 경우는 55로 잘 나오는데


dp(50)같은 경우는 때려죽여도 안나옵니다.

근데 이건 당연한 현상입니다. 위 코드대로 dp(50)을 구할 경우엔 1,000,000 초 = 약 277시간 후에나 컴파일 값이 나올 겁니다.

이렇게 쓸모없는 더미 자료들(위 예시에서의 dp(8),dp(7) 등)을 줄이고 시간복잡도를 2의 n승에서 O(n)으로 획기적이게 줄일 수 있는 알고리즘이 바로 DP의 메모이제이션입니다.

쉽게 설명하면 저 더미 자료들을 배열 하나 만들어서 저장하고, 만약에 현재 조사중인 N이 배열 안에 있는 자료라면 그대로 갖다 써먹는 방식입니다.

memo = [0] * 100
def dp(N):
    if(N==1): return 1
    if(N==2): return 1
    if(memo[N] != 0): return memo[N]
    memo[N] = dp(N-1) + dp(N-2)
    return memo[N]
print(dp(55))

이런 방식으로 배열 하나 만들어주고 메모가 비어있지 않으면 해당 메모로 return 해줍니다.
그리고 함수를 실행할 때마다 memo의 n번째
인덱스에 해당하는 값을 넣어줍니다.
위 식을 실행하면

이런씩으로 시간복잡도가 크게 줄어 금방 컴파일 값을 도출할 수 있습니다.

1003번 - 피보나치 함수

본격적으로 문제풀이를 해보겠습니다.
피보나치 수열에서 N을 호출할 때 0과 1이 각각 몇번 불러와지는지 횟수를 구하랍니다.

T = int(input())
for _ in range(T):
    zero = 0
    one = 0
    memo = [0]*41
    a = int(input())
    fib(a)

먼저 선언을 해주고 메모이제이션을 위한 memo의 길이는 n<41이므로 41로 설정하겠습니다.

    if a == 0:
        print(1,0)
    elif a == 1:
        print(0,1)
    elif a == 2:
        print(1,1)
    else:
        print(memo[a-1],memo[a])

DP는 점화식을 세워주는게 제일 중요한데 위와 같은 예외의 경우가 아니면 1과 0의 호출횟수를 메모이제이션을 통해 알아낼 수 있습니다.

def fib(N):
    if (N == 0): 
        return 0
    if (N == 1):
        return 1
    if (memo[N] != 0):
        return memo[N]
    memo[N] = fib(N-1) + fib(N-2)
    return memo[N]

메모이제이션을 사용하여 메모에 담겨있으면 return memo[N] 형식으로 return 해주고 메모에 담겨있지 않다면 memo[n]을 fib(n-1) + fib(n-2)로 지정해줍시다.