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

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

해결하기 어려운 문제

현실 세계에서 컴퓨터를 활용해도 해결하기 어려운 문제

• 최적의 해를 구하는데 매우 많은 시간이나 메모리 공간이 필요한 문제
  • 컴퓨터의 연산 속도의 한계, 메모리 공간의 한계

<aside> 💡 계산 복잡도 이론

해결하기 어려운 문제에 대해 깊게 다루는 분야. P → NP문제를 다룸

</aside>

• 효율적인 알고리즘의 설계와 분석 기법
  • 다이나믹 프로그래밍
    • 최적해에 도달하기 위해 일련의 선택이 이루어지는 최적화 문제에 적용
  • 그리디 알고리즘
  • 분할상환 분석 (amortized analysis)

다이나믹 프로그래밍이란?

• 큰 문제를 작은 문제로 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법
• 메모리 공간을 조금 더 활용해 연산 속도를 비약적으로 증가시키는 방법 중 하나
• 한국어로 동적 계획법이라고도 불림
• 분할 정복(Divide and Conquer) 알고리즘과의 차이점
  • 문제들이 서로에게 영향을 미치는지 여부
    • 영향을 미침 : DP
    • 영향이 없음 : 분할 정복

<aside> 💡 다이나믹 프로그래밍과 동적 할당의 다이나믹

프로그래밍에서의 다이나믹

• ’프로그램이 실행되는 도중에‘라는 의미

동적 할당

• 프로그램 실행 중에 프로그램 실행에 필요한 메모리를 할당하는 기법

다이나믹 프로그래밍

• DP의 ‘다이나믹’은 이러한 의미가 아니라는 것만 기억하자
• 프로그래밍 : 컴퓨터 코드를 쓰는 것을 의미하는 것이 아닌 테이블을 이용하는 방법을 말함 </aside>

일반적으로 최적화 문제에 적용

• 다양한 해를 가지나 그 중에 최적의 해를 찾는 문제

다이나믹 프로그래밍 사용 조건

1. 큰 문제를 작은 문제로 나눌 수 있다
   • 최적 부분 구조
     • 문제의 최적해가 그 안에 부분 문제의 최적해를 포함하는 문제의 구조
     • 최적 부분 구조를 갖는 문제는 DP나 그리디 적용할 수 있는 단서
       • DP와 그리디 차이
         • DP : 부분 문제들의 최적해를 먼저 구한 후 선택
         • 그리디 : 선택을 한 다음 그 결과로 얻어진 부분 문제만을 품
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다
   • 중복되는 부분 문제
     • 같은 문제를 반복해서 계산해야 함
       • 한 번만 계산해 테이블에 넣고 중복될 경우 상수 시간에 테이블 조회

메모이제이션(Memoization) 기법

• 다이나믹 프로그래밍을 구현하는 방법 중 한 종류
  • 다이나믹 프로그래밍과는 별도의 개념
• 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
• 값을 저장하는 방법이므로 **캐싱(Caching)**이라고도 함
• 구현 방법

단순히 한 번 구한 정보를 리스트에 저장

때에 따라 딕셔너리 자료형을 이용할 수도 있음

→ 수열처럼 연속적이지 않은 경우 유용

→ ex) an을 계산하고자 할 때, a0 ~ an-1 모두가 아닌 일부의 작은 문제에 대한 해답만 필요한 경우

같은 정보가 필요시 이미 구한 정답을 그대로 리스트에서 가져옴

다이나믹 프로그래밍 작성 방식

• 탑다운(Top-Down) 방식 (하향식)
  • 큰 문제를 해결하기 위해 작은 문제를 호출
  • 재귀 함수 사용
  • 메모이제이션 : 이전 결과 저장용 리스트
• 바텀업(Bottom-Up) 방식 (상향식)
  • 작은 문제부터 차근차근 답을 도출해 올라감
  • 반복문 사용
  • 다이나믹 프로그래밍의 전형적 방식
  • DP 테이블 : 결과 저장용 리스트

DP 알고리즘 개발 (풀이) 4단계

1. 최적해의 구조의 특징을 찾음
2. 최적해의 값을 재귀적으로 정의 (점화식을 세움)
3. 최적해의 값을 일반적으로 상향식(bottom-up) 방법으로 계산
4. 계산된 정보들로부터 최적해를 구성

코딩테스트와 다이나믹 프로그래밍

