시작
오랜만에 알고리즘에 대한 문제가 나와서 재밌게 공부했다. 웹을 알기 전에는 3학년 내내 알고리즘만 공부했었다. 어쩌다보니 주변 환경으로 인해 여러 가지 유형을 공부한게 아니라 삼성에 나올 법한 문제들만 계속 공부했었다. 변명이다. 내 기준으로 Input에 비해 output이 좋지 않다보니 자연스럽게 알고리즘에 흥미를 잃었고 재미가 없었다. 결국엔 취업을 위해 억지로 꾸역꾸역 했고 취업과 동시에 아예 쳐다보지도 않았다.
근데 최근에 모던 자바 인액션 스터디를 통해서 흥미로운 문제가 있었다. 그냥 넘어가려 했으나 며칠 동안 계속 머리에 남아있었다. 그래서 정리하고자 한다.
피보나치 문제에 있어서 DP는?
간단한 예이다. fib(7)을 구하기 위해서는 fib(6) + fib(5) 에 대한 값을 알아야 한다. 그렇기 위해서는 fib(6)을 계산해야하고 fib(5)를 계산해야한다. 그 과정속에서 fib(6)을 구할 때, 또 다시한번 fib(5)를 구한다.
즉, fib(7)을 구할 때, fib(5)를 두번 계산을 하는 것이다.
이러한 두번의 계산을 없애고자 DP가 필요했다.
코드 결과 및 나의 생각
결과로 보면 답은 잘나온다. 근데 과연 이게 DP일까? 나는 궁금했다. 이런 고민이 생긴이유는 우선적으로 나는 항상 DP는 계산된 값을 어떠한 Container에 넣어두고 그 계산을 또 하고자할 때, 그 Container에서 이미 계산된 값을 꺼내와야 한다고 생각했다. 항상 그렇게 했기에.
그때 당시 이 코드를 봤을 때, 0과 1은 초기화의 목적이었고 다른 Contatiner가 보이지 않았기에 중복된 계산을 한다고 생각했다.
결과적으로는 DP다. 왜냐하면 fib(T) 를 구할 때, fib(T-1) fib(T-2)에 대한 값이 privious와 current에 임시적으로 저장이 되어있기에 이 코드드 DP가 맞다.
다만, 만약 코딩테스트와 같은 문제에서 Fib(5), fib(10) 과 같은 값을 연달아 구하고자 하는 문제가 나온다면 이러한 코드로 해결하지 못한다. 그때는 중복된 계산을 해야하기 때문이다.
물론 그것은 getAsInt Method에서의 값들을 Container를 만들어서 캐시의 용도로 해결할 수 있다. 또한, 구하고자 하는 피보나치 범위가 좁다면, 그냥 쌩 Look-up-table을 만들어서 사용할 수있다.
내가 왜 헷갈렸는가?
문뜩 계속 생각나서 시간내서 한번 고민을 해봤다. 정말 간단했다. 내가 헷갈린 이유는 코드와 생각 방식이 달랐기 때문이다.
int fibonacci(int n) {
if (n==0) return 0;
if (n==1) return 1;
if (dp[n] != -1) return dp[n];
dp[n] = fibonacci(n-1) + fibonacci(n-2);
return dp[n];
}
나는 항상 DP를 풀 때, Top-Down으로 문제를 풀었다. 그렇기에 Java코드인 Bottom-Up 방식에 거부감이 있었던 것 같다. 뭐... 별거 아니었다.
끝내며
오랜만에 알고리즘 공부를 하니까 재밌었다. 물론 아직까지 엄청 재밌는건 아니다. 오랜만이라. 내가 하고싶어서. 그래서 재밌었다. 어떠한 지식을 얻고자할 때, 강제성이 없이 본인이 스스로 얻으려 할 때 재밌는것 같다. 그래서 앞으로도 알고리즘을 재밌게 풀 수 있을 것 같다.
