hyeoneee's blog

동적 프로그래밍(Dynamic Programming)이 란?

작은 결과 값을 이용해 더 큰 결과값으로 올라가 구하려는 결과값을 얻어 내는 알고리즘

> 중복되는 것은 기억해 두어서 skip (메모이제이션)

대표적인 것으로 피보나치 수열이 있다.

f(x) = f(x-1) + f(x-2);

1,1,2,3,5,7,14,21 ... 34,55

단순한 피보나치 수열을 짠 코드는 

int fibo1(int n) {

if (n < 2) {

return 1;

}

return fibo(n - 1) + fibo(n - 2);

}

이렇게 된다.

하지만 이 과정에서 똑같은 작업이 중복되어 일어난다.

예를들어 5를 구할때

5 - 4 -3  -2

      -1

 - 2   

   - 3 - 2

   -1

3부터는 중복이 일어난다 

이러한 중복을 막기위해 쓰는 것이 메모이제이션이다.

한번 구했던 값이면 다시 구하지 않고 넘어가도록 !

구했던 값인지 체크하는 로직을 넣어주기만 하면된다.

메모이제이션이 적용된 피보나치 수열 코드이다.

int fibo(int n) {

if (dp[n] > 0) {

return dp[n];

}

if (n < 2) {

return dp[n] = n;

}

return dp[n] = fibo(n - 1) + fibo(n - 2);

}

가장 이해 하기 쉬운 예로 접하니 더 이해하기 좋다.

구한 값을 dp[n]에 넣어주니 dp[n]의 값이 0 보다 큰지만 체크해주면 된다! ( 그전에 구한 값인가~?)

이렇게 하면 쉽지만...

다른 문제들을 풀어보면 어렵더라 

다른 문제를 풀어 보고 더 적용해 봐야겠다.

그럼 이만

뿅!