Dynamic Programming

1. 개념

---

동적 계획법(Dynamic Programming)은 전체 문제를 한 번에 해결하는 것이 아니라 작은 부분 문제들을 해결하고, 이것들을 활용하여 전체 문제를 해결하는 방법이다.

동적 계획법을 효율적으로 활용하려면 아래 두 가지 조건을 만족해야 한다.

1. 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장해야 한다.
2. 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성할 수 있어야 한다.

1.1. 점화식 세우기와 동적 계획법

---

동적 계획법으로 문제를 해결하는 절차는 다음과 같다.

1. 문제를 해결하는 해가 이미 있다고 가정한다.
2. 종료 조건을 설정한다.
3. 과정 1, 2를 활용해 점화식을 세운다.

1.2. 피보나치 수 구하기

---

다음과 같이 재귀에 메모이제이션을 조합해보자.

1. 메모이제이션을 위한 저장소 생성 : 이미 구한 해를 저장할 공간 생성
2. 재귀 함수 정의 : 점화식을 재귀로 표현할 함수를 정의
3. 재귀 함수의 종료 조건을 정의 : 피보나치 수의 첫 번째, 두 번째 수는 1로 정해져 있으므로 메모이제이션 저장소에 해를 미리 넣어두고 종료 조건으로 생각한다.
4. 재귀 함수의 일반 연산 처리 : 동적 계획법에서는 점화식으로 나머지 문제를 처리한다. 그 과정에서 구한 결괏값은 메모이제이션 저장소에 저장한다.

우선 점화식을 재귀와 메모이제이션으로 어떻게 구현할지에 대한 의사코드를 작성한다.

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] 반환

피보나치 구현 코드

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)

1.3. 최장 증가 부분 수열

---

부분 수열이란 주어진 수열 중 일부를 뽑아 새로 만든 수열을 말한다. 이때 각각의 원소는 전후 관계를 유지해야 한다.

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 (종료 조건)

1.4. 최장 공통 부분 수열

---

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) 이다.

2. (문제) 피보나치 수

---

2.1. 설명

---

2 이상의 n이 입력되었을 때 n 번째 피보나치 수를 1234567로 나눈 나머지를 반환하는 solution() 함수를 완성하세요.

2.2. 제약 조건

---

• n은 2 이상 100,000 이하인 자연수입니다.

2.3. 입출력의 예

---

n	return
3	2
5	5

피보나치 수는 0번째부터 0, 1, 1, 2, 3, 5, … 와 같이 이어집니다.

2.4. 코드

---

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]
}

Reference

---

Programmers: 피보나치 수