1. 피보나치 수는 n번째 자리의 수는 n-1번째 자리의 수와 n-2번째 자리의 수의 합과 같다. 2. n은 0또는 10,000이하의 자연수이다. 3. n이 5,000일 경우를 생각해보면 아래와 같이 엄청 큰 단위의 수가 나오기 때문에 JavaScript에서 Integer형의 범위를 벗어나기 때문에 BigInt 를 사용해야한다.
이 문제의 관건은 다른 조건보다는 동적계획법,DP 을 코드로 구현할 수 있는가 였다.
"동적계획법" 패러다임이름에서 의 "동적"이라는 말은 이 개념이 매우 어렵지 않을까 하는 편견을 만들었고 실제로 어떤게 정확히 동적계획법인지를 이해하는데 처음에는 시간이 필요했다. 메모이제이션은 무엇이며, 반복적으로 똑같은 해결책으로 최선책을 찾아나간다는 것이 잘 이해가 가지 않았는데, 동적 계획법이라는 패러다임을 학습하던 동적 계획법은 쉽게 이야기하자면 "기억하며 풀기" 라는 말이 있었다.
이 말을 보고 다시 메모이제이션과 해결 과정을 보니 결국 데이터를 계산으로 구한 해를 저장해두고 다음 계산에서 활용 할 수 있게 해준다는 설명이 이해가 갔다.
🔍코드
const n = +require("fs").readFileSync("/dev/stdin", "utf-8").trim();
const memo = new Array(n + 1).fill(0);
const fibo = (i) => {
if (i <= 1) return i;
if (memo[i] !== 0) return memo[i];
return (memo[i] = fibo(i - 1) + fibo(i - 2));
};
console.log(fibo(n));
처음에 제출한 코드이다. 예제 입력값으로 주어진 10을 넣으면 계산을 통해 55가 출력됨을 알 수 있었다.
먼저 n에 입력값을 선언하고, 이 문제는 n이 0인경우도 존재하기 때문에 피보나치 수열의 10번째 값을 출력하려면 n+1 개의 메모이제이션 공간이 필요했다. 그렇기 때문에 n+1크기의 배열로 메모이제이션 공간을 할당했고 그 아래 피보나치 수열 함수를 선언하며 동적계획법 패러다임을 적용했다. 하지만, 이 코드를 제출하니 실패가 나왔다.
왜 그런가 고민하던중 위에는 성공후 조건을 적어서 있지만, n의 값이 10,000 이하까지 입력 가능함을 보고 입력값이 큰 경우, 출력 값이 Integer의 범위를 벗어 남을 알게 되었다.
const n = +require("fs").readFileSync("/dev/stdin", "utf-8").trim();
const memo = new Array(n + 1).fill(0);
const fibo = (i) => {
if (i <= 1) return BigInt(i);
if (memo[i] !== 0) return memo[i];
return (memo[i] = fibo(i - 1) + fibo(i - 2));
};
console.log(`${fibo(n)}`);
출력값이 Integer 범위를 넘어서는 경우를 대비해 BigInt형으로 형변환을 진행했고, 제출하니 성공이 나왔다.
하지만, 패스하고나서 10,000번째 수는 어떤 값일지 궁금하여 VSC 환경에서 10,000을 입력하니 아래와 같은 오류가 나오며 실행이 중단되는 문제가 있었다.
어떤 문제인지 궁금해 찾아보니 너무 많은 재귀함수의 호출로 인한 call stack 용량의 초과가 문제가 되었다.
이 경우는 메모이제이션을 사용한 하양식으로 접근하는 것보단, 타뷸레이션을 사용한 상향식으로 접근하면 문제가 해결된다.
🤖chatGPT 응답 정리
위의 코드는 통과는 했지만, VSC 상에서 콜스택 오버플로우 오류가 있다. 이것은 불필요한 재귀호출로 문제가 생길 수 있음을 예상할 수 있다. 추가로 개선안이 있는지 GPT에 코드 리뷰를 요청해보았다.
해당 코드는 큰 범위의 피보나치 수열을 계산하기 위한 메모이제이션 방식으로 작성되었습니다. 주어진 코드에서 주요 동작은 정확하게 이루어지지만, 성능과 효율성을 조금 더 개선할 수 있는 방법이 있습니다.
개선할 수 있는 점 1. 재귀를 반복문으로 변경 (타뷸레이션 방식 적용) 현재 코드는 재귀 방식으로 작성되어 있는데, 재귀 호출이 깊어질 경우 스택 오버플로우가 발생할 가능성이 있습니다. 특히, 큰 n 값에서는 불필요한 재귀 호출로 인해 성능이 저하될 수 있습니다.이를 반복문 방식으로 바꾸면 스택 오버플로우 문제를 피할 수 있고, 오히려 더 효율적일 수 있습니다. 반복문을 사용하면 호출 스택을 관리할 필요가 없으므로 성능도 향상될 수 있습니다.
2. 메모이제이션 배열 초기화 불필요 현재 memo 배열을 0으로 초기화하고 있는데, 사실상 배열을 사용할 필요가 없습니다. BigInt 타입의 연산은 두 개의 값만 기억하고, 이전 두 값을 업데이트하면서 계산해 나가면 충분합니다. 피보나치 수열은 오직 f(n-1)과 f(n-2)만을 이용하므로 배열을 사용할 필요가 없습니다.
3. 메모리 최적화 피보나치 수열은 이전 두 값만 필요하기 때문에 전체 값을 저장할 필요가 없습니다. 두 개의 변수를 이용하여 메모리를 크게 줄일 수 있습니다.
처음 이 문제를 풀 때 index가 0인 경우 0을 리턴하게 만들어야 하기 때문에 처음부터 n+1크기의 배열이 0으로 초기화 되어 있다면 별도로 작업하지 않아도 된다는 단순한 생각으로 초기화를 진행했는데, 어처피 위의 코드로 배열이 채워짐을 확인할 수 있었다.
개선된 코드
const n = +require("fs").readFileSync("/dev/stdin", "utf-8").trim();
const fibo = (n) => {
if (n <= 1) return BigInt(n);
let prev = BigInt(0);
let curr = BigInt(1);
for (let i = 2; i <= n; i++) {
const next = prev + curr;
prev = curr;
curr = next;
}
return curr;
};
console.log(`${fibo(n)}`);
상향식을 사용하면서 전체 값을 저장할 필요 없이 필요한 값만을 저장함으로, 결과에 필요하지 않은 캐시 메모리의 사용을 줄일 수 있다.
🔥배운점
동적 계획법을 공부하면서 단순히 메모이제이션을 이용하는 하양식을 사용해 알고리즘 문제를 풀어갔는데, 작은 값에서는 별다른 문제가 없었지만, 큰 값을 다루면서 콜 스택 오버플로우가 발생하는 문제를 겪고 큰 값을 다뤄야하는 경우는 상향식 타뷸레이션으로 접근하는 것이 메모리를 최적하 할 수 있음을 알았다.
검색을 하며 찾아봤을 때 대부분 메모이제이션으로 접근하는 DP를 설명해서 하향식에 익숙했는데 타뷸레이션과 반복문을 통한 상향식 접근법으로 알고리즘을 해결하는 연습을 해야겠다.
