다이나믹 프로그래밍

Ⅰ. 다이나믹 프로그래밍

• 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법.

• 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

• 일반적으로 탑다운, 보텀업 2가지 방식으로 구성된다.

• 동적 계획법이라고도 부른다.

다이나믹 프로그래밍의 조건

1. 최적 부분 구조 (Optimal Substructure)

   큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있습니다.

2. 중복되는 부분 문제 (Overlapping Subproblem)

   동일한 작은 문제를 반복적으로 해결해야 합니다.

다이나믹 프로그래밍 V.S. 분할 정복

• 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있습니다.

• 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황

• 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복입니다.

• 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됩니다.

• 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않습니다.

다이나믹 프로그래밍 문제 접근 방법

• 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토하고 없다면 다이나믹 프로그래밍 고려

• 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 코드를 개선하는 방법을 사용 가능 (탑다운)

• 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복입니다.

① 탑다운

• 하향식이라고도 합니다.

• 재귀함수를 사용합니다.

메모이제이션 (Memoization)

• 다이나믹 프로그래밍을 구현하는 방법 중 하나입니다.

• 한 번 계산한 결과를 메모리 공간에 메모하는 기법입니다.

• 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옵니다.

• 값을 기록해 놓는다는 점에서 캐싱이라고도 합니다.

피보나치 수열 (탑다운 DP)

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
# 99 피보나치수 구하려고하니까 100으로 해줌
d = [0] * 100

# 피보나치 함수를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
    # 종료 조건(1 혹은 2일 때 1을 반환)
    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))

메모이제이션을 이용하면 피보나치 수열 함수의 시간 복잡도는 $O(N)$입니다.

② 보텀업

• 상향식이라고도 합니다.

• 다이나믹 프로그래밍의 전형적인 형태.

• 구현할때 결과 저장용 리스트는 DP 테이블이라고 부릅니다.

• 반복문을 사용합니다.

파이썬 구현

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
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])

Ⅱ. 예제

① 개미 전사

❔ 문제 설명

개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 합니다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있습니다.

각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정입니다.
이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있습니다.

따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 합니다.

개미 전사는 식량창고에서 최대한 많은 식량을 얻기를 원합니다.
개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최대값을 구하는 프로그램을 작성하세요.

💡 문제 해결 아이디어

• $a_i$ = i번째 식량창고까지의 최적의 해 (얻을 수 있는 식량의 최대값)

• $k_i$ = i번째 식량창고에 있는 식량의 양

• 한 칸 이상 떨어진 식량창고는 항상 털 수 있으므로 i-3번째 이하는 고려할 필요가 없습니다.

• 점화식은 $a_i = max(a_{i-1}, a_{i-2} + k_i)$

✔️ 풀이

Python

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

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[0] = array[0]
d[1] = max(array[0], array[1]) 
# 창고는 1부터 시작하는데 인덱스는 0부터 이므로 i는 n-1까지 
for i in range(2, n):
    d[i] = max(d[i - 1], d[i - 2] + array[i])

# 계산된 결과 출력
print(d[n - 1])

② 1로 만들기

❔ 문제 설명

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

  1. X가 5로 나누어 떨어지면, 5로 나눕니다.
  2. X가 3으로 나누어 떨어지면, 3으로 나눕니다.
  3. X가 2로 나누어 떨어지면, 2로 나눕니다.
  4. X에서 1을 뺍니다.

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 값을 1로 만들고자 합니다. 연산을 사용하는 횟수의 최소값을 출력하세요. 예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값입니다.

26 -> 25 -> 5 -> 1

💡 문제 해결 아이디어

• 최적 부분 구조와 중복되는 부분 문제를 만족합니다.

• $a_i = i$를 1로 만들기 위한 최소 연산 횟수

• 점화식은 $a_i = min(a_{i-1}, a_{i/2}, a_{i/3}, a_{i/5}) + 1$

• 단, $a_{i-1}$ 연산을 제외하고는 $a_{i/2}, a_{i/3}, a_{i/5}$는 해당 수로 나누어 떨어질 때 점화식을 적용합니다.

✔️ 풀이

Python

# 정수 X를 입력 받기
x = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1000001

# 다이나믹 프로그래밍(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)
        
    # 25면 5로 나누면 5남는데 이 남은 5는 몇번 연산해야 1되는지가 d[5] 
    # 여기에 5곱하는 1번의 연산만 더해주면 되므로 d[i // 5] + 1 인 원리

print(d[x])

③ 효율적인 화폐 구성

❔ 문제 설명

N가지 종류의 화폐가 있습니다. 이 화쳬들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 합니다. 이때 각 종류의 화폐는 몇 개라도 사용할 수 있습니다.

예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수입니다.

M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하세요.

💡 문제 해결 아이디어

• $a_i =$ 금액$i$를 만들 수 있는 최소한의 화폐 개수

• k = 각 화폐의 단위

• 점화식 : 각 화폐 단위인 k를 하나씩 확인하며

  $a_{i-k}$를 만드는 방법이 존재하는 경우, $a_i = min(a_i,a_{i-k} + 1)$
  $a_{i-k}$를 만드는 방법이 존재하지 않는 경우, $a_i = INF$

• 각각의 화폐 단위수 N개로 1부터 M까지의 수들을 다 되는지 판단하므로
  시간 복잡도는 $O(N * M)$

✔️ 풀이

Python

# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
    array.append(int(input()))

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
    	# (i - k)원을 만드는 방법이 존재하는 경우
        if d[j - array[i]] != 10001: 
            d[j] = min(d[j], d[j - array[i]] + 1)

# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

⑤ 병사 배치하기

❔ 문제 설명

N명의 병사가 무작위로 나열되어 있습니다. 각 병사는 특정한 값의 전투력을 보유하고 있습니다.

병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 합니다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 합니다.

또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용합니다. 그러면서도 남아 있는 병사의 수가 최대가 되도록 하고 싶습니다.

💡 문제 해결 아이디어

• 가장 긴 증가하는 부분 수열(LIS)로 알려진 전형적인 다이나믹 프로그래밍 문제의 아이디어

• {4, 2, 5, 8, 4, 11, 15}의 가장 긴 증가하는 부분 수열 = {4, 5, 8, 11, 15}

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

• 점화식은 $D[i] = max(D[i], D[j] + 1)$ $if$ $array[j] < array[i]$, $∀$ $O ≤ j < i$

• 이 문제는 가장 긴 감소하는 부분 수열을 찾는 문제이다.

• 가장 먼저 입력 받은 병사 정보의 순서를 뒤집고 LIS 알고리즘을 수행하여 정답을 도출

✔️ 풀이

Python

n = int(input())
array = list(map(int, input().split()))
# 순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환
array.reverse()

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

# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
# 인덱스는 0부터 시작하므로 n-1 까지 
for i in range(1, n):
    for j in range(0, i):
        if array[j] < array[i]:
	# dp[j] = 앞의 수가 더 작으면 그 수까지의 최대 결과 길이 
    	# +1 한것들 중 최대값 = dp[i] 사용
            dp[i] = max(dp[i], dp[j] + 1)

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