javascript - 다이나믹 프로그래밍 (Dynamic Programming)

투 포인터(Two Pointer) 알고리즘

다이나믹 프로그래밍은 큰 문제를 작은 문제들로 나눠서 해결하는 방법론입니다. 주로 반복되는 연산을 피하기 위해 이미 계산한 결과를 저장해두었다가 재활용하는 기법이 포함됩니다.

예시로 많이 들어지는 피보나치 수열을 살펴봅시다.

 

1. 일반적인 재귀 방법

function fib(n) {
	// 종료 조건이 없으면 무한 루프에 빠집니다.
    if (n <= 1) return n;
    
    // 실질적인 점화식 부분입니다.
    return fib(n - 1) + fib(n - 2);
}

하지만 이 방법은 n이 커질수록 중복해서 계산하는 경우가 많아져 비효율적입니다.

2. 다이나믹 프로그래밍 활용

중복된 연산을 피하기 위해 다이나믹 프로그래밍 기법을 사용하면 효율적으로 문제를 해결할 수 있습니다. 여기서는 메모이제이션 (Memoization)이라는 방법을 활용하겠습니다.

// memo라는 파라미터는 기본적으로 빈 객체로 설정되어 있습니다. 이 객체는 이전에 계산한 피보나치 수의 값을 저장하기 위해 사용됩니다.
function fib(n, memo = {}) {
    if (n in memo) return memo[n];
    
    // 만약 memo 객체 안에 현재 계산하려는 n번째 피보나치 수의 값이 이미 저장되어 있다면, 그 값을 바로 반환합니다. 이렇게 하면 중복 계산을 피할 수 있습니다.
    if (n <= 1) return n;
    
    // 피보나치 수열의 정의에 따라, n이 0이나 1일 때는 해당 값 그대로를 반환합니다.
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    
    //계산된 n번째 피보나치 수의 값을 반환합니다.
    return memo[n];
}

이 방법은 n번째 피보나치 수를 구할 때, 중복된 연산을 저장해두었다가 다시 사용하기 때문에 연산 시간을 크게 단축시킬 수 있습니다.

이처럼 다이나믹 프로그래밍은 큰 문제를 작은 문제로 나누어 풀고, 그 결과를 저장해두었다가 재활용하는 방식으로 문제를 효율적으로 해결할 수 있게 도와줍니다.

 

3. 다이나믹 프로그래밍 일반 형태

function dp() {
	1. 종료 조건
    2. 이미 해결한 문제라면, 정답을 그대로 반환
    3. 점화식에 따라 정답 계산
}

• 문제 이해하기
• 점화식 찾아내기 
• 구현방식(상향식/하향식) 결정하기
• 점화식을 실제 코드 구현하기