Dynamic Programming

개념

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

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

1. 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장해야 한다.

2. 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성할 수 있어야 한다.

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

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

1. 문제를 해결하는 해가 이미 있다고 가정한다.

2. 종료 조건을 설정한다.

3. 과정 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)

최장 증가 부분 수열

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

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, ... 와 같이 이어집니다.

코드

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

참고

https://school.programmers.co.kr/learn/courses/30/lessons/12945school.programmers.co.kr

피보나치 수