[알고리즘][이코테] 다이나믹 프로그래밍(Dynamic Programming, DP)

정리내용은 [이것이 취업을 위한 코딩 테스트다 with 파이썬] 책을 기반으로 작성하였습니다.

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 교보문고

---

다이나믹 프로그래밍(Dynamic Programming, DP)

동적 계획법이라고도 표현한다.

큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말 / 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘

 

DP를 사용하는 이유
일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다. 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용 한다면 다시 반복계산할 필요가 없기 때문에 시간이 감소된다.

재귀함수를 예를 들어보면 아래 그림과 같이 동일한 함수가 반복적으로 실행되는 것을 볼 수 있다.

피보나치 수열 - 재귀로 풀을 경우: f(3)이 총 3번 반복해서 나타났다

피보나치수열 - DP로 풀 경우: 반복되는 연산을 하지 않게 된다.

DP의 조건

1. 큰문제를 작은 문제로 나눌 수 있다. (최적 부분 구조, Optimal Substructure)

2. 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일하다 (중복되는 부분 문제, Overlapping Subproblem)

 

DP 사용하기

1. DP로 풀 수 있는 문제인지 확인한다: 위의 DP의 조건이 맞는지 확인하기!
2. 문제의 변수 파악한다: DP는 현재 변수에 따라 그 결과 값을 찾고 그것을 전달하여 재사용하는 것을 거친다.  즉, 문제 내 변수의 개수를 알아내야 한다.
3. 변수 간 관계식 만들기(점화식)
4. 메모하기(memoization or tabulation): 변수 값에 따른 결과를 저장할 배열 등을 미리 만들고 그 결과를 나올 때마다 배열 내에 저장하고 그 저장된 값을 재사용하는 방식으로 문제를 해결해 나간다.
5. 기저 상태 파악하기: 가장 작은 문제의 상태를 알아야 한다. 
6. 구현하기

 

DP 구현 방법 

탑다운 방식(상향식): 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
보텀업 방식(=메모이제이션/하향식): 작은 문제부터 차근차근 답을 도출하는 방식

 

코드 구현 - 피보나치 수열(탑다운 방식)

d=[0]*100

def pibo(x):
    if x==1 or x==2:
        return 1
    if d[x]!=0:
        return d[x]

    d[x]=pibo(x-1)+pibo(x-2)
    return d[x]

print(pibo(6))

코드 구현 - 피보나치 수열(보텀업 방식)

d=[0]*100

def pibo(x):
    d[0]=0
    d[1]=1
    
    for i in range(2,x+1):
        d[i]=d[i-1]+d[i-2]
        
    return d[x]

print(pibo(6))