Programmers - 피보나치수
💡 What Is Dynamic Programming and How To Use It 영상을 참고하였습니다.
by CS Dojo
- Recursion(재귀함수)
- Memoization(메모이제이션: 동일한 연산을 반복할 때 값을 저장)
- Bottom-Up(트리구조-bottom-up)
1. Recursion(재귀함수)
처음에 피보나치란 단어를 보자마자 아래와 같이 코드를 바로 작성해서 제출을 했었다.
const fibonacci = (n) => {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
역시 제출하니 10문제 중에서 7번부터 모두 실패와 런타임 에러가 나타났다. 재귀함수의 깊이가 너무 깊은게 문제였나 싶었다. 위에 작성한 함수의 시간복잡도를 생각해보면 으로 굉장히 비효율적이다.
2. Memoization(메모이제이션: 동일한 연산을 반복할 때 값을 저장)
그래서 다음으로 시도를 해본 것은 Memoization이다. 재귀호출이 반복되면 불필요한 계산들이 수없이 반복되고 수가 1000으로만 커져도 recurion error가 발생할 것이다. 중간에 계산된 값들을 저장해서 필요할 때 참조하는 방법이 바로 Memoizaiton이다. 코드는 아래와 같다.
const memoizationFibonacci = (n, memo = []) => {
let result = 0;
if (memo[n] !== undefined) {
return memo[n];
}
if (n <= 1) {
result = n;
}
else {
result = memoizationFibonacci(n - 1, memo) + memoizationFibonacci(n - 2, memo);
}
memo[n] = result;
return result;
} // O(2n + 1)
memo란 list를 이용해서 중간에 새로운 값들을 저장하는 것이다. 이 방법의 시간복잡도는 이다. 그 이유는
if (memo[n] !== undefined) {
return memo[n];
}
위 코드블럭이 작동할 경우는 1번이다. 그리고 아래 코드블럭이 작동할 경우는
if (n <= 1) {
result = n;
}
else {
result = memoizationFibonacci(n - 1, memo) + memoizationFibonacci(n - 2, memo);
}
memo[n] = result;
return result;
번이다. 그리고 result = memoizationFibonacci(n - 1, memo) + memoizationFibonacci(n - 2, memo);
이 line을 읽게 되면 최대 2번 작동하기 때문에 시간복잡도는 이 된다.
3. Bottom-Up(트리구조-bottom-up)
마지막으로 Bottom-Up 방법이다. 흔히 동적프로그래밍이라 알려져있다. 피보나치 수열을 트리구조로 그려봤을 때 n이 5라고 가정을 하고
fib_1() -> fib_2() -> fib_3() -> fib_4() -> fib_5()
와 같이 탐색을 하면 총 n번이 소요된다. 따라서 하나의 배열안에 1부터 n까지의 결과를 저장해 원하는 값을 찾는 것은 크기 n인 배열을 한번 순회하는 것이다. 코드로 작성하면 아래와 같다.
const bottomupFibonacci = (n) => {
if (n <= 1) {
return n;
}
let bottomupList = [];
bottomupList[0] = 0;
bottomupList[1] = 1;
// for loop to n
for (let i = 2; i <= n; ++i) {
bottomupList[i] = bottomupList[i - 1] + bottomupList[i - 2];
}
return bottomupList[n];
} // O(n) : travel only once
0 과 1은 이미 주어진 상태이므로 for문은 2부터 n까지 진행한다. 이렇게 하면 시간복잡도 에 해당하는 가장 빠르게 피보나치 수를 구할 수 있다.
하지만 위에 있는 코드로 답안을 제출한다면 정답으로 인정이 안될 것이다. 위에 코드에서 아래와 같이 수정을 해주어야한다.
bottomupList[i] = bottomupList[i - 1] % 1234567 + bottomupList[i - 2] % 1234567;
피보나치 연산에 있어서 큰 수가 오게되면 런타임에러
라고 하면서 멈출 것이다. 그래서 나머지 연산을 추가해주었다.
Author And Source
이 문제에 관하여(Programmers - 피보나치수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@seunghwanly/Programmers-피보나치수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)