동적 계획법(Dynamic Programming)

컴퓨터를 활용해도 해결하기 어려운 문제가 있다. 최적의 해를 구하기 위해 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제이다. 그렇기에 우리는 효율적인 알고리즘을 작성하기 위해 노력한다.
하지만 어떤 문제들 중에는 메모리 공간을 약간 사용함으로써 연산 속도를 비약적으로 증가시킬 수 있는 알고리즘들이 있는데 대표적으로 다이나믹 프로그래밍 기법으로 동적 계획법이라고도 한다.

1. 다이나믹 프로그래밍의 기본적인 아이디어
   다이나믹 프로그래밍의 기본적인 아이디어로 2가지가 있다. 바로 '탑다운'과 '바텀업' 방식이다. 특히 다이나믹 프로그래밍을 위해 '메모이제이션'이라는 기법도 자주 사용한다.
   다이나믹 프로그래밍과 동적 할당의 다이나믹은 다른 의미이다.

   다이나믹 프로그래밍을 사용하기 위해서는 조건이 필요하다.
   1) 큰 문제를 작은 문제로 나눌 수 있다.
   2) 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
   이런 조건을 만족하는 대표 문제로 피보나치 수열이 있다. 피노나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 수열이다.

   피보나치 수열 예시
   1 1 2 3 5 8 ...

   수학자들은 이런 수열의 항이 이어지는 형태를 점화식을 이용하여 간결하게 표현한다. 피노나치 수열의 점화식은 An = An-2 + An-1 로 표현할 수 있다.
   이런 수학적 점화식을 프로그래밍으로 표현하려면 재귀 함수를 사용하면 간단하게 표현할 수 있다.

# 피보나치 함수를 재귀 함수로 표현
def fibo(x):
	if x == 1 or x == 2:
    	return 1
    return fibo(x-1) + fibo(x-2)

print(fibo(4))

하지만 위와 같이 코드를 작성하게 되면 심각한 문제가 발생할 수 있다. f(n)함수에서 n이 지나치도록 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다. 위와 같은 겨우의 시간 복잡도는 O(N^2)에 해당한다. f(100)의 경우에는 2^100 번의 연산을 수행해야 하고 2진수 처리 방식을 가진 컴퓨터 구조에 기반한다면 우리의 수명이 끝날 때 까지 연산을 진행해도 답을 도출할 수 없게 된다.

그럼 이와 같은 피보나치 수열을 메모이제이션 기법을 사용하여 해결해보자. 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나로 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다. 이런 메모이제이션은 값을 저장하는 방법이므로 캐싱(cashing) 이라고도 한다. 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에서 가져오면 된다.

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

#피보나치 함수를 재귀 함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
	#종료 조건(1 혹은 2일 때 1을 반환)
    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(99))

정리
다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.

이와 같은 경우는 분할 정복 알고리즘과 유사한데 분할 정복 알고리즘과 다이나믹 프로그래밍의 차이점은 다이나믹 프로그래밍의 경우에는 나뉜 각 문제들이 서로 영향을 미치고 있다는 점이다. 일반적으로는 반복을 이용한 다이나믹 프로그래밍이 더 효율적이다. 피보나치 수열의 경우 다이나믹 프로그래밍을 사용하였을 시 시간복잡도가 O(N)이다.

재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을 큰 문제를 위해 작은 문제를 호출한다고 하여 탑다운(top-down)방식 이라고 말한다. 반면 단순 반복문을 이용하여 소스코드를 작성하는 경우는 작은 문제부터 차근차근 답을 도출한다고 하여 바텀업(bottom-up)방식 이라고 말한다. 위에서 작성한 피보나치 수열의 코드가 탑다운 방식이고 밑에 작성할 코드는 바텀업 방식이다.

#바텀업 방식의 피보나치 수열
d = [0] * 100

d[1] = 1
d[2] = 2
n = 99

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

print(d[n])

