파이썬 다이나믹 프로그래밍 잘하는법

알고리즘 공부를 시작했을 때, 이름만 보고 거부감이 들기 쉬운 다이나믹 프로그래밍을 잘하는 방법을 소개합니다. 저는 코딩 테스트를 준비할 때 따로 학원에 다니지 않아서, 주변에서 '다이나믹 프로그래밍 문제 짜증이 나'라는 얘기를 들으면 약간 불안했습니다. 왜냐하면 이름만 듣고 주눅 들었기 때문이죠. '다이나믹 프로그래밍은 다이나믹한 기술을 사용하나? 어렵다고 하니까 정말 어렵나 보다.' 생각했습니다. 하지만 다이나믹 프로그래밍의 정의를 알고, 문제를 여러 개 풀어보니 다이나믹 프로그래밍은 수학 점화식을 찾아가는 과정이라고 결론 내렸습니다. 모든 알고리즘 문제가 그렇듯 특정 유형의 문제를 여러 개 풀어보니 dp가 두렵지 않았습니다. 아래 저의 solved.ac 결과를 보면 아시겠지만, 저는 dp, graph, 구현 문제에 나름 강한 편입니다. 상대적으로 string, greedy를 사용하는 알고리즘에 약한 건 사실입니다. 이제 다이나믹 프로그래밍의 정의와 예제를 살펴보겠습니다. 

solved.ac

다이나믹 프로그래밍 뜻

다이나믹 프로그래밍의 다이나믹은 '프로그램이 실행되는 도중에'라는 의미입니다. 같은 의미로 사용된 단어를 보자면, 동적 할당(dynamic allocation)이 있는데요, 실행에 필요한 메모리를 프로그램이 실행되는 도중에 할당하는 기법을 말합니다. 다이나믹 프로그래밍의 의미는 메모리를 사용해서 연산 속도를 증가시키는 방법을 말합니다. 

 

메모이제이션 기법

다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메로리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미합니다. 

 

파이썬 다이나믹 프로그래밍을 위한 입출력

c언어에서는 array를 만들어서 메모이제이션을 했는데, 파이썬에서도 다이나믹 프로그래밍하려면 리스트를 입력받고, 초기화하고, 출력하는 방법을 꼭 알고 있어야 합니다. n, m은 map을 이용해서 입력받고, 엔터로 구분되는 리스트는 append를 통해서 입력받으면 됩니다. 

#정수 N,M을 입력받기
n, m = map(int, input().split())
#메모이제이션 dp 테이블 초기화
dp=[10001]*(m+1)
arr=[]
for i in range(n):
    arr.append(int(input()))
    
#입력 
#3 4
#3
#5
#7

 

피보나치 함수 구현

아래 코드는 탑다운 방식을 활용한 피보나치 함수 구현 코드입니다. 탑다운 방식을 활용하는 것의 장점은 점화식을 구했다면, 점화식 그대로를 사용할 수 있다는 장점이 있습니다. 

#메모이제이션을 위한 리스트 초기화
d= [0]*100

#피보나치 함수 재귀함수 구현 (탑다운)
def fibo(x):
    if x==1 or x==2:
        return 1
    #이미 계산했다면
    if d[x] !=0:
        return d[x]
    #계산하지 않았다면
    d[x]=fibo(x-1)+fibo(x-2)
    return d[x]

print(fibo(10))

 

보텀업 bottom up 기법으로 푼 피보나치 함수 

#피보나치 수열 for문 사용
d=[0]*100

#첫 번째 피보나치 수와 두 번째 피보나치 수 초기화
d[1]=1
d[2]=1

#bottom up 방식으로 문제 풀기
for i in range(3, 100):
    d[i]=d[i-1]+d[i-2]

print(d[99])
#출력 218922995834555169026

시스템에서 스택 크기의 제한이 있을 수 있기 때문에, 문제를 풀 때 재귀 함수를 사용하는 탑 다운 방식 보다 for문을 사용하는 보텀업 방식으로 구현하는 것이 좋습니다. 

 

1로 만들기 bottom up 방식 풀이 

