🔎 다이나믹 프로그래밍

다이나믹 프로그래밍(동적 계획법)은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함
다이나믹 프로그래밍의 구현은 일반적으로 탑다운, 보텀업 두 가지 방식으로 구성됨

참고) 일반적인 프로그래밍 분야에서의 동적(Dynamic) ≠ 다이나믹 프로그래밍에서의 '다이나믹'

• 자료구조에서 동적 할당은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'
• 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어

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

1. 최적 부분 구조
   • 큰 문제를 작은 문제로 나눌 수 있음
   • 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일
2. 중복되는 부분 문제
   • 동일한 작은 문제를 반복적으로 해결해야 함

📍 피보나치 수열

1, 1, 2, 3, 5, 8, 13, 21, ...
이와 같은 형태의 수열이며, 다이나믹 프로그래밍으로 효과적으로 계산할 수 있음
점화식이란 인접한 항들 사이의 관계식을 의미
an = an-1 + an-2, a1 = 1, a2 = 1

단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게 됨
동일한 함수가 반복적으로 호출됨 (중복되는 부분 문제)
ex) f(5) = f(4) + f(3), f(4) = f(3) + f(2)..
    f(5)를 계산할 때 f(3) 호출, f(4)를 계산할 때도 f(3)을 호출..

📍 메모이제이션

메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류
한 번 구한 결과를 메모리 공간에 메모하는 기법

• 같은 식을 다시 호출하면 메모한 결과를 그대로 가져옴
• 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 함

메모이제이션은 어떻게 구현? => 한 번 구한 정보를 리스트에 저장

📍 탑다운 VS 보텀업

탑다운(메모이제이션) 방식은 하향식이라고도 함
큰 문제를 해결하기 위해 작은 문제를 호출

보텀업 방식은 상향식이라고도 함
작은 문제부터 차근차근 답을 도출

다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식
보텀업 방식에서 사용되는 결과 저장용 리스트 = 'DP 테이블'

📍 다이나믹 프로그래밍 VS 분할 정복

공통점: 최적 부분 구조를 가질 때 사용할 수 있음
차이점: 부분 문제의 중복

• 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨
• 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않음

📍 다이나믹 프로그래밍 문제에 접근하는 방법

주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요 (당연한 것..)
그리디, 구현, 완전 탐색 등의 아이디어로 문제 해결 가능한지 우선 검토 후 다이나믹 프로그래밍 고려해보기

재귀 함수로 비효율적인 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 코드를 개선하는 방법도 좋은 아이디어
가능하다면 재귀함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장함
참고) sys 라이브러리에 포함되어 있는 setrecursionlimit() 함수

코딩 테스트의 다이나믹 프로그래밍 문제는 대체로 간단한 형태로 출제됨

---

✏️ 실전 문제

📝 1로 만들기

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 아래의 4가지
ⓐ X가 5로 나누어떨어지면, 5로 나눔
ⓑ X가 3으로 나누어떨어지면, 3으로 나눔
ⓒ X가 2로 나누어떨어지면, 2로 나눔
ⓓ X에서 1을 뺌

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 함
연산을 사용하는 횟수의 최솟값을 출력하시오

• 입력 조건
  - 첫째 줄에 정수 X가 주어짐 (1 ≤ X ≤ 30,000)
  
• 출력 조건
  - 첫째 줄에 연산을 하는 횟수의 최솟값을 출력함
  

문제 해설

이 문제는 잘 알려진 다이나믹 프로그래밍 문제
(그림으로 도식화해보기)
점화식 => ai = min(ai-1, ai/2, ai/3, ai/5) + 1
이 점화식을 토대로 보텀업 다이나믹 프로그래밍으로 소스코드 작성
(단, 1을 빼는 연산을 제외하고는 해당 수로 나누어떨어질 때에 한해서만 점화식을 적용할 수 있음)

소스코드

---

📝 개미 전사

개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 함
메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있음
각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정임

이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있음
따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소 한 칸 이상 떨어진 식량창고를 약탈해야 함
ex) 식량창고 4개 [1, 3, 1, 5] => 두 번째와 네 번째 식량창고 선택시, 최댓값인 8

개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오

• 입력 조건
  - 첫째 줄에 식량창고의 개수 N이 주어짐 (3 ≤ N ≤ 100)
  • 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어짐 (0 ≤ K ≤ 1,000)
    
• 출력 조건
  - 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력함
  

문제 해설

그림으로 도식화해보기