탑 다운 방식은 '하향식'이라고도 하며 바텀업 방식은 '상향식'이라고도 한다. 전형적인 다이나믹 프로그래밍의 형태는 바텀업 방식이다. 바텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다. 메모이 제이션은 때에 따라서 리스트가 아닌 다른 자료형을 사용하기도 한다. 예를 들면 사전(dict) 자료형이 있는데 이와 같은 경우는 수열처럼 연속적이지 않은 경우에 유용하다.

코딩 테스트에서의 다이나믹 프로그래밍은 대부분 간단한 형태로 출제가 된다. 문제를 푸는 첫 단계는 주어진 문제가 다이나믹 프로그래밍 유형임을 빠르게 파악하는 것이다. 특정한 문제를 완전 탐색 알고리즘으로 접근하였을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자.
일단 재귀 함수로 비효율적인 프로그램을 작성한 후에 탑다운 방식이면 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 방법이다.
또한 가능하다면 재귀적인 방식(탑다운) 방식보다는 바텀업 방식으로 문제를 해결하는것을 권장한다. 탑다운 방식으로 문제를 해결할때 시스템 상 재귀함수의 스택 크기가 한정되어 있을 수 있기 때문이다. 이런 경우 sys 라이브러리에 포함되어 있는 setrecursionlimit() 함수를 호출하여 재귀 제한을 완화할 수 있다.

실전 문제 1. 1로 만들기
정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다.
X가 5로 나누어 떨어지면 5로 나눈다.
X가 3으로 나누어 떨어지면 3으로 나눈다.
X가 2로 나누어 떨어지면 2로 나눈다.
X에서 1을 뺀다.
정수가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오
입력조건
첫째 줄에 정수 X가 주어진다.(1 <= X <= 30,000)
출력조건
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

solution

x = int(input())

d = [0]*30001

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:
    	min(d[i], d[i//5] + 1)
     
print(d[x])

실전 문제 2. 개미전사
문제설명
개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려 한다. 메뚜기 마을엔 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이 때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식랴창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 개미 전사를 위해 식량 창고 N개에 대한 정보가 주어질 때 얻을 수 있는 식량의 최댓값을 구하여라
입력조건
첫째 줄에 식량창고의 개수 N이 주어진다.(3 <= N <= 100)
둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다.(0 <= K <= 1,000)
출력조건
첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오

solution

n = int(input())

array = list(map(int, input().split()))

d = [0] * 100

d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, n):
	d[i] = max(d[i-1], d[i-2] + array[i])
   
print(d[n-1])

실전 문제 3. 바닥 공사
문제설명
가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다. 이 때 바닥을 채우는 모든 경우의 수를 구하여라.
입력조건
첫째 줄에 N이 주어진다.(1 <= N <= 1,000)
출력조건
첫째 줄에 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.

solution

import sys

N = int(input())
d = [0] * 1001

d[1] = 1
d[2] = 3

for i in range(3, N+1):
	d[i] = (d[i-1] + 2 * d[i-2]) % 796796
    
print(d[N])

실전문제 4. 효율적인 화폐 구성
문제설명
N가지 종류의 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록하려고 한다. 이 때 각 화폐는 몇 개라도 사용가능하며 사용한 화폐의 구성은 같지만 순서가 다른 것은 같은 경우로 구분한다.
입력조건
첫째 줄에 N, M이 주어진다.(1 <= N <= 100, 1 <= M <= 10,000)
이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10,000보다 작거나 같은 자연수이다.
출력조건
첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다.
불가능할 때는 -1을 출력한다.

solution

import sys

N, M = map(int, input().split())
currency = [int(input()) for _ in range(N)]
# DP 테이블
d = [10001] * (M+1)
d[0] = 0  # 0원일 경우

for c in range(len(currency)):
	for j in range(currency[c], M+1):
    	if d[j - currency[c]] != 10001:
        	# 화폐 단위마다 갱신
        	d[j] = min(d[j], d[j - currency[c]] + 1)
 
if d[M] == 10001:
 	print(-1)
else:
	print(d[M])

출처
이것이 취업을 위한 코딩 테스트다 with 파이썬
저자 나동빈

이 글은 위 서적을 바탕으로 학습하기 위해 작성되었습니다.