DP(Dynamic Programing: 동적 계획법)에 대해 이해해보자

코딩테스트 문제를 풀다 보면 꼭 걸리는 문제가 여러 개가 있다..

각자 고충이 있겠지만, 그 고충 중에는 "시간복잡도"가 있는 것은 꼭 있다.ㅠ

 

분명 코드를 알맞게 작성했지만, 소화해야할 데이터의 양,

그러니까 배열의 길이 등이 몇 십만 단위로 기하급수적으로 커지게 된다면, 

반드시 제한 시간 초과와 같은 실패를 직면하게 된다.

 

이전 글에서 index를 통해 테이블에서 원하는 레코드를 탐색할 때,

시간복잡도를 줄여준다는 내용을 적었다시피...

방대한 데이터를 다룰 때는 시간복잡도를 감소시키는 것은 굉장히 중요하다.

 

 

Dynamic Programing도 이런 시간 복잡도를 줄여주는 알고리즘 기법이다

동적 계획법은 하나의 큰 문제를 여러 개의 작은 문제로 나눈 다음,

작은 문제들을 해결해 결과를 저장하여, 결과로 큰 문제를 해결하는 설계 기법이다.

이렇게 말하면, 노 베이스에서 이 말을 아무도 이해 못하는 것은 당연하다.

나 또한 처음에는 무슨 도대체 무슨 말인지 몰랐으니까...

 

 

가장 많이 사용되는 예시, 피보나치 수열로 이해를 해보자!

피보나치 수열은 마치 나무의 가지치기, Tree(나무) 구조로 설명이 가능하다

 

여기서 조그마한 원들을 node라고 한다.

각 node는 항을 구하는 식인 만큼 동시에 위에서 말한 작은 문제 이기도 하다.

작은 문제인 각 node를 구해서 위로 올라가다 보면, 큰 문제인 F(5)를 구할 수 있다고 해석이 가능하다.

 

5번째 항을 구하는 데 저 만큼 가지치기, 즉 node가 필요하게 되는데..

5번째 항이라면 그나마 괜찮다. 하지만, 20번째 혹은 100번째 항을 구해야 한다면 어떻게 될까?

node는 무수히 많아지게 되고, 컴퓨터가 연산하는데 필요한 시간은 기하급수적으로 늘어나게 된다!

하지만 DP의 접근법을 사용하면, 그렇게 시간이 많이 걸리는 방법을 택할 필요는 없게 된다.

 

먼저 node 를 살펴보자 

빨간색의 F(1)

노란색의 F(2)

초록색의 F(3)

이 node들이 "반복한다"는 것을 알 수 있다.

 

따라서.. 작은 문제들을 풀 때, 반복되는 값의 경우, 미리 메모리에 저장을 한다면,

그리고 특정 node의 값이 필요로 할 때, 연산을 하지 않고, 저장된 내용을 꺼내서 쓰게 한다면?

불필요한 연산을 줄일 수 있게 된다!

 

 

이렇게 반복되는 문제를 효율적으로 푸는 것을 동적 계획법이라 한다.

 

 

이를 Javascript로 표현을 하면 다음과 같다:

// 피포나치 n번째 수열을 구하는 함수다.
function fibonacci(n) {
	// 1번째 혹은 0 번째 수열은 그 값이 동일하므로, n을 그대로 반환한다.
    if (n <= 1) {
        return n;
    }

	// 메모리에 저장될 수열이다. 맨 처음 0, 1이 저장되어 있다.
    let fib = [0, 1];
    // n번째 수열까지 2번째 부터 시작해서 for 문이 돌아간다.
    for (let i = 2; i <= n; i++) {
    	// n번째 수열은 앞의 n-1 번째, n-2 번째 수열의 합이다.
        // 두 수열의 합을 구한 후 n 번째 수열에 그 값을 저장한다.
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
}

 

 

참고로 동적계획법은 Bottom-up, Top-down이라는 두 가지 방식으로도 나눠진다.

위의 코드는 Bottom-up 방식이다.

이 부분까지 작성하려면 글이 길어져서 이만 마치려고 한다.

 

 

 

이 글을 작성하는데 큰 도움이 된 영상입니다.

출처: https://www.youtube.com/watch?v=lhZTYwHgrDM&t=1s