컴퓨터를 활용해도 해결하기 어려운 문제
💡 하지만 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있다.
➡️ 다이나믹 프로그래밍 (동적 계획법)
Q. 다이나믹 프로그래밍과 동적 할당의 다이나믹은 같은 의미일까?
A. 다름!!
프로그래밍에서의 다이나믹: "프로그램이 실행되는 도중에"
다이나믹 프로그래밍에서의 다이나믹 ➡️ 앞으로 알아보자!!
이번 장에서는 다이나믹 프로그래밍의 기본 아이디어와 2가지 방식(탑다운
&보텀업
)을 설명하고, 특히 다이나믹 프로그래밍을 위해 자주 사용되는 메모이제이션 기법
을 다룬다.
📌 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법
다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예로 피보나치 수열
이 있다.
프로그래밍에서는 수열을
배열
이나리스트
로 표현 가능!
배열과 리스트는 '연속된 많은 데이터'를 처리한다는 점이 동일!
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
🤔 피보나치 수열을 위와 같이 재귀함수로 구현하면 심각한 문제가 생길 수 있다.
➡️ f(n) 함수에서 n이 커질수록 반복해서 호출하는 수가 많아짐
➡️ 수행 시간 기하급수적으로 증가! O(2^N)
다이나믹 프로그래밍을 사용하면 효율적으로 해결 가능! 단, 다음의 조건을 만족할 때!
➡️ 피보나치 수열은 위의 조건을 만족!
메모이제이션(Memoization)
을 사용해서 해결해보자!
: 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
값을 저장하는 방법이므로캐싱(Caching)
이라고도 한다!
📌 메모이제이션 구현 방법: 한 번 구한 정보를 리스트에 저장!
# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100
# 피보나치 함수를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
# 종료 조건 (1 or 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))
앞서 수열은 배열이나 리스트로 표현할 수 있다고 했는데,
메모이제이션
은 때에 따라 다른 자료형(ex. 사전 자료형) 사용 가능!
📌 사전 자료형은 수열처럼 연속적이지 않은 경우에 유용!
(예를 들어 an을 계산하고자 할 때, a_0 ~ a(n-1) 전부가 아닌 일부에 대한 답만 필요할 경우)
🤔 재귀 함수로 구현하면 오버헤드가 발생할 수 있다.
➡️ 반복문
을 이용한 다이나믹 프로그래밍이 더 성능이 좋다!
O(N)
# 호출하는 함수 확인
d = [0] * 100
def pibo(x):
print('f(' + str(x) + ')', end=' ')
if x == 1 or x == 2:
return 1
if d[x] != 0:
return d[x]
d[x] = pibo(x - 1) + pibo(x - 2)
return d[x]
pibo(6)
# f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 2
n = 99
# 피보나치 함수 반복문으로 구현 (보텀업 DP)
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]
print(d[n])
큰 문제를 작게 나누는 건 퀵 정렬에서도 나왔는데, 퀵 정렬은 분할 정복(Divide and Conquer)
알고리즘으로 분류된다.
분할 정복: 정렬할 리스트를 분할하여 전체적으로 정렬될 수 있도록 하는 알고리즘
다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다!
퀵 정렬은 한 번 피벗이 자리를 변경하면 피벗의 위치는 더 이상 바뀌지 않고, 그 피벗 값을 다시 처리하는 부분 문제는 존재하지 않는다.
탑다운(하향식)
: 큰 문제를 해결하기 위해 작은 문제 호출
보텀업(상향식)
: 작은 문제부터 차근차근 답 도출
DP 테이블
: 보텀업 방식에서 사용되는 결과 저장용 리스트당연하지만 주어진 문제가 DP 유형임을 파악해야 한다!
비효율적인 재귀 함수(탑다운)으로 작성한 뒤, 메모이제이션
을 적용할 수 있는지 확인(작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있는지)
📌 가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업
방식으로 구현하는 것을 권장한다!
recursion depth(재귀 함수 깊이)
에러 발생 가능recursion depth 에러가 발생할 때,
sys 라이브러리
에 포함되어 있는setrecursionlibit()
함수를 호출하면 재귀 제한을 완화시킬 수 있다.
난이도: 🌕🌗
풀이시간: 20분
시간제한: 1초
메모리제한: 128MB
정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.
정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 구하시오.
입력 조건
출력 조건
# 입력 예시
26
# 출력 예시
3
예시에 대한 설명)
<해설>
이 문제는 같은 함수들이 동일하게 여러 번 호출된다.
➡️ 동일한 함수에서 구하는 값들은 동일해야 하므로 다이나믹 프로그래밍이 효과적!
📌 보텀업 다이나믹 프로그래밍으로 구현해보자!
# 정수 X 입력받기
x = int(input())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 30001
# 다이나믹 프로그래밍 진행 (보텀업)
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 // 2] + 1)
# 현재의 수가 5로 나누어 떨어지는 경우
if i % 5 == 0:
d[i] = min(d[i], d[i // 5] + 1)
print(d[x])
난이도: 🌕🌕
풀이시간: 30분
시간제한: 1초
메모리제한: 128MB
메뚜기 마을에는 여러 개의 식량창고가 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기는 일직선상에 존재하는 식량창고 중 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 들키지 않고 약탈하기 위해선 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.
개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.
입력 조건
출력 조건
# 입력 예시
4
1 3 1 5 # 두 번째와 네 번째 식량창고 선택했을 때 최댓값인 8
# 출력 예시
8
<해설>
i번째 식량창고에 대해서 털지 안 털지의 여부를 결정할 때, 2가지 경우만 확인하면 된다.
➡️ 1, 2번 중에서 더 많은 식량을 털 수 있는 경우를 택하면 된다.
(i - 3)번째 이하의 식량창고에 대한 최적의 해에 대해서는 고려할 필요가 없다. d[i - 3]은 d[i - 1]과 d[i - 2]를 구하는 과정에서 이미 계산되었기 때문이다.
📌 i번째 식량창고에 있는 식량의 양이 k_i라고 했을 때 점화식은 아래와 같다.
# 정수 N 입력받기
n = int(input())
# 모든 식량 정보 입력받기
array = list(map(int, input().split()))
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
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])
난이도: 🌕🌗
풀이시간: 20분
시간제한: 1초
메모리제한: 128MB
가로의 길이 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 이 얇은 바닥을 1x2 덮개, 2x1 덮개, 2x2 덮개를 이용해 채우고자 한다.
이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.
입력 조건
출력 조건
# 입력 예시
3
# 출력 예시
5
<해설>
타일링
문제 유형 (다이나믹 프로그래밍의 기초 예제)
왼쪽부터 i-1까지 길이가 덮개로 이미 채워져 있으면 2x1 덮개를 채우는 하나의 경우만 존재
왼쪽부터 i-2까지 길이가 덮개로 이미 채워져 있으면 2가지 경우
a. 1x2 덮개 2개
b. 2x2 덮개 1개
2x1 덮개 2개를 넣는 경우는
1
에서 이미 고려되었기 때문에 제외
위에 풀었던 문제와 마찬가지로 왼쪽부터 (i-3)번째 이하의 위치에 대한 최적의 해에 대해서는 고려할 필요가 없다.
➡️ 사용할 수 있는 덮개의 형태가 최대 2x2 크기의 직사각형 형태이기 때문!
점화식
# 정수 N 입력받기
n = int(input())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
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])
난이도: 🌕🌕
풀이시간: 30분
시간제한: 1초
메모리제한: 128MB
N가지 종류의 화폐가 있을 때, 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.
입력 조건
출력 조건
# 입력 예시 1
2 15
2
3
# 출력 예시 1
5 # 3원 5개 사용
# 입력 예시 2
3 4
3
5
7
# 출력 예시 2
-1
<해설>
그리디에서 다뤘던 거스름돈 문제와 거의 동일하다!
# 정수 N, M 입력받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력받기
array = []
for i in range(n):
array.append(int(input()))
# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)
# 다이나믹 프로그래밍 진행 (보텀업)
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])