다이나믹 프로그래밍 with 파이썬

in Algorithm on Basics

1. 중복되는 연산을 줄이자

컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점에서 많은 제약을 발생시킨다. 그래서 우리는 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.
다만, 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 그것이 바로 다이나믹 프로그래밍 기법으로 동적 계획법이라고 표현하기도 한다. 다이나믹 프로그래밍은 2 가지 방식(탑다운, 보텀업)이 있다. 특히 다이나믹 프로그래밍을 위해 사용되는 메모이제이션 기법도 있다.

cf) 다이나믹 프로그래밍과 동적 할당의 다이나믹은 같은 의미인가?
프로그래밍에서 다이나믹은 프로그램이 실행되는 도중에 라는 의미이다. 예를 들어 자료구조에서 동적 할당은 프로그램 실행 중에 프로그램 실행에 필요한 메모리를 할당하는 기법이다. 하지만 다이나믹 프로그래밍에서는의 다이나믹은 이런 의미가 아니라는 것 정도만 기억하자.

2. 피보나치 수열

def fibo(x):
    if x==1 or x==2:
        return 1
    return fibo(x-1)+fibo(x-2)
print(fibo(4))

피보나치 수열은 위와 같이 간단하게 구현할 수 있다. 하지만 위 처럼 구현하게 되면 이미 한 번 계산한 내용을 호출할 때마다 계속 다시 계산해야 하는 문제가 생긴다. 따라서 엄청난 연산의 수가 발생하게 된다. O(2^n)의 지수 시간이 소요되며 2^10을 약 1000이라고 했을 때 연산 횟수는 1,000,000,000,000,000,000,000,000,000,000번이다. 따라서 매우 비효율적이라는 것을 알 수 있다.
이러한 문제는 다이나믹 프로그래밍을 사용하여 효율적으로 해결할 수 있다. 다이나믹 사용 조건은 다음과 같다.

  1. 큰 문제를 작은 문제로 나눌 수 있다.
  2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

피보나치 수열은 이러한 조건을 만족하는 대표적인 문제이다. 이 문제를 메모이제이션 기법을 사용해서 해결해보자. 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 메모이제이션은 값을 저장하는 방법으로 캐싱 이라고도 한다.

# 재귀적 구현
memo = [0]*100 # 메모이제이션하기 위한 리스트
def fibo(x):
    if x==1 or x==2:
        return 1
    if memo[x]!=0:        
        return memo[x]
    memo[x]= fibo(x-1)+fibo(x-2)
    return memo[x]

print(fibo(99))

다이나믹 프로그래밍을 적용했을 때의 피보나치 수열의 시간 복잡도는 O(N)이다. 왜냐하면 f(1)을 구한 다음 그 값이 f(2)를 푸는데 사용되고, f(2)값은 f(3)을 푸는 데 사용되는 방식으로 이어지기 때문이다.

정리하면 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 이다. 사실 큰 문제를 작은 문제로 나누는 것은 퀵 정렬에서도 소개했었다. 퀵 정렬은 정렬을 수행할 때 정렬할 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 한다. 이는 분할 정복 알고리즘으로 분류된다. 다이나믹 프로그래밍과 분할 정복의 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다.
퀵 정렬은 한 번 피벗이 자리를 잡게 되면 그 피벗의 위치는 더 이상 변화하지 않고 그 피벗값을 다시 처리하는 부분 문제는 존재하지 않는다. 반면에 다이나믹 프로그래밍은 한 번 해결했던 문제를 다시금 해결한다는 점이 특징이다. 그렇기 때문에 부분 문제에 대한 답을 저장해 놓고 이 문제는 이미 해결했던 것이니까 다시 해결할 필요가 없다고 저장값을 반환하는 것이다.

다이나믹 프로그래밍을 사용할 때는 웬만하면 재귀보다는 반복문을 사용하는 것이 좋다. 재귀 함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있다. 따라서 반복문을 사용하면 오버헤드를 줄일 수 있다. 일반적으로 반복문을 이용한 다이나믹 프로그래밍이 성능이 더 좋다는 것을 기억하자.

# 반복문으로 구현
memo = [0]*100
def fibo(x):
    memo[1]=memo[2]=1
    for i in range(3,x+1):
        memo[i]=memo[i-1]+memo[i-2]
    return memo[x]

print(fibo(4))


