동적 계획법

동적 계획법 개념

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

A의 문제를 풀기 위해서 B, C, D, F의 과정을 한다면 동적 계획이라는 것이 아닙니다. D를 하기 위해서 B의 값을 재사용하는 형태로 문제를 풀어야 합니다.

동적 계획법을 문제로 풀이하는 절차는 다음과 같습니다.

예를 들어

Fin(N) 이라는 피보나치 값을 반환하는 함수가 있다고 가정합니다.
Fin(N)의 종료 조건을 알아냅니다. 피보나치는 N번째 수까지 더한 값을 반환합니다.
이제 Fin(N)부터 시작하여 피보나치 계산식을 쪼갭니다. 예를 들어 Fin(N)은 Fin(N-1)과 Fin(N-2)의 합으로 표현할 수 있습니다. 마지막으로 Fib(1)까지 가서야 더 쪼갤 수 없는 상태에 도달합니다.
그럼 다음과 같이 점화식이 그려집니다. Fib(N) = Fib(N - 1) + Fib(N - 2) (N > 2) Fib(1) = 1
N이 1이 되면 쪼개는 과정을 종료합니다. 앞에서 본 그림을 식으로 표현했다고 생각할 수 있습니다.

function Fib(n){
    if(n <= 2){
        return 1
    }
    
    return Fib(n - 1) + Fib(n - 2)
}

재귀 방식으로 점화식을 구현해보았습니다. 하지만 해당 함수는 스택 메모리에 재귀 호출한 함수들이 모두 쌓이는 부담이 있습니다. 그래서 반복되는 함수들을 메모이제이션해주는 것이 좋습니다.

메모이제이션은 이미 계산한 값을 저장해두었다가 이후 쓸 일이 있을 때 활용하는 개념입니다. 예를 들어 Fib(20)을 하게 될 경우 Fib(10)의 경우 여러번 호출이 됩니다. 이런 연산을 반복하지 않아도 바로 값을 가져올 수 있습니다.

주어진 수열 중 일부를 뽑아 새로 만든 수열을 말합니다.

수열의 원소가 오름차순을 유지하면서도 길이가 가장 긴 수열을 말합니다. 예를 들어 [1, 8, 6, 10, 13, 12]라는 배열이 있을 때 [1, 6, 10, 12] 숫자를 뽑았다면 이는 오름차순이 유지되므로 최장 증가 부분 수열 즉 LIS가 됩니다.

최장 공통 부분 수열은 LCS라고도 불립니다. 이는 두 수열에서 순서를 유지하면서 공통으로 나타나는 가장 긴 부분 수열을 의미합니다.

다음 배열로 예시를 보겠습니다.

const arr1 = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'];
const arr2 = ['A', 'D', 'D', 'I', 'C', 'T', 'E', 'F'];

이중 'A' 'D' 'E' 'F'는 순서의 길이가 같으므로 공통 부분 수열입니다. 그러므로 가장 긴 부분 수열이므로 LCS입니다.

Last modified: 16 August 2024