[ 자바스크립트(JavaScript) ] section10 - 1 - 계단 오르기(DP)

📍 section10 - 1 - 계단 오르기(DP)

이번 섹션은 동적 계획 프로그래밍인(DP)에 대해서 배운다. (넷플릭스 DP 꿀잼 😁)

 

DP 문제는 직관적으로 분석하기 어려운데, 이 감을 키우려면 선생님께서는 역시 양치기 즉, 많은 문제를 풀어봐야 한다고 하셨다. DP문제들의 특징을 살펴보자.

 

1. DP는 큰 문제를 한 번에 풀기보다는 직관적으로 알 수 있는 단위로 잘게 쪼갠다.
2. 작은 단계부터 답을 dp에 저장하고, 범위를 점차 넓혀간다. 이때, 앞에서 사용한 값을 그대로 사용한다.
3. 직관적으로 알 수 있는 값은 dp에 저장하는데 보통은 dp[1]~dp[2] 정도이고 많으면 dp[0]~dp[3]정도까지 저장한다.
4. 작은 단계부터 경우의 수를 한번 세본다. (이후에는 어떻게 활용할지 고민하기!)
5. 이전 단계와의 관계식(점화식)을 만들어보자. 예를 들면 바로 앞의 항에 3을 더했더니 답이 되는 규칙(d[i]=d[i-1]+3) 등

 

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

 

N계단을 올라갈 때를 바로 생각하지 말고 계단을 1개 오를 때, 2개 오를 때처럼 낮은 단계를 먼저 생각해보자. 철수가 1계단을 오를 때 경우의 수는 1개이다. 그렇다면 2계단을 오를 때는 어떨까? 한 칸씩 오르는 방법과 두 칸을 한 번에 오르는 방법 총 2가지가 있다. 이때 그림으로 나타내면 다음과 같다.

 

 

그렇다면 3번째 계단을 오를 때는 어떨까? 3번째 계단을 오르는 방법은 1계단에서 한번에 올라가는 방법과 2계단에서 한 칸 올라가는 방법이 있다. 즉, 1계단에서 오르는 경우의 수 + 2계단에서 오르는 경우의 수가 된다. 하나만 더 해보자. 4번째 계단을 올라가는 방법은 어떨까? 일일이 세보는 것도 방법이 될 수 있다. 하지만 시간이 오래 걸린다. DP는 이전의 값을 참고하여 결과를 낼 수 있는 방법이다. 마찬가지로 2계단에서 한 번에 올라가는 방법과 3계단에서 한 칸올라가는 방법을 더해주면 된다. 이를 코드로 나타내면 다음과 같다.

 

let n = 7;

console.log(solution(n));

function solution(n){
  let d = Array.from({length: n+1}, () => 0);
  d[1] = 1;
  d[2] = 2;

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

  return d[n];
}

👉🏽 21

 

728x90

 

💡 번외: 계단을 3칸까지 오를 수 있다면?

만약에, 철수가 한번에 계단을 오를 때 1칸, 2칸, 3칸까지 올라갈 수 있을 때는 어떻게 구할까? 이전에 구했던 1칸, 2칸은 남겨두고 3칸을 어떻게 올라갈지 구해보자. 핵심적인 사고는 dp[3]이 어디서 왔는지를 떠올리면 된다. dp[3]은 dp[3-1]칸에서 가는 방법과 dp[3-2]칸에서 가는 방법이 있지만, dp[3-3]칸에서 한 번에 3칸을 건너올 수도 있다. 따라서 dp[0]=1 조건을 추가해줘야 한다. 코드는 다음과 같다.

 

let n = 5;

console.log(solution(n));

function solution(n){
  let dp = Array.from({length: n+1}, () => 0);
  dp[0]=1;
  dp[1]=1;
  dp[2]=2;

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

👉🏽 13