[알고리즘] 다이나믹 프로그래밍 예제
이것이 취업을 위한 코딩 테스트다. with 파이썬책을 참고하여 정리한 내용입니다.
📖 예제 1) 1로 만들기
정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.
- X가 5로 나누어떨어지면, 5로 나눈다.
- X가 3로 나누어떨어지면, 3로 나눈다.
- X가 2로 나누어떨어지면, 2로 나눈다.
- X에서 1을 뺀다.
정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들 때, 연산을 사용하는 횟수의 최솟값을 출력하시오.
ex) 26 일 경우
- 26 - 1 = 25
- 25 / 5 = 5
- 5 / 5 = 1
🗒️문제 해설
점화식으로 확인해보면 $a_i = min(a_{i-1}, a_{i/2}, a_{i/3}, a_{i/5}) + 1$ 이다.
🗒️답안 예시
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import sys
x = int(sys.stdin.readline())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 3001
# 다이나믹 프로그래밍(Dynamic Programming) 진행(바텀업)
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])
📖 예제 2) 개미 전사
식량창고는 일직선으로 이어져있고, 개미들은 식량창고를 약탈하려고 한다. 정찰병에게 들키지 않기 위해 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구해라.
✔️입력 조건
- 첫째 줄에 식량창고의 개수 N이 주어진다. (3 $\leq$ N $\leq$ 100)
- 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0 $\leq$ K $\leq$ 1,000)
✔️출력 조건
- 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오.
🗒️문제 해설
왼쪽부터 차례대로 식량창고를 턴다고 가정하면, i번 째 식량창고는 2가지 경우만 생각하면 된다.
- (i - 1)번째 식량 창고를 턴 경우 → 현재 식량창고를 털 수 없다.
- (i - 2)번째 식량 창고를 턴 경우 → 현재 식량창고를 털 수 있다.
따라서 i번째 식량창고에 있는 식량의 양이 $k_i$라고 했을 때 점화식은 다음과 같다.
\[a_i = max(a_{i-1}, a_{i-2} + k_i)\]여기서 알아둘 점은 i번째 식량창고에 대한 최적의 해를 구할 때 왼쪽부터 (i - 3)번째 이하의 식량 창고에 대한 최적의 해에 대해서는 고려할 필요가 없다는 점이다. d[i - 3]은 d[i - 1]과 d[i - 2]를 구하는 과정에서 이미 고려되었기 때문이다.
🗒️답안 예시
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sys
n = int(sys.stdin.readline())
array = list(map(int, sys.stdin.readline().split()))
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 다이나믹 프로그래밍(Dynamic Programming) 진행 (바텀업)
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 $\leq$ N $\leq$ 1,000)
✔️출력 조건
- 첫째 줄에 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.
🗒️문제 해설
다이나믹 프로그래밍 문제에서는 종종 결과를 어떤 수로 나눈 결과를 출력하라는 내용이 들어가는 경우가 많다. 이는 단지 결괏값이 굉장히 커질 수 있기 때문에 그런 것이다.
이 문제 역시 왼쪽부터 차례대로 바닥을 덮개로 채운다고 생각하면 점화식을 세울 수 있다.
- 왼쪽부터 (i - 1)까지 길이가 덮개로 이미 채워져 있으면 2 X 1의 덮개를 채우는 하나의 경우 밖에 존재하지 않는다.
- 왼쪽부터 (i - 2)까지 길이가 덮개로 이미 채워져 있으면 1 X 2 덮개 2개를 넣는 경우, 혹은 2 X 2 덮개 하나를 넣는 경우로 2가지 경우가 존재한다. 참고로 2 X 1 덮개 2개를 넣는 경우를 고려하지 않은 이유는
1에서 이미 고려되었기 때문이다.
또한 이 문제 역시 (i - 3)번째 이하의 위치에 대한 최적의 해에 대해서는 고려할 필요가 없다. 덮개 형태의 최대 크기가 2 X 2 이기 때문. 따라서 점화식은 다음과 같다.
\[a_i = a_{i-1} + a_{i-2} \times 2\]🗒️답안 예시
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import sys
n = int(sys.stdin.readline())
# DP 테이블 초기화
d = [0] * 1001
# 다이나믹 프로그래밍(Dynamic Programming) 바텀업
d[1] = 1
d[2] = 3
for i in range(3, n + 1):
d[i] = (d[i - 1] + d[i - 2] * 2) % 796796
print(d[n])
📖 예제 4) 효율적인 화폐 구성
N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.
✔️입력 조건
- 첫째 줄에 N, M이 주어진다. (1 $\leq$ N $\leq$ 100, 1 $\leq$ M $\leq$ 10,000)
- 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10,000보다 작거나 같은 자연수이다.
✔️출력 조건
- 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다.
- 불가능할 때는 -1을 출력한다.
입력 예시
2 15 2 3
출력 예시
5
🗒️문제 해설
적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾으면 된다. 금액 i를 만들 수 있는 최소한의 화폐 개수를 $a_i$, 화폐 단위를 $k$라고 했을 때, 다음과 같이 점화식을 작성할 수 있다. $a_{i-k}$는 금액 $(i - k)$를 만들 수 있는 최소한의 화폐 개수를 의미한다.
- $a_{i-k}$를 만드는 방법이 존재하는 경우, $a_i = min(a_i, a_{i-k} + 1)$
- $a_{i-k}$를 만드는 방법이 존재하지 않는 경우, $a_i = 10,001$
🗒️답안 예시
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import sys
n, m = map(int, sys.stdin.readline().split())
array = []
for _ in range(n):
array.append(int(sys.stdin.readline()))
# DP 테이블 초기화
d = [10001] * (m + 1)
# 다이나믹 프로그래밍(Dynamic Programming) 바텀업
d[0] = 0
for k in array:
for i in range(k, m+1):
if d[i - k] != 10001: # (i-k)원을 만드는 방법이 존재하는 경우 (사실 조건식이 없어도 min에서 걸러지므로 없어도 됨)
d[i] = min(d[i], d[i - k] + 1)
if d[m] == 10001:
print(-1)
else:
print(d[m])