사이트: HackerRank
난이도: 미디움
분류: Dynamic programming
기존 피보나치 수열을 변환하여 새로 만든 규칙을 적용하려고 한다. 새로 만든 피보나치 규칙은 다음과 같다.
t[i + 2] = t[i] + (t[i + 1]^2)
아래 예시를 한번 살펴보자.
t1 = 0
t2 = 1
n = 6
t3 = 0 + (1^2) = 1
t4 = 1 + (1^2) = 2
t5 = 1 + (2^2) = 5
t6 = 2 + (5^2) = 27
BigInt
를 사용할 수 없는 환경이라서 일단 BigInt
를 처리하는 것은 제외하고 작성해 보았다. 피보나치 수열은 전형적인 dp
로 해결할 수 있는 문제라서 어렵지 않게 작성했다.
function fibonacciModified(t1, t2, n) {
// Write your code here
const dp = [t1, t2];
for (let i = 2; i < n; i++) {
dp[i] = dp[i - 2] + Math.pow(dp[i - 1], 2);
}
return dp[n - 1];
}
해당 문제를 풀고 다른 사람들의 풀이 방법이 궁금해서 찾아봤는데, 공간 복잡도
조건도 같이 부합해야 한다는 내용을 보게 되어 위 로직을 수정해 보았다.
설명에서는 시간 복잡도
와 공간 복잡도
를 각각 아래와 같이 표현하였다.
Time complexity: O(n)
Space complexity: O(1)
수정된 로직은 아래와 같다.
function fibonacciModified(t1, t2, n) {
// Write your code here
let t3 = t1 + Math.pow(t2, 2);
for (let i = 2; i < n; i++) {
t3 = t1 + Math.pow(t2, 2);
t1 = t2;
t2 = t3;
}
return t3;
}
알고리즘 문제를 작성하면서 공간 복잡도를 계산하는 방식이 익숙하지 않지만, t3
변수를 추가함으로써 O(3)
의 공간 복잡도를 가지고 상수는 1로 생략되기 때문에 총 O(1)
의 공간 복잡도를 가지게 하였다.
O(3)인 이유는 각각 t1, t2, t3 변수가 사용되기 때문이다.
기존 작성된 로직은 n
만큼 배열의 길이가 늘어나기 때문에 O(n)
공간 복잡도를 가지며, 수정된 로직을 사용하면 공간 복잡도를 개선할 수 있다.
바로 풀 수 있었던 문제들은 지금은 생략하고 추후 더 효율적인 문제 풀이법을 찾아보도록 하겠다.