반복문

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)의 장점

• 반복문을 사용하는 방식에서는 호출 스택을 사용하지 않는다.
• 루프는 상수 메모리만을 사용하며, 모든 계산된 값은 배열 같은 외부 저장소에 저장되므로 스택 프레임에 추가되지 않는다.
• 반복문은 루프 변수만을 사용하기 때문에 상수 공간을 유지하며 동작한다. 즉, 반복문 자체는 스택 프레임을 쌓지 않기 때문에 호출 깊이에 따른 메모리 증가가 없다.