탑다운(메모이제이션)방식은 하향식이라고도 하며, 보텀업 방식은 상향식이라고도 한다. 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다. 보텀업 방식에서 사용되는 결과 저장용 리스트는 DP테이블 이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다. 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하고, 다이나믹 프로그래밍과는 별도의 개념이다. 한 번 계산된 결과를 어딘가에 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다는 것이다.
위에서 반복문으로 구현한 것이 보텀업 방식이고 재귀로 구현한 것이 탑다운 방식이다. 코드를 보면 왜 이렇게 부르는지도 쉽게 알 수 있을 것이다.

문제를 푸는 첫 번째 단계는 당연히 주어진 문제가 다이나믹 프로그래밍 유형인지 파악하는 것이다. 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자. 일단 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 것도 좋은 아이디어이다.
하지만 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것이 좋다. 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다.

3. 실전 문제

문제 : 1로 만들기

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같다.

  • X가 5로 나누어떨어지면 5로 나눈다.
  • X가 3으로 나누어떨어지면 3으로 나눈다.
  • X가 2로 나누어떨어지면 2로 나눈다.
  • X에서 1을 뺀다.

4개의 연산을 적절히 이용해서 X를 1로 만들려고한다. 연산을 사용하는 최소 횟수를 출력하시오.
입력 조건

  • 첫째 줄에 정수 X가 주어진다. (1<=x<=30,000)

출력 조건

  • 첫째 줄에 연산을 하는 횟수의 최솟값 출력
입력 예시
26

출력 예시
3

풀이

x = int(input())
DPtable = [0]*(x+1)

