다이나믹 프로그래밍 (1)

* 주의 : 다이나믹 프로그래밍과 다이나믹, 프로그래밍은 아무런 관계없습니다.
처음 이 알고리즘을 만든 분에 따르면 단지 멋있어서 지으셨다는 이야기가 있네요.ㅎㅎ(믿거나 말거나)

 

중복된 연산을 줄이는 방법으로 사용된다.

여기서 우리는 어떻게 중복된 연산인지 알 수 있을까? 에 대해 생각할 수 있다.

 

모든 문제들이 중복된 연산이 있는것도 아니고... 
어떻게 파악을 해야할까?

많은 방법이 있겠지만... 그 전에 한 가지 공식을 살펴볼 것이다.
이 공식은 고등학교 시절때 배운 공식 중 하나로 등차 수열이라는 공식이다.

등차 수열은 일반적으로

1 3 5 7 9 ..... 이런식으로 증감의 형태로 진행이 되는 특징을 가지고 있다.

우리는 이 식의 점화식을 세울 수 있는데..

점화식은 x = 2x+1이 된다. 왜 이렇게 되는지는 설명하지는 않겠지만... 아무튼..
이 점화식이라는게 다이나믹 프로그래밍에서 굉장히 중요하다.

 

다이나믹 프로그래밍의 특징을 하나 살펴보면

        1. 큰 문제를 작은 문제로 나눌 수 있다고 한다.
        2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

이렇게 나와있다. 그러면 여기서 큰 문제라는 게 뭐고, 작은 문제라는게 뭘까?

여기서 문제는 숫자다. 즉, 큰 문제라는 뜻은 값이 큰 숫자를 말한다. 

예를들어 이 점화식에서 50000번째 값을 계산한다면?

저 점화식에 넣으면 된다.

바로 2*50000 + 1 즉, 100,001가 된다. 또, 작은 문제라는건 3,5같이 작은 숫자들을 말한다.

우리는 1,3,5이렇게 3가지 숫자로 100,001이라는 숫자를 구할 수 있다. 실제로 답도 맞다. 

아무튼 우리는 점화식을 이용해서 작은 문제를 큰 문제를 해결하는 방법을 배웠다.

 

근데, 프로그래밍에서는 어떻게 사용할까? 단순히 변수로만 사용해서는 값을 구할 수 없을 것 같다.

왜냐하면 위 점화식 x = 2x+1같은 경우 뒤에 있는 x는 사실 x-1이다.

그러면 식을 다시 작성하면 x = 2(x-1) +1 이 된다.

아 실수 했다.

정정하겠다. d(x) = 2 * d(x-1) +1 가 된다.

x-1에는 x의 전값을 넣는다. 그러면 전 값은 어떻게 알 수 있을까?

프로그래밍에는 배열이라는 자료구조가 존재한다. 그것을 이용하면 어떨까?

재귀를 이용할 수 도 있겠지만, 일반적인 재귀를 사용할 경우, 중복된 코드가 발생하게 된다.

여기에서는 재귀는 사용하면 안된다는 정도만 알고 있는게 좋을 것 같다.
(사실 가능하지만 설명을 위해)

우리는 배열에 값을 저장하고,

저장 된 값을 호출해서 다시 사용하는 방식이 바로 다이나믹 프로그래밍이라는 사실이라는것을 알 수 있다.

즉, 다이나믹 프로그래밍은 점화식을 구하는 알고리즘이라고 해석이 될 수 있을 것 같다.