문제 설명: 정수 x가 주어질 때 정수 x에 사용할 수 있는 연산은 다음과 같이 4가지다. 

1. x가 5로 나누어떨어지면, 5로 나눈다. 

2. x가 3으로 나누어떨어지면, 3으로 나눈다.

3. x가 2로 나누어떨어지면, 2로 나눈다.

4. x에서 1을 뺀다. 

정수 x가 주어졌을 때, 연산 4개를 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 

#1로 만들기 다이나믹 프로그래밍 문제
d=[0]*30001

x =int(input())

#my solve
for i in range (2, x+1):
    tem=100000
    if i % 5 ==0:
        if d[i//5] +1 <= tem:
            tem=d[i//5]+1
    if i % 3 ==0:
        if d[i//3] +1 <= tem:
            tem = d[i//3]+1
    if i%2 ==0:
        if d[i//2]+1 <=tem:
            tem = d[i//2]+1
    if d[i-1]+1 <=tem:
        tem = d[i-1]+1
    d[i]=tem

#book solve
for i in range(2, x+1):
    d[i]=d[i-1] +1
    if i%2 ==0:
        d[i] = min(d[i], d[i//2]+1)
    if i%3 ==0:
        d[i] = min(d[i], d[i//3]+1)
    if i%5 ==0:
        d[i] = min(d[i], d[i//5]+1)

print(d[x])

제가 문제 풀 때 min 함수를 잘 몰라서 임시 값을 받을 수 있는 tem 변수를 추가하여 문제를 풀었습니다. 책에서는 min 함수를 이용하여 깔끔하게 풀었고, if 조건문 위치도 효율적으로 배치했습니다. 

 

개미 전사 풀이

#첫째 줄에 식량창고의 개수 N이 주어진다(3<=N <=100)
n = int(input())
#둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 k가 주어진다.
# 0<=K <= 1,000
arr = list(map(int, input().split(' ')))

#dp 메모이제이션을 위한 테이블 생성
d=[0]*100

#dp 테이블 초기화
d[0]=arr[0]
d[1]=max(arr[0],arr[1])

#bottom up dp 테이블 채우기
for i in range(2, n):
    d[i]=max(d[i-1], d[i-2]+arr[i])

print(d[n-1])
#입력 
#5
#2 1 3 1 5
#출력 10

 

바닥공사 풀이

#정수 N을 입력받기 
n=int(input())
dp=[0]*1001

dp[1]=1
dp[2]=3
for i in range(3,n+1):
    dp[i]=(dp[i-2]*2 +dp[i-1]) % 796796

print(dp[n])
#입력 3, 출력 5

효율적인 화폐 구성 풀이

#정수 N,M을 입력받기
n, m = map(int, input().split(' '))
#메모이제이션 dp 테이블 초기화
dp=[10001]*(m+1)
# N개의 화폐 단위 정보를 입력받기
arr=[]
for i in range(n):
    arr.append(int(input()))

dp[0]=0
for i in arr:
    dp[i]=1

#my solve
for i in range(1, m+1):
    for j in arr:
        if i - j > 0:
            if dp[i] > dp[i-j]+1:
                dp[i]=dp[i-j]+1

#book solve
for i in range(n):
    for j in range(arr[i],m+1):
        if dp[j - arr[i]] != 10001: #(i-k)원을 만드는 방법이 존재하는 경우
            dp[j]=min(dp[j], dp[j-arr[i]]+1)

if dp[m]==10001:
    print(-1)
else:
    print(dp[m])

 

다이나믹 프로그래밍 예제

https://www.acmicpc.net/problemset?sort=ac_desc&algo=25 

문제 - 1 페이지

백준 사이트 > 문제> 알고리즘 분류 > 다이나믹 프로그래밍에서 더욱 많은 문제를 풀 수 있습니다. 

 

마무리

다이나믹 프로그래밍의 핵심은 문제를 보고 다이나믹 프로그래밍이라고 판단하는 것과 점화식을 빠르게 잘 찾는 것입니다. 이름을 보고 겁먹지 말고, 차근차근 쉬운 문제부터 풀다 보면 언젠가는 익숙해집니다.