[동적계획법]계단오르기

문제

철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 (1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 2 + 2) 로 5가지이다.그렇다면 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇가지인가?

 

코드

function solution(n) {
  let answer = 0;

  function DFS(sum) {
    if(sum > n) return; //cut-edge
    if(sum === n) {
      answer++;
      return;
    } 
    else {
      DFS(sum + 1);
      DFS(sum + 2);
    }
  }

  DFS(0);

  return answer;
}

console.log(solution(7));

 

오답

해당 문제는 깊이 탐색으로 푸는 것이 아닌 동적계획법을 사용해서 푸는 것이었다.

 

동적계획법(Dynamic Programming)

• 전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용하여 전체 문제를 해결하는 방식
• 전체 문제를 작은 문제로 단순화 => 부분 문제를 정의
• 재귀적인 구조를 활용할 수 있는 점화식을 만듬 => 부분 문제에서 분석된 내용 토대로 점화식 도출
• 메모이제이션(Memoization)은 동적계획법에서 반드시 필요함

동적계획법

 

코드

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[n];
  return answer;
}

console.log(solution(7));