javaScript 1부터 n까지 숫자를 이용해 주어진 숫자 n 구하기

문제 

숫자 n이 주어질 때 1,2 만 사용하여 주어진 숫자 n을 구할 수 있는 경우의 수

풀이 

function solution(n) {
    let a = 1, b = 2;

    for (let i = 3; i <= n; i++) {
        [a, b] = [b, (a + b) % 1234567];
    }

    return n === 1 ? 1 : b;
}

• 주어진 초기값 a와 b를 사용하여 반복문을 통해 새로운 값을 계산후 최종적으로 계산된 값을 반환 
• 1234567은 상수를 선언하는 js 코드, 
• [a, b] = [b, (a + b) % 1234567
  • (a + b) % 1234567은 중간 결과를 1234567로 나눈 나머지를 취한 값으로 큰 수를 다룰 때 오버플로우를 방지하고 값을 작게 유지하기 위한 것 
  • for 루프를 통해 i가 3부터 n 까지 반복하면서 수열 갱신 
• n의 값에 따라 반환 

다른 풀이

function jumpCase(num) {
  if (num === 1) return 1
  if (num === 2) return 2
  return jumpCase(num-1) + jumpCase(num-2)
}

• 재귀 호출
  • jumpcase(num - 1)  + jumpcase (num - 2)를 통해 현재 위치에 도달하는 방법의 수 계산 
  • 이전 두 위치에 도달하는 방법의 합
• 재귀 호출을 통해 문제를 해결하고 있지만, 중복계산이 많이 발생할 수 있다. 
• 시간복잡도를 가져, 큰 입력에 대해는 효율적이지 않음

function jumpCase(num, memo = {}) {
  if (num === 1) return 1;
  if (num === 2) return 2;

  if (!memo[num]) {
    memo[num] = jumpCase(num - 1, memo) + jumpCase(num - 2, memo);
  }

  return memo[num];
}

function solution(n) {
    const MOD = 1234567;
    const dp = [0, 1, 2];

    for (let i = 3; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
    }

    return dp[n] % MOD;
}

• dp 초기화 
  • 도달 가능한 각 위치에 대한 방법의 수 저장하는 배열 dp 초기화
  • n이 4일때 예시

for 루프가 3부터 시작하여 i가 4까지 반복됩니다.

i = 3:

현재 dp 배열: [0, 1, 2, _] (아직 dp[3] 값이 없음)
dp[3] 계산: dp[3] = dp[2] + dp[1] = 2 + 1 = 3
갱신된 dp 배열: [0, 1, 2, 3]
i = 4:

현재 dp 배열: [0, 1, 2, 3, _] (아직 dp[4] 값이 없음)
dp[4] 계산: dp[4] = dp[3] + dp[2] = 3 + 2 = 5
갱신된 dp 배열: [0, 1, 2, 3, 5]

최종적으로 dp[4] 값을 MOD로 나눈 나머지를 반환합니다.
dp[4] % MOD 계산: 5 % 1234567 = 5