• 대체로 간단한 유형이 출제됨
• 주어진 문제가 DP 유형임을 빠르게 파악하는 것이 중요
  • 특정 문제를 완전 탐색으로 접근했을 때 시간이 매우 오래 걸리는 경우
  • 부분 문제들의 중복 여부 체크
• 일단 단순히 재귀를 이용해 비효율적인 프로그램을 작성한 뒤 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용할 수 있으면, 즉 메모이제이션을 적용할 수 있다면 코드를 수정해 개선해 나가는 방법도 좋음
• 가능하다면 탑다운 방식의 재귀보단 바텀업 방식으로 구현하는 것을 권장
  • 시스템상 재귀 함수의 스택 크기가 한정되어 있음
    • sys 라이브러리의 setrecursionlimit() 를 이용해 재귀 제한을 완화 가능하긴 함

피보나치 수열과 DP

기본적인 피보나치 재귀 함수 코드

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

print(fibo(6))

• 문제점

n이 커질수록 수행 시간이 기하급수적으로 늘어남

• 동일한 함수가 반복적으로 호출되어 비효율적임
• O(2^N) (정확히는 세타(1.618^N))

메모이제이션을 사용한 피보나치 함수 코드 (재귀)

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
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(99))	

바뀐 재귀 동작

• 이로써 시간복잡도가 O(N)이 됨
• 호출 순서
  • f(6) → f(5) → f(4) → f(3) → f(2) → f(1) → f(2) → f(3) → f(4)

DP테이블을 사용한 피보나치 함수 코드 (반복)

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수 반복문으로 구현 (바텀업 다이나믹 프로그래밍)
def fibo(n):
	for i in range(3, n + 1):
		d[i] = d[i - 1] + d[i - 2]

print(d[n])

문제 풀이

1로 만들기

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

1. x가 5로 나누어 떨어지면, 5로 나눔
2. x가 3으로 나누어 떨어지면, 3으로 나눔
3. x가 2로 나누어 떨어지면, 2로 나눔
4. x에서 1을 뺌

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

입력 조건

• 첫째 줄에 정수 X가 주어짐 (1 ≤ X ≤ 30,000)

출력 조건

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

입력 예시

26

출력 예시

3

코드

import sys
input = sys.stdin.readline

x = int(input())

# dp 테이블
d = [0] * (x + 1)

# 다이나믹 프로그래밍 진행 (바텀업)
for i in range(2, x + 1):
    # 현재 수에서 1을 빼는 경우
    d[i] = d[i - 1] + 1
    # 현재의 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    # 현재의 수가 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    # 현재의 수가 5로 나누어 떨어지는 경우
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[x])

문제 해결 방법

개미 전사

코드

import sys
input = sys.stdin.readline

'''
1. (i - 1)번째 식량창고를 털기로 결정한 경우 현재의 식량 창고를 털 수 없다
2. (i - 2)번째 식량창고를 털기로 결졍한 경우 현재의 식량 창고를 털 수 있다
'''

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

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

문제 해결 방법

바닥 공사

코드

import sys
input = sys.stdin.readline

'''
1. 왼쪽부터 i - 1까지 길이가 덮개로 이미 채워져 있으면 2 * 1 덮개를 하나 채우는 경우 존재
2. 왼쪽부터 i - 2까지 길이가 덮개로 이미 채워져 있으면 1 * 2 덮개 2개는 넣는 경우, 혹은 2 * 2 덮개 하나를 넣는 경우 2가지 존재
'''

n = int(input())

d = [0] * (n + 1)
d[1], d[2] = 1, 3

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

문제 해결 방법

효율적인 화폐 구성

코드

import sys
input = sys.stdin.readline

'''
ai = 금액i를 만들 수 있는 최소한의 화폐 개수
k = 화폐의 단위
ai-k = (i - k)를 만들 수 있는 최소한의 화폐 개수

- ai-k를 만드는 방법이 존재하는 경우 : ai = min(ai, ai-k + 1)
- ai-k를 만드는 방법이 존재하지 않는 경우 : ai = 10001
'''

n, m = map(int, input().split())
coins = []
for i in range(n):
    coins.append(int(input()))
coins.sort()

d = [10001] * (m + 1)
d[0] = 0

for k in coins:
    for i in range(k, m + 1):
        d[i] = min(d[i], d[i - k] + 1)
print(d[m]) if d[m] < 10001 else print(-1)

문제 해결 방법

금주의 문제

11053번: 가장 긴 증가하는 부분 수열