이코테 | 다이나믹 프로그래밍
다이나믹 프로그래밍(Dynamic Programming)
: 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘
컴퓨터 프로그래밍에서 최적화 문제를 해결하는데 사용되며, 주로 중복되는 연산을 효율적으로 처리하여 실행 시간을 줄이는 데 활용됩니다. ex) 피보나치 수열
다이나믹 프로그래밍을 사용하기 위해 만족해야 할 조건
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
메모이제이션(Memoization) 기법 (= 캐싱 기법)
: 한 번 구한 결과를 메모리 공간에 메모해두고 다시 호출하면 그 결과를 그대로 가져오는 기법
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))
print(d)
탑다운 방식 (Top-Down)
: 큰 문제를 해결하기 위해 작은 문제를 호출하는 방법 (재귀 함수 이용)
보텀업 방식 (Bottom-Up)
: 작은 문제부터 차근차근 답을 도출하는 방법 (반복문 이용)
피보나치 수열, 최장 공통 부분 수열, 배낭 문제 등 다양한 최적화 문제를 해결하는 데 사용된다.
1로 만들기
정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.
a) X가 5로 나누어떨어지면, 5로 나눈다.
b) X가 3으로 나누어떨어지면, 3으로 나눈다.
c) X가 2로 나누어떨어지면, 2로 나눈다.
d) X에서 1을 뺀다.
연산 4가지를 적절히 사용해서 1을 만들려고 한다. 연산 사용 횟수의 최솟값을 출력하시오.
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
x = int(input())
d = [0]*30001
for i in range(2, x+1):
d[i] = d[i-1] + 1
if i%2==0:
print(d[i], d[i//2]+1)
d[i] = min(d[i], d[i//2]+1)
if i%3==0:
print(d[i], d[i//3]+1)
d[i] = min(d[i], d[i//3]+1)
if i%5==0:
print(d[i], d[i//5]+1)
d[i] = min(d[i], d[i//5]+1)
print(d[x])
처음엔 큰 수로 나누면 연산 사용 횟수가 적을 것이라고 생각이 들었지만,
-1을 한 후 나누는 경우도 무시할 수 없다고 판단했다.
다양한 방법들(큰 문제) 중에서 최솟값(작은 문제)를 호출하는 느낌....?이 맞을까?
최선의 방법이 무엇인지 알 수 없기 때문에 모든 계산을 해봐야 아는?
어떤 경우에 다이나믹 프로그래밍 방법으로 접근해야 하는지 어떤 식으로 코딩해야 할지 모르겠다.
점화식을 만들 수 있으면 쉬운데 점화식을 이끌어내는데 문제 이해력이 부족한 것 같다.
참고) d[1] : 1은 이미 1이기 때문에 연산 횟수가 0이다.
d[2] : 2가 1이 되기 위해 수행되는 최소 연산 횟수를 의미
2-1을 하면 1이 된다. (1회)
2/2를 하면 1이 된다. (1회)
둘 중 최소 연산 횟수는 1회로 d[1] = 1이다.
------------------------------------------------------------------------------------------------------
d[3] : 3이 1이 되기 위해 수행되는 최소 연산 횟수를 의미
3-1을 하면 2가 되고, 2에서 1이 되기 위해 수행되는 횟수는 d[2]에 저장되어 있다.
따라서 d[3]은 d[2] + 1로 2회이다.
3/3을 하면 1이 된다. (1회)
둘 중 최소 연산 횟수는 1회로 d[3] = 1이다.
------------------------------------------------------------------------------------------------------
d[4] : 4가 1이 되기 위해 수행되는 최소 연산 횟수를 의미
4-1을 하면 3이 되고, 3에서 1이 되기 위해 수행되는 횟수는 d[3]에 저장되어 있다.
따라서 d[4]는 d[3] + 1로 2회이다.
4/2를 하면 2가 되고, 2에서 1이 되기 위해 수행되는 횟수는 d[2]에 저장되어 있다.
따라서 d[4]는 d[2] + 1로 2회이다.
둘 중 최소 연산 횟수는 2회로 d[4] = 2이다.
------------------------------------------------------------------------------------------------------
d[5] : 5가 1이 되기 위해 수행되는 최소 연산 횟수를 의미
5-1을 하면 4가 되고, 4에서 1이 되기 위해 수행되는 횟수는 d[4]에 저장되어 있다.
따라서 d[5]는 d[4] + 1로 3회이다.
5/5를 하면 1이 된다. (1회)
둘 중 최소 연산 횟수는 1회로 d[5] = 1이다.
개미 전사
개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다.
개미 전사가 정찰병에게 들키지 않기 위해 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.
import sys
input = sys.stdin.readline
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-2] + array[i], d[i-1])
print(d[n-1])1, 3, 1, 5
d[i] : i번째 식량 창고까지 갔을 때 최대로 수확할 수 있는 식량
d[0]
0번째 식량창고만 약탈할 수 있기 때문에 array[0] 이다.
d[1]
1번째 식량창고까지 가기 위해서는
- 0번째 식량창고만 약탈하는 방법
- 1번째 식량창고만 약탈하는 방법
중 최댓값을 고르면 된다.
max(array[0], array[1])
d[2]
2번째 식량창고까지 가기 위해서는
- 0번째와 2번째 식량창고를 모두 약탈하는 방법
- 1번째 식량창고만 약탈하는 방법
중 최댓값을 고르면 된다.
max(d[1], d[0]+array[2])
d[3]
3번째 식량창고까지 가기 위해서는
- 0번째, 2번째 식량창고를 약탈하는 방법 = d[2]
- 1번째, 3번째 식량창고를 약탈하는 방법 = d[1] + array[3]
중 최댓값을 고르면 된다.
위 패턴을 통해 점화식은 d[i] = max(d[i-1], d[i-2]+array[i]) (단, 2<=i<n) 라고 할 수 있다.
바닥 공사
가로 길이 N, 세로 길이 2인 직사각형 형태의 얇은 바닥이 있다.
태일이는 이 얇은 바닥을 1*2의 덮개, 2*1의 덮개, 2*2의 덮개를 이용해 채우고자 한다.
이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.
import sys
input = sys.stdin.readline
n = int(input())
d = [0]*1001
d[0] = 1
d[1] = 3
for i in range(2, n):
d[i] = d[i-1] + 2*d[i-2]
print(d[n-1])
이번에는 시간도 덜 걸리고 그나마 빨리 풀었다.
n이 4일 때까지 하나하나 고려해봤을 때 d = [1, 3, 5, 11, ~] 이렇게 나왔다.
3 + 2*1 = 5
5 + 2*3 = 11
수의 규칙을 찾아서 점화식을 이끌어낼 수 있었다.
효율적인 화폐 구성
N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 한다.
각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것 같은 같은 경우로 구분한다.
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
array = []
d = [10001]*(m+1)
for _ in range(n):
array.append(int(input()))
d[0]=0
for i in range(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])
d = [10001]*(m+1)
: 최솟값을 구해야 하는 문제이므로 최대 범위인 10,000보다 큰 10,001로 초기화한다.
d[0]=0
: 0원일 때는 0이므로 초기화
for j in range(coin[i], m+1):
: 현재 동전 단위(입력한 동전 단위 순서대로 대입)부터 m원까지 반복
d[j]: 현재 금액을 만들기 위해 필요한 최소 동전 개수
d[j-coin[i]): 현재 금액에서 현재 동전 1개 값을 뺀 차액을 만들기 위해 필요한 최소 동전 개수
if d[j-coin[i]]!=10001:
: 현재 금액에서 현재 동전 1개 값을 뺀 차액을 만들기 위해 필요한 최소 동전 개수가 존재하는 경우
d[j] = min(d[j], d[j-coin[i]]+1)
: 둘 중 최솟값 선택
예시)
2 15
2
3
d[2-coin[0]] = d[0] - if문 성립 O
d[2] = min(d[2], d[0]+1) = 1
* d[0] + 1 : d[0]에 현재 동전(2원) 한 개를 더한 수
d[3-coin[0]] = d[1] - if문 성립 X
d[4-coin[0]] = d[2] - if문 성립 O
d[4] = min(d[4], d[2]+1) = 2
d[5-coin[0]] = d[3] - if문 성립 X
---------------- 중략 ----------------
d[3-coin[1]] = d[0] - if문 성립 O
d[3] = min(d[3], d[0]+1) = 1
d[4-coin[1]] = d[1] - if문 성립 X
d[5-coin[1]] = d[2] - if문 성립 O
d[5] = min(d[5], d[2]+1) = 2
d[6-coin[1]] = d[3] - if문 성립 O
d[6] = min(d[6], d[3]+1) = 2
d[7-coin[1]] = d[4] - if문 성립 O
d[7] = min(d[7], d[4]+1) = 4
---------------- 중략 ----------------