다이나믹 프로그래밍(DP)

다이나믹 프로그래밍

다이나믹 프로그래밍의 가장 큰 특징은 메모리를 적절히 사용해 수행 시간을 비약적으로 증가시키는 방법이다. 메모리가 완전 탐색에 비해 더 많이 필요할 수 있지만 메모리를 조금 더 사용함으로써 수행 시간을 비약적으로 증가시킨다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장해 다시 계산하지 않도록 하며 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운, 버텀업)으로 구성된다. 

다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있다. 

 

1.  최적 부분 구조
   1. 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. ex) 피보나치 수열
2. 중복되는 부분 문제
   1. 동일한 작은 문제를 반복적으로 해결해야 한다. ex) f(2)의 반복적인 호출

 

• 메모이제이션(Memoization)
  • 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나이다.
  • 한번 계산한 결과를 메모리 공간에 메모하는 기법이다
    • 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다
    • 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다.
  • 탑다운(메모이제이션) 방식은 하향식이라고도 하며 버텀업 방식은 상향식이라고도 한다.
  • 다이나믹 프로그래밍의 전형적인 형태는 버텀업 방식이다.
    • 결과 저장용 리스트는 DP 테이블이라고 부른다.
  • 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미한다. 따라서 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아니며, 한 번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다.

## 피보나치 수열 

# 탑다운 다이나믹 프로그래밍 소스코드

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
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))

2189229958345551690263


# 버텀업 다이나믹 프로그래밍 소스코드

d = [0] * 100

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

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

2189229958345551690263

 

그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토해보고 다른 알고리즘을 이용한 풀이 방법이 떠오르지 않는다면 다이나믹 프로그래밍을 고려해야한다. 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성하고작은 문제에서 구한 답인 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법으로 다이나믹 프로그래밍 알고리즘을 사용해 문제를 해결할 수 있다.

---

 

• <개미 전사>
• 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다.
• 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다.
• 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.
• 예를 들어 식량창고 4개가 [1, 3, 1, 5] 이렇게 존재한다고 가정하면 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택햇을 때 최댓값인 8개의 식량을 빼앗을 수 있다. 개미 전사는 식량창고가 이렇게 일직선상일 때 최대한 만ㅅㅎ은 식량을 얻기를 원한다.
• 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하라.
  • 첫째 줄에 식량창고의 개수 N이 주어진다 (3<= N <=100)
  • 둘째 줄에 공백을 기준으로 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0<= K <= 1,000)
  • 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하라

왼쪽부터 차례대로 식량창고를 턴다고 했을 때, 특정한 i번째 식량창고에 대해서 털지 안 털지의 여부를 결정하면, 2가지 경우 중에서 더 많은 식량을 털 수 있는 경우를 선택하면 된다.

i-1을 털 수 있으면 i를 털 수 없음 //  i-2를 털 수 있으면 i를 털 수 있음

 

이를 점화식으로 나타내보면 a(i) = max(a(i-1), a(i-2) + k(i)) // a(i) = i번째 식량창고까지 얻을 수 있는 식량의 최댓값

n = int(input()) # 정수 N을 입력 받기
arr = list(map(int, input().split()) # 모든 식량 정보 입력 받기

d = [0]*100 # 앞서 계산된 결과를 저장하기 위한 DP테이블 초기화, 창고가 100개까지 있으므로 *100

# 다이나믹 프로그래밍 진행 (버텀업)

d[0] = arr[0]
d[1] = max(arr[0], arr[1])

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

 

 

• <1로 만들기>
• 정수 X가 주어졌을 때 정수 X에서 사용할 수 있는 연산은 다음과 같이 4가지이다.
  • X가 5로 나누어 떨어지면, 5로 나눈다.
  • X가 3으로 나누어 떨어지면, 3으로 나눈다.
  • X가 2로 나누어 떨어지면, 2로 나눈다
  • X에서 1을 뺀다.
• 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 값을 1로 만들고자 한다. 연산을 사용하는 횟수의 최솟값을 출력하라. 예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다. ex) 26 -> 25 -> 5 -> 1
  • 첫째 줄에 정수 X가 주어진다 (1<= X  <= 30,000)
  • 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

