[JavaScript/section 10] 01 - 계단오르기

📌 01 - 계단오르기(동적 계획법)

철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2로 5가지이다.

그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?

 

📝 풀이 방법(DFS, DP)

DFS 알고리즘을 사용하여 문제를 풀어보았다. 정답은 훌륭하게도 잘 나온다 👍

하지만 n의 값이 커진다면...❓ 연산 횟수가 기하급수적으로 증가하게 된다.

이를 해결할 수 있는 방법으로 동적 계획법(dynamic programming, DP)이 존재한다.

function solution(n) {
  let answer = 0;

  function DFS(sum) {
    if (sum > n) return;
    if (sum === n) answer++;
    else {
      for (let i = 1; i <= 2; i++) {
        DFS(sum + i);
      }
    }
  }

  DFS(0);
  return answer;
}

console.log(solution(7));

 

동적 계획법(dynamic programming, DP)

어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘이다.

주어진 부분 문제의 정답을 한 번만 계산하고 저장(메모)해둔 뒤 다시 한 번 이 부분 문제를 이용할 때에는 저장해둔 정답을 바로 산출하여 이용함으로써 속도를 향상시킨다❗

• 총 7계단을 오르기 위한 문제를 더 작은 문제로 나누어 1계단과 2계단을 오르기 위한 경우의 수를 먼저 구한다.
• 3계단을 오르기 위해서는 1계단에서 두 계단을 오르던지 2계단에서 한 계단을 오르면 된다.
• 그렇기 때문에 3계단을 오르기 위한 경우의 수는 1계단을 오르기 위한 경우의 수와 2계단를 오르기 위한 경우의 수를 더해주면 된다. 
• 다음과 같이 dy[i] = dy[i-2] + dy[i-1] 와 같은 관계식을 만들 수 있다.
• 결론적으로 dy[3]을 구하기 위해서 dy[1]과 dy[2]를 이전에 연산을 해두고 저장해둔 배열에서 산출하여 이용함으로써 연산 속도를 향상시킬 수 있다.

function solution(n) {
  let answer = 0;
  let dy = Array.from({ length: n + 1 }, () => 0);

  dy[1] = 1;
  dy[2] = 2;
  for (let i = 3; i <= n; i++) {
    dy[i] = dy[i - 2] + dy[i - 1];
  }
  answer = dy[7];

  return answer;
}

console.log(solution(7));

 

💻 참고 사이트

동적 계획법 - 나무위키