07 다이나믹 프로그래밍 (문제)
이것이 코딩 테스트다. with 파이썬 - 07 다이나믹 프로그래밍 문제
⭐ 문제는 나동빈님의 유튜브를 통해 확인해 주세요!!
유튜브에 있는 문제들만 풀이하여 이 블로그에 포스트 했습니다.
문제를 안적은 이유는 나동빈님의 유튜브에서 한 번 보시고 공부 해보시라고 문제는 따로 적지 않았습니다.
책에 있는 문제들은 이 블로그에는 없습니다.
개미 전사
n= 식량 갯수array= 모든 식량 정보d= 결과를 저장하기 위한 DP 테이블
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])
일단 조건으로는 다음과 같다.
- 식량창고는 일직선으로 이어여 있다.
- 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.
n만큼 식량 창고의 갯수를 정해주고 모든 식량 정보를 담을 수 있는 array를 만들어준다. array에는 개미들의 식량 정보만 입려되어 있다.
그리고 d라는 DP 테이블을 만들어준다.
식량창고는 일직성으로 이루어져 있으며 한 칸 이상 떨어진 식량창고를 약탈할 수 있는 조건을 이용하여 최적의 해를 계산할 수 있게 해준다.
또한 왼쪽부터 차례대로 식량창고를 턴다고 했을 때, 특정한 i번째 식량창고에 대해서 털지 안 털지의 여부를 결정하면 된다.
식으로는 다음과 같다.
a(i) = max(a(i-1), a(i-2) + k(i))
i는 인덱스이며 a(i)는 i번째 식량창고까지의 최적의 해, k(i)는 i번째 식량창고에 있는 식량의 양을 나타낸다.
i-2번째 까지만 계산하는 이유은 한 칸 이상 떨어진 식량창고는 털 수 있으므로 i-3는 고려할 필요가 없다.
1로 만들기
x= 정수 Xd= 결과를 저장하기 위한 DP 테이블
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:
d[i] = min(d[i], d[i // 5] + 1)
print(d[x])
연산을 사용하는 횟수의 최솟값을 출력해준다.
정수 X가 주어졌을 때, X에 사용할 수 있는 연산은 다음가 같이 4가지의 경우다.
- X가 5로 나누어 떨어지면, 5로 나눈다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- X에서 1을 뺀다.
a(i) = i를 1로 만들기 위한 최소 연산 횟수는 다음과 같다.
a(i) = min(a(i)-1, a(i/2), a(i/3), a(i/5))
1을 빼는 연산을 제외하고는 해당 수로 나누어떨어질 때에 한해 점화식을 적용할 수 있다.
이 연산식을 사용해서 if 조건문으로 차례대로 작성한다. 해당하는 조건에서 식이 이루어 지며 여러 조건이 겹쳐도 마지막 조건에서 처리해준 최소값이 적용된다.
효율적인 화폐 구성
n= 화폐의 종류m= 구해야 하는 화폐 합array=n개의 화폐 단위 정보dp= 결과를 저장하기 위한 DP 테이블
n, m = map(int, input().split())
array = []
for i in range(n):
array.append(int(input()))
dp = [10001] * (m + 1)
dp[0] = 0
for i in range(n):
for j in range(array[i], m + 1):
if d[j - array[i]] != 10001: # INF
d[j] = min(d[j], d[j - array[i]] + 1)
if d[m] == 10001:
print(-1)
else:
print(d[m])
문제의 조건으로는 다음과 같다.
- 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 해야 한다.
- 화폐 종류는 상관 없다.
- 사용할 수 있는 최소한의 화폐 개수를 구해야 한다.
점화식: 각 화폐 단위인 k를 하나씩 확인하며
a(i-k)를 만드는 방법이 존재하는 경우 a(i) = min(a(i), a(i-k) + 1) a(i-k)를 만드는 방법이 존재하지 않는 경우 a(i) = INF(무한)
a(i) = 금액 i를 만들 수 있는 최소한의 화폐 개수
k = 각 화페의 단위
INF = 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다는 의미를 가진다.
처음 실행을 하면 해당하는 인덱스에 INF를 설정해준다. 그리고 array에 길이만 만큼 반복을 시켜주는데 이번에는 화폐의 종류의 값에서부터 구해야하는 화폐까지 반복시켜준다.
값을 구하는 방법이 있다면 점화식을 사용하고 없다면 INF로 처리를 해준다.
최종적으로 계산된 결과를 출력할 경우 m원을 만드는 방법이 없다면 -1을 있으면 dp에 담긴 m인덱스만큼을 출력해준다.
금광
n= 광산의 열m= 광산의 행array= 금광 정보dp= 결과를 저장하기 위한 DP 테이블index= 시작 인덱스result= 결과
for tc in range(int(input())):
n, m = map(int, input().split())
array = list(map(int, input().split()))
dp = []
index = 0
for i in range(n):
dp.append(array[index:index + m])
index += m
for j in range(1, m):
for i in range(n):
if i == 0:
left_up = 0
else:
left_up = dp[i - 1][j - 1]
if i == n - 1:
left_down = 0
else:
left_down = dp[i + 1][j - 1]
left = dp[i][j - 1]
dp[i][j] = dp[i][j] + max(left_up, left_down, left)
result = 0
for i in range(n):
result = max(result, dp[i][m - 1])
print(result)
- 금광은 1 x 1 크키의 칸으로 나누어져 있다.
- 채굴자는 첫 번째 열부터 출발하여 금을 캔다.
- 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다.
- 이후 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동한다.
금광의 모든 위치에 대하여 다음의 세가지만 고려하면 된다.
- 왼쪽 위에서 오는 경우
- 왼쪽 아래에서 오는 경우
- 왼쪽에서 오는 경우
점화식은 다음과 같다.
dp[i][j] = array[i][j] + max(dp[i-1][j-1], dp[i][j-1], dp[i+1][i-1])
array[i][j] = i행 j열에 존재하는 금의 양
dp[i][j] = i행 j열까지의 최적의 해 ( 얻을 수 있는 금의 최댓값 )
이때 테이블에 접근할 때마다 리스트의 범위를 벗어나지 않는지 체크해야 한다.
편의상 초기 데이터를 담는 변수 array를 사용하지 않아도 된다. 바로 DP 테이블에 초기 데이터를 담아서 다이나믹 프로그래밍을 적용할 수 있다.
병사 배치하기
n= 병사의 수array= 병사의 정보dp= 결과를 저장하기 위한 DP 테이블
n = int(input())
array = list(map(int, input().split()))
array.reverse()
dp = [1] * n
for i in range(1, n):
for j in range(0, i):
if array[j] < array[i]:
dp[i] = max(dp[i], dp[j] + 1)
print(n - max(dp))
병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. (앞에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다)
본 문제는 가장 긴 감소하는 부분 수열을 찾는 문제로 치환할 수 있으므로, LIS 알고리즘을 조금 수정하여 적용함으로써 정답을 도출할 수 있다.
가장 긴 증가하는 부분 수열(LIS) 알고리즘을 사용할 수 있다.
dp[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이
점화식은 다음과 같습니다.
- 모든
0 ≤ i < i에 대하여,dp[i] = max(dp[i], D[j] + 1) if array[j] < array[i]
