반복문
function run(inputs: string) {
const n = Number(inputs);
const dp = Array(n + 1).fill(-1);
for (let i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + 1;
if (i % 3 === 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
if (i % 2 === 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
}
return dp[n];
}
- 최대 n번 계산을 반복하기 때문에 시간 복잡도는 O(n)
- 메모이제이션과 반복문을 사용한 DP는 재귀보다 효율적이다
재귀
function run(inputs: string) {
const number = Number(inputs);
const memo = Array(number + 1).fill(-1);
function go(num: number): number {
if (num === 1) return 0;
if (memo[num] !== -1) return memo[num];
let result = go(num - 1) + 1;
if (num % 3 === 0) result = Math.min(result, go(num / 3) + 1);
if (num % 2 === 0) result = Math.min(result, go(num / 2) + 1);
memo[num] = result;
return memo[num];
}
return go(number);
}
- 함수 호출을 사용하기 때문에 호출 오버헤드와 스택 깊이의 문제를 야기할 수 있다.
- 재귀함수는 깊어질수록 스택 메모리가 증가하고, 스택 오버플로우가 발생할 수 있다.
- 해당 코드는 제출 시 런타임 에러(StackSizeExceeded)가 발생한다.
반복문을 사용한 동적 계획법(DP)의 장점
- 반복문을 사용하는 방식에서는 호출 스택을 사용하지 않는다.
- 루프는 상수 메모리만을 사용하며, 모든 계산된 값은 배열 같은 외부 저장소에 저장되므로 스택 프레임에 추가되지 않는다.
- 반복문은 루프 변수만을 사용하기 때문에 상수 공간을 유지하며 동작한다. 즉, 반복문 자체는 스택 프레임을 쌓지 않기 때문에 호출 깊이에 따른 메모리 증가가 없다.