해당 문제의 점화식은 a(i) = min(a(i-1), a(i/2), a(i/3), a(i/5) + 1/ 단 1을 빼는 연산을 제외한 해당 수로 나누어 떨어질 때에 한해 점화식을 적용할 수 있다.

 

x = int(input()) # x 입력 받기

d[0] * 30001 # DP테이블 초기화

# 다이나믹 프로그래밍 진행(버텀업)
for i in range(2, x+1):
   	d[i] = d[i-1] + 1 # 현재의 수에서 1을 빼는 경우
    
    if i % 2 == 0: # 현재의 수가 2로 나눠 떨어지는 경우
    	d[i] = min(d[i], d[i//2] + 1
    if i % 3 == 0: # 현재의 수가 3으로 나눠 떨어지는 경우
    	d[i] = min(d[i], d[i//3] + 1
    if i % 5 == 0: # 현재의 수가 5로 나눠 떨어지는 경우
    	d[i] = min(d[i], d[i//5] + 1
        
print(d[x])

 

 

• <효율적인 화폐 구성>
• N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 종류의 화폐는 몇 개라도 사용할 수 있다.
• 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.
• M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 만들어라.
  • 첫재 줄에 N, M이 주어진다. (1<= N <= 100, 1<= M <= 10,000)
  • 이후의 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐의 가치는 10,000보다 작거나 같은 자연수 이다.
  • 첫재 줄에 최소 화폐 개수를 출력한다. 불가능 할때는 -1을 출력한다.

a(i)가 금액 i를 만들 수 있는 최소한의 화폐 개수라 할때, k는 각 화폐의 단위이다. 이를 점화식으로 나타내보면, 각 화폐 단위인 k를 하나씩 확인하며

a(i-k)를 만드는 방법이 존재하는 경우, a(i) = min(a(i), a(i-k)+1)

a(i-k)를 만드는 방법이 존재하지 않는 경우,  a(i) = INF

n, m = map(int, input().split()) # N과 M 입력받기

coin = [] # N개의 화폐 단위 정보 입력 받기
for i in range(n):
	coin.append(int(input()))
    
d[0] = [10001] * (m + 1) # DP 테이블 초기화, 1부터 시작하므로 가능 금액 + 1   
for i in range(n):
	for j in range(coin[i], m+1):
    	if d[j - coin[i]] != 10001: # (i-k)원을 만드는 방법이 존재하는 경우
        	d[j] = min(d[j], d[j - coin[i]] +1)
            
# 계산된 결과 출력
if d[m] == 10001: # M원 만드는 방법이 없는 경우
	print(-1)
else:
    print(d[m])

 

 

• <금광>
• n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 
• 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하라
  • 첫째 줄에는 테스트 케이스 T가 입력된다. (1<= T <=1,000)
  • 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력된다. (1<= n, m <=20) 둘째 줄에 n x m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력된다. (1<= 각 위치에 매장된 금의 개수 <=100)
  • 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력한다. 각 테스트 케이스는 줄바꿈을 이용해 구분한다.

금광의 모든 위치에 대해서 왼쪽 위, 왼쪽, 왼쪽 아래에서 오는 3가지 경우에 대해서만 고려하면 된다. 이 세 가지 경우 중에서 가장 많은 금을 가지고 있는 경우를 테이블에 저장해서 문제를 해결하면 된다.

arr[i][j] = i행 j열에 존재하는 금의 양으로, d[i][j] = i행 j열까지의 최적의해(얻을 수 있는 금의 최댓값)이라고 할때 점화식은 아래와 같다.

d[i][j] = arr[i][j] + max(arr[i-1][j-1], arr[i][j-1], arr[i+1][j-1]) (현재 위치 값 + 왼쪽 위, 왼쪽, 왼쪽 아래 중 최댓값)

이때 테이블에 접근 시 리스트의 범위를 벗어나지 않는지 체크 해야한다.

for tc in range(int(input()): # 테스트 케이스 입력
	n, m = map(int, input().split()) # 금광 정보 입력
    arr = list(map(int, input().split()))
    
    # 다이나믹 프로그래밍을 위한 DP 테이블 초기화
    dp = []
    index = 0
    for i in range(n): # n행 만큼 반복
    	dp.append(arr[index:index +m]) # m 열 만큼 2차원 배열로 만들기
        index += m 
    # 다이나믹 프로그래밍 진행   
    for j in range(1, m): # 두번째 열부터 m번째 열까지 반복 진행
        for i in range(n):
            if i == 0: left_up = 0 # 왼쪽 위에서 오는 경우, i가 0일 경우 왼쪽위에서 오는 경우는 없으므로 0
            else: left_up = dp[i-1][j-1]
            
            if i == n-1: left_down = 0 # 왼쪽 아래에서 오는 경우, i가 n-1일 경우 왼쪽아래에서 오는 경우는 없으므로 0
            else: left_down = dp[i+1][j-1]
            
            left = dp[i][j-1]
            dp[i][j] = dp[i][j] + max(left_up, left, left_down)
            
    result = 0
    
    for i in range(n):
    	result = max(result, dp[i][m-1])
    print(result)

 

 

 

• <병사 배치하기>
• N명의 병사가 무작위로 나열되어 있고, 각 병사는 특정한 값의 전투력을 보유하고 있다. 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 해야한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.
• 또한 배치과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서 남아 있는 병사의 수가 최대가 되도록 하고 싶다.
  • 첫째 줄에 N이 주어진다. (1<= N <=2,000) 둘째 줄에 각 병사의 전투력이 공백으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.
  • 첫째 줄에 남아 있는 병사의 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수를 출력하라

문제의 기본 아이디어는 가장 긴 증가하는 부분 수열로 알려진 전형적인 다이나믹 프로그래밍 문제의 아이디어와 같다. 예를 들어 하나의 수열 [4, 2, 5, 8, 4, 11, 15]가 있다고 하면 이 수열의 가장 긴 증가하는 부분은 [4, 5, 8, 11, 15]이다. 이 문제는 가장 긴 감소하는 부분 수열을 찾는 문제로 치환가능하며, 가장 긴 증가하는 부분수열(LIS) 알고리즘을 수정(입력받은 병사 순서를 뒤집음)하여 적용함으로써 정답을 도출할 수 있다.

n = int(input())
arr = list(map(int, input().split()))

arr.recerse() # 순서를 뒤집어 최장 증가 부분 수열(LIS) 문제로 변환

dp = [1] * n  # 다이나믹 프로그래밍을 위한 1차원 DP테이블 초기화

# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행

for i in range(1, n):
	for j in range(0, i):
    	if arr[j] < arr[i]:
        	dp[i] = max(dp[i], dp[j] +1)

# 열외해야 하는 병사의 최소 수를 출력
print(n-max(dp))