동적 계획법(다이나믹 프로그래밍) DP (feat. 계단오르기)

큰 문제를 작은 문제로 쪼개어 나가면서 문제를 해결하는 기법. 
DP에는 크게 두 가지 방법이 많이 사용되는데 Top Down 방식과 Bottom Up 방식이다.

 

Top Down : 큰 문제를 작은 문제로 쪼개어 나가면서 문제를 해결하는 방식으로 주로 재귀함수를 사용해 문제를 해결한다. 

구현은 쉽지만 재귀함수를 이용하다보니 느리다는 단점이 있다. 

 

Bottom Up : 점화식이라는 전체 알고리즘을 파악해 작은 문제로 큰 문제를 해결하는 방식.

점화식을 찾기가 쉽지 않아 구현이 어렵다. 하지만 점화식을 찾고나면 for문을 사용해 속도가 빠르다는 장점이 있다. 

 

대표적인 DP문제로는 피보나치 수열이 있다. 그 밖에도 배낭문제, LIS(Longest Increasing Subsequence)등이 있다. 

 

 

피보나치 수(백준 2747)

피보나치 수열은 보통 재귀로 풀었던 것 같은데 DP를 처음 공부할 때도 많이 사용되는 예제라고 한다. 

피보나치 수를 DP 방식으로 풀어보면서 DP가 뭔지 알아보자!!

 

Top-Down 구현하기

재귀로 푸는 방법. 

 

n=int(input())

def fibo(n):
    return fibo(n-1)+fibo(n-2)

print(fibo(n))

 

점화식 Fn=Fn-1+Fn-2에 대한 피보나치 수열을 구현했다. 종료조건이 없기 때문에 종료 조건이 없으면 재귀함수는 무한으로 반복한다. n값이 만약 음수라면 종료가 되지 않기 때문에 종료조건을 추가해 다시 코드를 구현해보겠다. 

 

def fibo(n):
    # 종료 조건 추가하기
    if n < 2:
        return n

    return fibo(n-1) + fibo(n-2)

 

메모이제이션(Memoization)

하지만 위와 같이 피보나치 수열을 구현하면 시간초과가 발생한다. 이를 방지하기 위해 메모이제이션이라는 dp에서 계산된 결과를 저장해두고 필요할 때 다시 사용해 중복 계산을 피하는 기법을 사용해야한다. 

 

예를 들어 피보나치 수열 10번쨰 숫자를 구한다고 했을 때, F(10)은 F(9)와 F(8)의 합계이다. F(9)를 구하기 위해서는 F(8)과 F(7)을 알아야 한다. F(10)을 계산할 때도 F(8)을 계산했고, F(9)를 계산할 때도 F(8)을 계산해야한다. 한 번 계산했으면 더이상 계산하지 않도록 방지해야한다!!

 

 

- 메모이제이션 사용해서 피보나치 수열 구현하기

n=int(input())

memo=[0]*(n+1)

def fibo(n):
    #종료조건
    if n<2:
        return n
    

    #메모이제이션 1 : 저장값 반환
    if memo[n]!=0:
        return memo[n]
    
    #memo[n]이 0이면
    #메모이제이션2 : 새로운 값 저장
    memo[n]=fibo(n-1)+fibo(n-2)
    return memo[n]

print(fibo(n))

 

memo 리스트를 0으로 모두 초기화하고 

memo[n]값을 확인해 0이 아니면 이미 계산을 한 값이기 떄문에 그대로 출력하고 함수를 종료한다. 

0일 경우에는 계산을 하고 그 값을 memo[n]에 저장한다. 

 

Bottom Up 구현

점화식을 사용한 코드

n = int(input())

def fibo(n):
    f = [0] * (n+1)
    f[0] = 0
    f[1] = 1
    for i in range(2, n+1):
        f[i] = f[i-1] + f[i-2]
    return f[n]

print(fibo(n))

 

f[0]과 f[1]은 0과 1로 미리 만들어주고 반복문처럼 계산하면 값을 구할 수 있다. 

 

 

백준 2579 계단 오르기

사실 이 문제를 풀다가 어떻게 풀어야할지 잘 모르겠어서 구글링하다 DP라는 개념을 알게되었다.

DP 풀이방법을 적용해서 풀어보았다. 

 

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

 

 

 

위와 같은 계단을 오르는데 규칙이 있다. 

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

 

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 구현해야한다. 

 

<입력>

n=int(input())
stairs=[0]*301

#0층은 0으로 두고 1층부터 넣어준다.
for i in range(1,n+1):
    stairs[i]=int(input())

 

계단의 개수와 계단 별 점수를 입력해준다. 

 

 

<1층,2층, 3층을 올라갔을 때 최대 점수 구해주기>

#계단이 300개 밖에 없으니까 0층 포함해서 301개 만들어주기
dp=[0]*301

#1층올라갔을 때 얻을 수 있는 최대 점수는 1층 값 뿐...
dp[1]=stairs[1] 

#2층 올라갔을 때 최대 점수를 얻으려면 무조건 1층도 거쳐야 함. 
dp[2]=stairs[1]+stairs[2]

#3층 올라갈 떄 점수 얻는 법 : 1칸+2칸 or 2칸+1칸 
#이 중 최대 점수로 기록하기
dp[3]=max(stairs[1]+stairs[3],stairs[2]+stairs[3])

 

<점화식 계산>

#4층부터 시작
#4층까지 최대 점수 얻는 법 : 1칸,2칸 1칸 or 2칸, 2칸
for i in range(4,n+1):
    dp[i]=max(dp[i-3]+stairs[i-1]+stairs[i],dp[i-2]+stairs[i])

 

 

<정답 코드>

#2579 계단오르기

n=int(input())
stairs=[0]*301

#0층은 0으로 두고 1층부터 넣어준다.
for i in range(1,n+1):
    stairs[i]=int(input())

dp=[0]*301
dp[1]=stairs[1] 
dp[2]=stairs[1]+stairs[2]
dp[3]=max(stairs[1]+stairs[3],stairs[2]+stairs[3])

for i in range(4,n+1):
    dp[i]=max(dp[i-3]+stairs[i-1]+stairs[i],dp[i-2]+stairs[i])

print(dp[n])

 

 

DP문제의 특징은 일단 DP로 풀 수 있는 문제인지 확인을 빨리 하는 것이 중요하다는 것.. 이 문제는 계속 전 단계의 결과를 필요로 했고 최적의 답을 구한다는 것에서 어느정도 눈치를 챘다. 문제는 ... 변수 간 관계식을 만드는 것이 어려웠다.. ㅠ 오히려 나는 Top-Down 방식보다 Bottom-Up 방식을 더 자주 사용할 거 같은 느낌이다.. 차라리 오래 생각하고 점화식 만드는게 쉬운 것 같다.. 더 문제 많이 풀어봐야지..!