[Week7] 동적 계획법 (DP: Dynamic Programming)

동적 계획법 (DP: Dynamic Programming)

작은 문제들을 풀면서 그 결과를 저장해 나아가면서 전체 문제를 해결하는 알고리즘

중복 계산을 줄여서 계산 속도를 높일 수 있으며, 경우의 수가 많은 경우에도 효율적으로 계산할 수 있다. 

일반적으로 재귀를 사용해서 구현되며 메모이제이션(Memoization) 기법을 사용하여 중복 계산을 피한다. 

---

동적 계획법의 조건

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

 

'큰 문제의 최적해'가 '작은 문제의 최적해'를 포함하는 성질

즉, 작은 문제의 최적해를 구한 후 그것을 이용하여 큰 문제의 최적해를 구할 수 있다. 

 

2. 중복 부분 문제(Overlapping Subproblems)

f(3), f(2), f(1)이 반복적으로 나타남

 

'동일한 작은 문제를 반복적으로 해결'해야 하는 성질

즉, 작은 문제를 해결할 때 반복적으로 같은 문제를 해결해야 한다. 

---

동적 계획법의 구현 단계

1. DP로 풀 수 있는 문제인지 확인한다.

 

현재 직면한 문제가 작은 문제들로 이루어진 하나의 함수로 표현될 수 있는지 판단하기

즉, 위의 조건들이 충족되는 문제인지 체크

 

보통 특정 데이터 내 최대화 / 최소화 계산을 하거나, 특정 조건 내 데이터의 개수나 확률 등의 계산의 경우

DP로 풀 수 있는 경우가 많다. 

 

 

2. 문제의 변수를 파악한다. 

 

DP는 현재 변수에 따라 그 결과 값을 찾고 그것을 전달하여 재사용하는 것을 거친다. 

즉, 문제 내 변수의 개수를 알아내야 한다는 것. 이것을 영어로 "state"를 결정한다고 한다.

 

예를 들어, 피보나치 수열에서는 n번째 숫자를 구하는 것이므로 n이 변수가 된다. 

그 변수가 얼마이냐에 따라 결과값이 다르지만 그 결과를 재사용하고 있다. 

 

 

3. 변수 간 관계식 만들기 (점화식)

 

변수들에 의해 결과 값이 달라지지만 동일한 변수값인 경우 결과는 동일하다.

또한 우리는 그 결과값을 그대로 이용할 것이므로 그 관계식을 만들어낼 수 있어야 한다.

그러한 식을 점화식이라고 부르며

그를 통해 짧은 코드 내에서 반복/재귀를 통해 문제가 자동으로 해결되도록 구축할 수 있게 된다.

 

예를 들어 피보나치 수열에서는 f(n) = f(n-1) + f(n-2) 였다. 이는 변수의 개수, 문제의 상황마다 모두 다를 수 있다.

 

 

4. 메모하기 (Memoization or Tabulaion)

 

변수 간 관계식까지 정상적으로 생성되었다면 변수의 값에 따른 결과를 저장해야 한다.

이것을 메모한다고 하여 Memoization이라고 부른다.

 

변수 값에 따른 결과를 저장할 배열 등을 미리 만들고

그 결과를 나올 때마다 배열 내에 저장하고

그 저장된 값을 재사용하는 방식으로 문제를 해결해 나간다.

 

이 결과 값을 저장할 때는 보통 배열을 쓰며 변수의 개수에 따라 배열의 차원이 1~3차원 등 다양할 수 있다.

 

 

5. 기저 상태 파악하기

 

여기까지 진행했으면, 가장 작은 문제의 상태를 알아야 한다.

보통 몇 가지 예시를 직접 손으로 테스트하여 구성하는 경우가 많다. 

 

피보나치 수열을 예시로 들면, f(0) = 0, f(1) = 1과 같은 방식이다.

이후 두 가지 숫자를 더해가며 값을 구하지만 가장 작은 문제는 저 2개로 볼 수 있다.

 

해당 기저 문제에 대해 파악 후 미리 배열 등에 저장해두면 된다.

이 경우, 피보나치 수열은 매우 간단했지만 문제에 따라 좀 복잡할 수 있다.

 

 

6. 구현하기

 

DP는 2가지 방식으로 구현할 수 있다.

 

1) Bottom-Up (Tabulation 방식) - 반복문 사용
2) Top-Down (Memoization 방식) - 재귀 사용

 

메모이제이션 (Memoization)
'중복 계산'을 피하기 위한 기법
이전에 계산된 결과를 저장하고 다음에 동일한 계산이 필요할 때 저장된 결과를 이용하여
중복을 피함으로써 성능을 향상시킬 수 있다.

메모이제이션 구성 과정
1. 입력값에 대한 결과값을 저장할 메모이제이션 테이블 생성 및 초기화
2. 함수를 호출할 때, 먼저 메모이제이션 테이블에서 해당 입력값의 결과값이 이미 저장되어 있는지 확인
3. 저장되어 있으면 해당 결과값을 반환, 저장되어 있지 않으면 계산을 수행하고 그 결과를 메모이제이션 테이블에 저장
4. 계산된 결과값을 반환

※ 메모이제이션 테이블
동적 계획법에서 사용되는 저장 공간 이전에 계산한 값을 저장해 둠
나중에 같은 값을 계산할 때 다시 계산하지 않고 이전에 계산한 값을 활용하여 계산 속도를 높임
일반적으로 해시 테이블이나 배열 등을 사용하여 구현

 

---

DP 구현 방법

1. Bottom-Up 방식

 

이름에서 보이듯이, 

아래에서 부터 계산을 수행 하고 누적시켜서 전체 큰 문제를 해결하는 방식이다.

 

메모를 위해서 dp라는 배열을 만들었고 이것이 1차원이라 가정했을 때,

dp[0]가 기저 상태이고 dp[n]을 목표 상태라고 하자.

Bottom-up은 dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서

dp[n]까지 그 값을 전이시켜 재활용하는 방식이다.

 

왜 Tabulation?

 

반복을 통해 dp[0]부터 하나 하나씩 채우는 과정을 "table-filling" 하며,

이 Table에 저장된 값에 직접 접근하여 재활용하므로 Tabulation이라는 명칭이 붙었다고 한다.

사실상 근본적인 개념은 결과값을 기억하고 재활용한다는 측면에서 메모하기(Memoization)와 크게 다르지 않다.

 

 

 

2. Top-Down 방식

 

이는 dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 

위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음

해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식이다.

 

피보나치의 예시처럼,

f(n) = f(n-2) + f(n-1)의 과정에서 함수 호출 트리의 과정에서 보이듯,

n=5일 때, f(3), f(2)의 동일한 계산이 반복적으로 나오게 된다.

이 때, 이미 이전에 계산을 완료한 경우에는 단순히 메모리에 저장되어 있던 내역을 꺼내서 활용하면 된다.

그래서 가장 최근의 상태 값을 메모해 두었다고 하여 Memoization 이라고 부른다.

 

---

분할 정복과의 차이점

 

주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다는 점은 같다.

차이점은, 분할 정복은 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰며,

동일한 중복이 일어나면 동적 프로그래밍을 쓴다는 것이다.

 

https://hongjw1938.tistory.com/47

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

https://adjh54.tistory.com/201

[Java/알고리즘] 동적 계획법(DP: Dynamic Programming) 이해하기