최진실

Sejong Univ. DataScience woowacourse

4 분 소요

Coding Test 6

이코테 6

다이나믹 프로그래밍

1. 설명

  • 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
  • 이미 계산된 결과(작은 문제)를 별도의 메모리 영역에 저장
  • 탑다운 방식 / 보텀업 방식

2. 조건

  • 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있음 or 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음
  • 중복되는 문제: 동일한 작은 문제를 반복적으로 해결

메모제이션(탑다운)

  • 한번 계산한 결과를 메모리 공간에 메모
  • 하향식

보텀업

  • 정형적인 방법
  • 상향식

피보나치 수열

재귀

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

print(fibo(4))

실행결과: 3

다이나믹 프로그래밍(탑다운)

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))

실행결과: 218922995834555169026

다이나믹 프로그래밍(보텀업)

d = [0] * 100

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

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

print(d[n])

실행결과: 218922995834555169026

문제1-개미 전사

:grey_question: 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 각 식량 창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다.
이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다.
따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 얻을 수 있는 식량의 최댓값은?

입력예시
4
1 3 1 5

출력예시
8

1

아래 2가지 경우 중 더 많은 식량을 털 수 있는 경우를 선택

2

점화식

a[i] = i번째까지 얻을 수 있는 식량의 최댓값
k[i] = i번째 식량창고에 있는 식량의 양

a[i] = max(a[i-1], a[i-2]+k[i])

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])

문제2-1로 만들기

:grey_question: 정수 X가 주어졌을 때, 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.

  1. X가 5로 나누어 떨어지면, 5로 나누기
  2. X가 3으로 나누어 떨어지며나 3으로 나누기
  3. X가 2로 나누어 떨어지면, 2로 나누기
  4. X에서 1 빼기

X를 1로 만드는 연산의 최소 횟수는?

입력예시
26

출력예시
3

점화식

a[i] = i를 1로 만들기 위한 최소 연산 횟수

a[i] = min(a[i-1], a[i/2], a[i/3], a[i/5]) + 1

주의: 0이 아닌 1을 만드는 게 목적임

d[1] = 0
이미 1이므로 횟수 0임

d[2] = 1
1을 빼서 1로 만들어도 되고, 2로 나눠서 1로 만들어도 됨
min(d[1]+1=1, d[2//2]+1=1) = 1

d[3] = 1
d[2]+1 = 2
d[3//3]+1 = d[1]+1 = 1
min(d[2]+1=2, d[3//3]+1=1) = 1

d[4] = 2
d[3]+1 = 2
d[4//2]+1 = d[2]+1 = 2
min(d[3]+1=2, d[4//2]+1=2) = 2

d[5] = 1
d[4]+1 = 2
d[5//5]+1 = d[1]+1 = 1
min(d[4]+1=2, d[5//5]+1=1) = 1

d[6] = 2
d[5]+1 = 2
d[6//2]+1 = d[3]+1 = 2
min(d[5]+1=2, d[6//2]+1=2) = 2
d[6//3]+1 = d[2]+1 = 2
min(d[6//2]+1=2, d[6//3]+1=2) = 2

d[7] = 3
d[6]+1 = 3

d[8] = 3
d[7]+1 = 4
d[8//2]+1 = d[4]+1 = 3
min(d[7]+1=4, d[8//2]+1=3) = 3

이런 식으로 진행된다

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])

d[0:27] 출력결과
[0, 0, 1, 1, 2, 1, 2, 3, 3, 2, 2, 3, 3, 4, 4, 2, 3, 4, 3, 4, 3, 4, 4, 5, 4, 2, 3]

문제3-효율적인 화폐구성

:grey_question: N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 종류의 화폐는 몇 개라도 사용할 수 있다.
M원을 만들기 위한 최소한의 화폐 개수는? (불가능할 때는 -1 출력)

입력예시
2 15
2
3

출력예시
5

점화식

a[i] = 금액 i를 만들 수 있는 최소한의 화폐 개수
k = 각 화폐의 단위

a[i] = min(a[i], a[i-k]+1)

3

4

5

6

n, m = map(int, input().split())
array = [int(input()) for _ in range(n)]

d = [10001] * (m+1)

d[0] = 0
for i in rnage(n):
	for j in range(array[i], m+1):
		if d[j-array[i]] != 10001:
			d[j] = min(d[j], d[j-array[i]]+1)

if d[m] = 10001:
	print(-1)
else:
	print(d[m])

문제4-금광

:grey_question: n x m 크기의 금광이 있다. 각 칸은 특정한 크기의 금이 들어 있다.
채국자는 첫 번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다. 이후에 m-1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다.
채굴자가 얻을 수 있는 금의 최대 크기는?

입력예시
2
3 4
1 3 3 2 2 1 4 1 0 6 4 7
4 4
1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2

출력예시
19
16

점화식

array[i][j] = i행 j열에 존재하는 금의 양
dp[i][j] = i행 j열까지의 최적의 해

d[i][j] = array[i][j] + max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1])

7

T = int(input())
for _ in range(T):
	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):
			# i-1에서 올 때
			if i = 0:
				left_up = 0
			else:
				left_up = dp[i-1][j-1]
			# i+1에서 올 때
			if i = n:
				left_down = 0
			else:
				left_down = dp[i+1][j-1]
			# i에서 올 때
			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)

문제5-병사 배치하기

:grey_question: N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있다.
병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치하고자 한다.
배치 과정에서 특정한 위치에 있는 병사를 열외시키는 방법을 이용하면서 남아 있는 병사의 수가 최대가 되도록 한다. 열외시켜야 하는 병사의 최솟값은?

입력예시
7
15 11 4 8 5 2 4

출력예시
2

가장 긴 증가하는 부분 수열

점화식

D[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이

D[i] = max(D[i], D[j] + 1) if array[j] < array[i]

8

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))

카테고리:

업데이트:

댓글남기기

참고