# 보텀업 방식
for i in range(2,x+1):
    # 1을 빼주는 경우 # 1을 더하는 이유는 연산횟수 측정
    # 이전의 연산 결과를 그대로 가져와 1을 빼는 연산횟수만 더해주는 식
    DPtable[i]=DPtable[i-1]+1
    # 2로 나누어떨어지는 경우 
    # 2를 나눈후의 연산결과를 그대로 가져오고 2를 나누는 연산횟수를 더해주는식
    # 1을 빼주는 경우와 비교했을 때 어느 것이 더 적은 연산을 수행하는지 min 이용
    if i%2==0:
        DPtable[i]=min(DPtable[i],DPtable[i//2]+1)
    # 1빼는경우와 2를 나누는 경우를 비교해서 작은 연산수가 dptable[i]에 들어있을 것임
    # 그럼 3과도 나누어떨어질때 연산결과를 비교를 한다.    
    if i%3==0:
        DPtable[i]=min(DPtable[i],DPtable[i//3]+1)
    if i%5==0:
        DPtable[i]=min(DPtable[i],DPtable[i//5]+1)

print(DPtable[x])


문제 : 개미 전사

개미 전사는 메뚜기 마을에 여러 개의 식량 창고를 공격하려고 한다. 식량창고는 일직선으로 이어져있고 정해진 수의 식량을 저장하고 있다. 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격당하면 알아챌 수 있다. 따라서 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 들키지 않는다. 예를 들어 {1,3,1,5}가 있다면 3과 5를 털어야 최대한 많은 식량을 얻을 수 있는 것이다.
입력 조건

  • 첫째 줄에 식량창고의 개수N이 주어진다. (3<=N<=100)
  • 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다(0<=K<=1,000)

출력 조건

  • 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오
입력 예시
4
1 3 1 5

출력 예시
8

풀이 : 내가 푼 풀이

2차 리뷰 코드로 수정

n = int(input())
store = list(map(int,input().split()))

dp=[0]*n
dp[0]=store[0]
dp[1] = max(store[0],store[1])
for i in range(2,n):
    dp[i]= max(dp[i-1],dp[i-2]+store[i])

print(dp[n-1])

모법 답안

n = int(input())
store = list(map(int,input().split()))
DPtable = [0]*(n) # 해당 인덱스까지 왔을때 최댓값을 저장하는 테이블
# 해당 인덱스까지의 최댓값을 저장하다보니 위에서와 같은 if문이 불필요해짐
DPtable[0]=store[0]
DPtable[1]=max(store[1],DPtable[0])

for i in range(2,n):
    DPtable[i] = max(DPtable[i-2]+store[i],DPtable[i-1])        

print(DPtable[n-1])

점화식만 판단할 수 있으면 매우 간단하다. 보텀업 방식으로 dptable에는 현재 인덱스까지의 식량 최대값을 저장하게 된다.


문제 : 바닥 공사

가로의 길이가 N, 세로의 길이가 2인 직사각형의 바닥이 있다. 이 바닥을 1 * 2의 덮개 2 * 1의 덮개, 2 * 2 의 덮개를 이용해 채우고자 한다. 이때 바닥을 채우는 모든 경우의 수를 구하시오.
입력 조건

  • 첫째 줄에는 N이 주어진다 (1<=N<=1,000)

출력 조건

  • 첫째 줄에 2 * N크기의 바닥을 채우는 방법의 수를 출력한다.
입력 예시
3
출력예시
5

풀이 : 내가 푼 풀이

2차 리뷰 코드로 수정, 중간을 보고 먼저 점화식 세우고 첫 부분만 따로 수정하는 방식

n = int(input())

dp = [0] * (n + 1)

dp[1] = 1
dp[2] = 3

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

print(dp[n])

풀이 : 모범 답안

n = int(input())

dptable = [0] * (n + 1)

dptable[1] = 1
for i in range(2, n + 1):
    if i == 2:
        dptable[i] = 3
    else:
        dptable[i] = dptable[i - 1] + dptable[i - 2] * 2

print(dptable[n])

점화식 설명
2 * 1, 1 * 2, 2 * 2의 타일에서 2 * 2가 최대이다. 왼쪽부터 차례대로 i만큼의 바닥을 덮개로 채운다고 생각해보자. 왼쪽부터 i-1까지 길이가 덮개로 이미 덮었다고 가정한 상태라면 i까지 채우는 경우는 2 * 1의 덮개를 채우는 1가지 경우이다. i-2까지 길이가 덮개가 이미 덮었다고 가정한 상태라면 i까지 채우느 경우는 1 * 2 덮개 2개로 채우는 경우와 2 * 2의 덮개로 채우는 경우일 것이다. 여기서 i-3부터는 생각할 필요가 없다. 왜냐하면 사용할 수 있는 덮개의 형태가 2 * 2가 최대이기 때문에 더이상 해봤자 덮개의 형태는 동일하기 때문이다. 따라서 i까지 덮개로 채우는 경우는 i-1까지 채웠을 때의 경우 + i-2까지 채웠을 때의 경우인데 i-2까지 채웠을때는 서로 다른 경우가 2가지이므로 *2가 필요한 것이다.
i-2의 경우에서 2 * 1의 덮개 2개로 채워서 총 3가지의 경우를 만들 수 있지 않느냐고 오해할 수 있지만 이 경우는 i-1까지 채웠을 때의 경우에 포함되어 있다.

문제 : 효율적인 화폐 구성

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.
입력 조건

  • 첫째 줄에 N,M (1<=N<=100 , 1<=M<=10,000)
  • 이후의 N개의 줄에는 각 화폐의 가치가 주어진다. 10,000보다 작거나 같은 자연수

출력 조건

  • 첫째 줄에 최소 화폐 개수 출력, 불가능할 경우 -1 출력
입력 예시
2 15
2
3
출력 예시
5

내가 작성한 코드

n, m = map(int, input().split())

INF = int(1e9)
units = []
dp = [INF] * (m + 1)
for i in range(n):
    units.append(int(input()))

for unit in units:
    dp[unit] = 1
    for i in range(1, m - unit + 1):
        if dp[i] != INF:
            dp[i + unit] = min(dp[i + unit], dp[i] + 1)

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

답안

# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
    array.append(int(input()))

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
        if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] + 1)

# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

보텀업 방식으로 처음부터 차례차례진행한다. 먼저 dptable을 모두 거스름이 불가능한 경우 10001로 저장하고, 0은 거스를 것이 없으므로 0으로 따로 저장한다. 따라서 dptable은 0인덱스를 제외하고는 10001로 채워진다.
핵심이 되는 min(dptable[i],dptable[i-pay]+1)를 살펴보자. 처음에는 dptable[i]에는 10001이 있을 것이다. dptable[i-pay]+1과 비교하는 이유는 금액 (i-pay)에서 pay를 더하면 금액 i 즉, d[i-pay]에 저장된 화폐 개수에다가 pay 화폐 1개를 더한 것과 기존에 dptable[i]에 있던 것(처음이라면 10001이 저장되어 있을 것이고 어느 정도 진행된 후라면 다른 pay값에 의해 화폐의 개수가 저장되어 있을 것 )과 비교하여 min을 통해 작은 것을 저장하기 위해서이다.
pay가 바뀌면서 과정이 반복되다보면 최종적으로 dptable에는 화폐의 최소 개수가 저장되게 된다.


© 2021. By Backtony