왼쪽부터 차례대로 식량창고를 털지 안 털지를 결정하는 경우와 특정한 i번째 식량창고에 대해서 털지 안털지의 여부를 결정할 때, 단 2가지 경우에 대해서만 확인하면 됨
ⓐ (i - 1)번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 없음
ⓑ (i - 2)번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 있음
따라서 ⓐ와 ⓑ 중에서 더 많은 식량을 털 수 있는 경우를 선택하면 됨

점화식 => ai = max(ai-1, ai-2 + ki) // i번째 식량창고에 있는 식량의 양 ki

소스코드

---

📝 바닥 공사

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있음
수빈이는 이 얇은 바닥을 1 x 2의 덮개, 2 x 1의 덮개, 2 x 2의 덮개를 이용해 채우고자 함

이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오

• 입력 조건
  - 첫째 줄에 N이 주어짐 (1 ≤ N ≤ 1,000)
  
• 출력 조건
  - 첫째 줄에 2 x N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력함
  

문제 해설

다이나믹 프로그래밍의 기초 예제에서 빠질 수 없는 타일링 문제 유형
다이나믹 프로그래밍의 문제에서는 종종 결과를 어떤 수로 나눈 결과를 출력하라는 내용이 들어가있는 경우가 많음 (이 문제에서는 796,796으로 나눈 나머지를 출력)

왼쪽부터 차례대로 바닥을 덮개로 채운다고 생각하여 점화식을 세워보자
1. 왼쪽부터 i - 1까지 길이가 덮개로 이미 채워져 있으면 2 x 1의 덮개를 채우는 하나의 경우밖에 존재하지 않음
2. 왼쪽부터 i - 2까지 길이가 덮개로 이미 채워져 있으면 1 x 2 덮개 2개를 넣는 경우, 혹은 2 x 2의 덮개 하나를 넣는 경우로 2가지 경우가 존재함
(2 x 1 덮개 2개를 넣는 경우는 1에서 이미 해당 경우가 고려되었기 때문)

점화식 => ai = ai-1 + ai-2 x 2

소스코드

---

📝 효율적인 화폐 구성

N가지 종류의 화폐가 있음, 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려 함
각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분함

• 입력 조건
  - 첫째 줄에 N, M이 주어짐 (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000)
  • 이후 N개의 줄에는 각 화폐의 가치가 주어짐, 화폐 가치는 10,000보다 작거나 같은 자연수
    
• 출력 조건
  - 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력함
  • 불가능할 때는 -1을 출력함

문제 해설

적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾으면 됨

금액 i를 만들 수 있는 최소한의 화폐 개수를 ai, 화폐의 단위를 k라고 했을 때,
(ai-k는 금액 (i - k)를 만들 수 있는 최소한의 화폐 개수)
점화식

• ai-k를 만드는 방법이 존재하는 경우, ai = min(ai, ai-k + 1)
• ai-k를 만드는 방법이 존재하지 않는 경우, ai = 10,001

ex) N = 3, K = 7, 각 화폐의 단위가 2, 3, 5인 경우
step 0 초기화: 각 인덱스에 10,001 설정 (10,001은 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다는 의미)

인덱스	0	1	2	3	4	5	6	7
값	0	10,001	10,001	10,001	10,001	10,001	10,001	10,001

step 1 화폐 단위: 2, 3, 5: 가장 먼저 첫 번째 화폐 단위인 2부터 확인함
인덱스 2의 경우 값 1 => a2 = a0 + 1 (2원짜리 화폐 하나 이용하여 2원)
인덱스 4의 경우 값 2 => a4 = a2 + 1 (2원짜리 화폐 두개 이용하여 4원)

인덱스	0	1	2	3	4	5	6	7
값	0	10,001	1	10,001	2	10,001	3	10,001

step 2 화폐 단위: 2, 3, 5: 화폐 단위 3을 확인함
인덱스 5의 경우 값 2 => a5 = a2 + 1 (2원짜리 화폐 하나, 3원짜리 화폐 하나 이용하여 5원)

인덱스	0	1	2	3	4	5	6	7
값	0	10,001	1	1	2	2	3	3

step 3 화폐 단위: 2, 3, 5: 화폐 단위 5을 확인함
인덱스 7의 경우 값 2 => a7 = a2 + 1 (2원짜리 화폐 하나, 5원짜리 화폐 하나 이용하여 7원) // a7 = 3 (2 + 2 + 3) => 2 (2 + 5)
더 작은 값으로 갱신됨

인덱스	0	1	2	3	4	5	6	7
값	0	10,001	1	1	2	1	2	2

소스코드

---

📒 이것이 코딩 테스트다 교재를 통해 학습한 내용을 정리하였습니다.