> For the complete documentation index, see [llms.txt](https://jimmyblog.gitbook.io/jimmys-blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmyblog.gitbook.io/jimmys-blog/jimmys-tech/algorithm/dynamic-programming.md). # Dynamic Programming ## 개념 동적 계획법(Dynamic Programming)은 전체 문제를 한 번에 해결하는 것이 아니라 작은 부분 문제들을 해결하고, 이것들을 활용하여 전체 문제를 해결하는 방법이다. 동적 계획법을 효율적으로 활용하려면 아래 두 가지 조건을 만족해야 한다. 1. 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장해야 한다. 2. 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성할 수 있어야 한다. ### 점화식 세우기와 동적 계획법 동적 계획법으로 문제를 해결하는 절차는 다음과 같다. 1. 문제를 해결하는 해가 이미 있다고 가정한다. 2. 종료 조건을 설정한다. 3. 과정 1, 2를 활용해 점화식을 세운다. ### 피보나치 수 구하기 다음과 같이 재귀에 메모이제이션을 조합해보자. 1. 메모이제이션을 위한 저장소 생성 : 이미 구한 해를 저장할 공간 생성 2. 재귀 함수 정의 : 점화식을 재귀로 표현할 함수를 정의 3. 재귀 함수의 종료 조건을 정의 : 피보나치 수의 첫 번째, 두 번째 수는 1로 정해져 있으므로 메모이제이션 저장소에 해를 미리 넣어두고 종료 조건으로 생각한다. 4. 재귀 함수의 일반 연산 처리 : 동적 계획법에서는 점화식으로 나머지 문제를 처리한다. 그 과정에서 구한 결괏값은 메모이제이션 저장소에 저장한다. 우선 점화식을 재귀와 메모이제이션으로 어떻게 구현할지에 대한 의사코드를 작성한다. ```java fibodata[N] // 메모이제이션을 위한 배열 선언, 0으로 초기화 // 메서드 정의 int fibo(int N) { // 메모이제이션 활용 if (fibodata[N] != 0) fibodata[N] 반환 // 메모이제이션, 종료 조건 if (N이 2 이하이면) fibodata[N]에 1 삽입 // 메모이제이션, 일반항 else fibodata[N]에 fibo(N - 1) + fibo(N - 2) 삽입 } fibo(N) 호출 fibodata[N] 반환 ``` 피보나치 구현 코드 ```kotlin val n = 5 // 메모이제이션을 위한 배열 선언, 0으로 초기화 val fibodata = IntArray(n + 1) { 0 } // 메서드 정의 fun fibonacci(n: Int): Int { // 메모이제이션 활용 if (fibodata[n] != 0) { return fibodata[n] } // 메모이제이션, 종료 조건 else if (n <= 2) { fibodata[n] = 1 return 1 } // 메모이제이션, 일반항 else { fibodata[n] = fibonacci(n - 1) + fibonacci(n - 2) return fibodata[n] } } val result = fibonacci(n) println(result) ``` ### 최장 증가 부분 수열 부분 수열이란 주어진 수열 중 일부를 뽑아 새로 만든 수열을 말한다. 이때 각각의 원소는 전후 관계를 유지해야 한다. LIS(Long Increasing Subsequence, 최장 증가 부분 수열)이란 부분 수열의 원소가 오름차순을 유지하면서도 길이가 가장 긴 수열을 말한다. 동적 계획법으로 LIS의 길이를 구해보자. LIS에는 다음과 같은 특징이 있다. 1. 숫자가 점점 증가함 2. 원소 간의 전후 관계는 유지함 메모이제이션을 위한 dp 배열에 각 원소로 끝나는 LIS의 길이를 저장하고 마지막에 db 배열에 있는 값 중 가장 큰 값을 최종 LIS의 길이로 생각하면 된다. 정리하면 dp는 다음과 같다. * dp\[N] = arr\[N]을 마지막 원소로 하는 LIS의 길이 dp로 점화식을 세우면 다음과 같다. * dp\[N] = max(dp\[K]) + 1 (단, K는 1 <= K < N, arr\[K] < arr\[N]) * dp\[1] = 1 (종료 조건) ### 최장 공통 부분 수열 LCS(Longest Common Subsequence, 최장 공통 부분 수열)는 두 수열이 어떤 기준에 따라 양쪽에 공통으로 발견할 수 있는 긴 부분 수열을 의미한다. 그리고 부분 수열은 원소 사이의 순서만 유지하면 되고 반드시 연속할 필요는 없다. LCS의 길이를 구할 때는 2가지 조건을 검사해야 한다. 1. 두 문자열의 특정 문자가 같은지 2. 같다면 찾은 두 문자의 위치가 이전에 찾은 문자의 다음에 있는지 LCS의 길이를 반환하는 LCS() 함수를 다음과 같이 정의한다. * `LCS(i, j)` = `x[1...i]` 와 `y[1...j]` 의 LCS의 길이 * `x[i]` 와 `y[j]` 가 다르면 LCS(i, j) = LCS(i - 1, j) 와 LCS(i, j - 1)을 비교하여 큰 값으로 함 즉, LCS(i, j)의 점화식은 이렇게 정의할 수 있다. * `LCS(0, 0) = 0` * `x[i] == y[j]` 이면 `LCS(i-1, j-1) + 1` * `x[i] != y[j]` 이면 `max(LCS(i-1), j), LCS(i, j-1))` 총 연산 횟수는 dp를 채우는 것과 같으므로 O(N \* M) 이다. ## 문제 1. 피보나치 수 ### 설명 2 이상의 n이 입력되었을 때 n 번째 피보나치 수를 1234567로 나눈 나머지를 반환하는 solution() 함수를 완성하세요. ### 제약 조건 * n은 2 이상 100,000 이하인 자연수입니다. ### 입출력의 예 | n | return | | --- | ------ | | `3` | `2` | | `5` | `5` | 피보나치 수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다. ### 코드 ```kotlin fun solution(n: Int): Int { val fibodata = IntArray(n + 1) { 0 } fibodata[1] = 1 for (i in 2..n) { fibodata[i] = (fibodata[i - 1] + fibodata[i - 2]) % 1234567 } return fibodata[n] } ``` ## 참고 {% embed url="" %} 피보나치 수 {% endembed %}