[알고리즘 with 파이썬] - DP(다이나믹 프로그래밍)

참고서적: 이것이 취업을 위한 코딩테스트다 with python - 나동빈

 

메모리 공간을 더 사용하여 연산 속도를 증가시킬 수 있는 방법. ex) 점화식을 이용해 풀기

2가지 방법(top down, bottom up)이 있다.

 

예시: 피보나치 함수

# 피보나치 함수를 재귀로 구현할때
def pibo(x):
    if x == 1 or x == 2: 
        return 1
    
    else:
        return pibo(x-1) + pibo(x-2)

print(pibo(4))

이렇게 단순 재귀로 작성하면 n이 커질 수록 시간복잡도가 기하급수적으로 늘어난다. O(2^N)

따라서 dp를 이용한다.

 

dp를 사용할 수 있는 경우:

1. 큰 문제를 작은 문제로 나눌 수 있다

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

 

탑 다운 방식은 큰 문제를 해결하기 위해 작은 문제를 호출하고, 바텀 업 방식은 단순히 반복문을 이용해 작은 문제부터 차근차근 답을 도출하는 경우를 의미한다.

 

※메모이제이션(탑다운): dp를 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미함. 캐싱(caching)이라고도 한다.

 

완전 탐색으로 접근했을 때 시간이 매우 오래 걸리면 문제가 DP 유형인것을 파악하기!

 

# 한 번 계산된 결과를 메모이제이션 하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수를 탑다운 dp로 프로그래밍
def pibo(x):
    # 0. 종료 조건(1 혹은 2일때 1을 반환)
    if x == 1 or x == 2:
        return 1
    
    # 1. 이미 계산 한 적이 있는 문제라면 그대로 반환
    if d[x] != 0:
        return d[x]
    
    # 2. 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[x] = pibo(x-1) + pibo(x-2)
    return d[x]

print(pibo(99))

시간 복잡도는 O(N)으로 줄어들게 된다.