Fact
- 오늘 프로그래머스 문제 두개를 도전했다. 하나는 멀리 뛰기. 하나는 거스름돈 . 둘다 혼자 힘으로 풀지 못했다. 첫번째 문제 멀리뛰기는 dp 문제였다. 동적계획법 중 하나인 bottom-up 계획법으로 문제를 풀었다. 솔직히 말해서 그냥 dp라고 해서 대충 코드 때려 보니 통과 됬다. 왜 통과 되는지는 모르겠다. 두번째 것은 이해를 아예 못해서 그냥 따라 쳐서 뜯어봤다. 뜯어봐도 왜 되는지 모르겠다 ㅋㅋㅋ…
- 오랜만에 코어 자바를 보면서 자바 공부를 다시 시작했다.
Feeling
- dp문제들은 뒤지게 피토하는 문제들이다.
- 어제 부터 허리 아파 뒤지겠다. 나 허리 디스크 초기? ㅋㅋㅋㅋㅋ
Findings
- 동적계획법의 핵심은 큰 문제를 잘게 나눠서 푸는게 핵심이다.
메모이제이션
- 동적계획법 알고리즘의 중 하나는 이항 계수 계산법이다.
출처: https://coding-all.tistory.com/2 [all about coding]
위 그림 보듯이 dp는 거쳐 갔던것을 저장 함으로써 함수 호출을 줄이면서 중복 계산을 제거하고 효율을 높인다. 이것을 메모이제이션이라고 한다.
이것을 하기 위해서
top-down 과 bottom-up 기법이 있다.
top-down은 위에서 부터 계산 해서 결과값을 얻는 방법이다. top-down은 보통 재귀 방식으로 얻는다.
const fibonacci = (n) => {
if(n === 1 || n === 2 ) {
return 1;
}
if(fibo[n]) {
return fibo[n];
}
fibo[n] = fibonacci(n-1) +fibonacci(n-2)
return fibo[n];
}bottom-up는 밑에서 부터 위로 계산 하고 결과값을 얻는 방법이다.
const fibonacci = (n) => {
let fibo = new Array(n);
fibo[0] = 0;
fibo[1] = 1;
for (let i = 2; i <= n; i++) {
fibo[i] = (fibo[i - 1] + fibo[i - 2]);
}
return fibo[n];
}Future Action
- dp… 흠 안되면 될 때까지!…는 너무 비효율적이고 적당히 다시 도전해보도록 하자. dp뿐만 아니라 다른 것들도 너무 비효율적이라고 생각하면 그때 멈춰서 빠른 재고가 필요하다.