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

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

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

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

 

1. 일반적인 재귀 방법

html

닫기 줄바꿈

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

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

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

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

html

닫기 줄바꿈

// 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. 다이나믹 프로그래밍 일반 형태

html

닫기 줄바꿈

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

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