[알고리즘] Dynamic Programming(동적 계획법)

1. 다이나믹 프로그래밍이란?

- "동적 계획법"

- step1. 하나의 큰 문제를 여러 개의 작은 문제로 나눈다.

- step2. 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용한다.

- 하나의 문제 해결 패러다임 (특정한 알고리즘 X)

- 기억하기 프로그래밍

---

2. 재귀와 DP의 차이?

- 일반적인 재귀(Naive Recursion)를 단순히 사용 시, 동일한 작은 문제들이 여러 번 반복 > 비효율적 계산 

ex. 피보나치 수열 

- 재귀:  f(n-1), f(n-2)에서 각 함수를 1번씩 호출

     => 동일한 값을 2번씩 구하게 됨

     => n 값이 증가함에 따라 호출되는 함수의 횟수는 기하급수적으로 증가 (약 7해)

- DP: 한 번 구한 작은 문제의 결과 값을 저장하고 재사용

         > 반복 X > 약 200회 내에서 계산이 가능.

- 시간 복잡도가 O(n^2) → O(f(n)) 로 개선

---

3. DP의 사용 조건?

* DP의 전제 조건: 큰 문제를 여러 작은 문제로 나누고, 이 결과를 재활용하여 전체 답을 구한다.

 

1️⃣ Overlapping Subproblems (겹치는 부분 문제)

- 동일한 작은 문제들이 반복하여 나타나는 경우, 사용 가능

- 부분 문제가 반복적으로 나타나지 X => 재사용이 불가

=> 부분 문제가 중복되지 않는 경우는 사용할 수 없다.

ex. 피보나치 수열

- 이진 탐색: 정렬된 배열 내에서 위치를 찾아 데이터를 바로 반환 > 재사용 과정 X

- DP: f(3), f(2), f(1)과 같이 동일한 부분문제가 중복 > 저장된 값을 재활용 可

---

2️⃣ Optimal Substructure (최적 부분 구조)

- 부분 문제의 최적 결과 값을 사용 > 전체 문제의 최적 결과를 낼 수 있는 경우

=> 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일

ex. A-B까지의 가장 짧은 경로 찾기 (중간에 X가 존재)

- A - X / B - X가 여러 경로 중 가장 짧은 경로라면, 전체 최적 경로도 A - X - B

- 여기서는 AX2 -BX2가 전체 최단 거리 (아무리 많은 경로가 추가되어도, 전체 최단 거리는 변하지 않는다.)

=> 부분 문제에서 구한 최적 결과가 전체 문제에도 동일하게 적용되어 결과가 변하지 않으면 DP 사용 가능

---

4. DP 사용하기

- 특정한 경우에 사용하는 알고리즘 X

- 하나의 방법론으로 다양한 문제해결에 사용 가능!

 

1️⃣ DP로 풀 수 있는 문제인지 확인

- 작은 문제들로 이루어진 하나의 함수로 표현될 수 있는가?

- 일반적으로 DP로 풀 수 있는 경우 : 특정 데이터 내 최대화/최소화 계산

                                                        : 특정 조건 내 데이터를 세기

                                                        : 확률 계산

---

2️⃣ 문제의 변수 파악

- 현재 변수에 따라 그 결과 값을 찾는다 > 값을 전달한다 > 재사용한다.

=> 문제 내, 변수의 개수를 알아야 한다. (state를 결정한다.)

ex. (1) 피보나치 수열 : n번째 숫자 구하기 > n이 변수

      (2) 문자열 간의 차이 : 문자열의 길이, Edit 거리가 변수

            ** Edit 거리? - 문자열 A와 문자열 B가 존재

                                 - A의 문자를 삭제, 변경, 삽입하여 문자열 B를 만듦.

                                 - 이 때, 최소 횟수를 구하는 문제

      (3) Knapsack 문제 : index, 무게가 변수

---

3️⃣ 변수 간, 관계식 만들기 (점화식)

- 동일한 변수 값인 경우, 결과가 동일

- 그 결과값을 그대로 이용할 것 > 관계식을 만들 수 있다 >> 점화식

- 점화식을 통해, 짧은 코드 내에서 반복/재귀로 문제가 자동 해결 가능하도록

ex. 피보나치 수열 : f(n) = f(n-1) + f(n-2)

---

4️⃣ 메모하기 (memorization or tabulation)

- 변수의 값에 따른 결과를 저장 (메모)

- step 1. 변수 값에 따른 결과를 저장할 배열을 미리 만듦.

- step 2. 결과가 나올 때 마다, 배열 내에 저장

- step 3. 그 저장된 값을 재사용

---

5️⃣ 기저 상태 파악하기

- 가장 작은 문제의 상태 알기

ex. 피보나치 수열: f(0) = 0,  f(1) = 1

---

6️⃣ 구현하기

(1) Bottom-Up (Tabulation 방식)  ~  반복문

- 아래에서부터 계산 수행 > 결과를 누적 > 전체 큰 문제를 해결

ex. dp라는 배열 존재

- 기저 상태: dp[0], 목표 상태: dp[n]

- Bottom-Up : dp[0]부터 시작 > 반복문 > 점화식으로 결과를 냄 > dp[n]까지 값을 전이시켜 재활용

- table-filling: 반복을 통해 dp[0]부터 하나씩 채우는 과정 > 이 테이블에 저장된 값에 직접 접근하여 재활용 > Tabulation

 

(2) Top-Down (Memorization 방식)  ~  재귀

- dp[n]의 값을 찾기 위해 위에서부터 바로 호출 시작

- dp[0]까지 내려간 다음, 해당 결과 값을 재귀를 통해 전이시켜 재활용

ex. 피보나치 수열 f(n) = f(n-2) + f(n-1)에서

- n=5일 때, f(3), f(2)의 동일한 계산이 반복적으로 나옴

- 이미 이전에 계산을 완료한 경우, 단순히 메모리에 저장된 내역을 꺼내서 활용

=> 가장 최근의 상태 값을 메모해 두었다 (Memorization)

* Memorization: 컴퓨터 프로그램이 동일한 계산을 반복할 경우 사용

                        : 이전에 계산한 값을 메모리에 저장 > 동일한 계산의 반복 수행 제거

                        : 프로그램 실행 속도 빠르게 하는 기술

---

⭐Divide and Conquer(분할 정복)와 차이점은?

- 공통점: 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결

- 차이점 ~ 분할 정복 : 분할된 하위 문제가 동일하게 중복이 일어나지 않은 경우 ex. 병합정렬

                 동적 프로그래밍: 분할된 하위 문제가 동일하게 중복이 일어나는 경우 ex. 피보나치 수열

 

⭐동적 프로그래밍의 대표적인 세 가지 문제

- 막대기 자르기 문제

- 최장 공통 부분 수열 문제

- 0/1 배낭 문제

---

5. 참고 자료

- https://hongjw1938.tistory.com/47

- https://didu-story.tistory.com/220

- https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182