Dynamic Programming

큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법

동적 프로그래밍(DP)란 문제를 한번에 풀기 어려워 그 문제를 작은 단위로 쪼개어 그 단위에 대한 답을 구한 후 그 답들을 더해가며 점화식을 도출함으로써 최종적으로 문제를 해결하는 방식을 의미한다.

핵심은 작은 단위로 쪼개었을 때, 그 답을 어떤 배열에 기록해 놓고 그 답을 찾아가는 과정에서 점화식을 찾아내는 것이 핵심이다.

DP의 특성

1. 최적 부분 구조 (Optimal Substructure)

큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 경우를 의미한다.

2. 중복되는 부분 문제 (Overlapping Subproblem)

동일한 작은 문제를 반복적으로 해결해야 하는 경우를 의미한다.

문제

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

입력설명

첫째 줄은 계단의 개수인 자연수 N(3≤N≤45)이 주어집니다.

출력설명

첫 번째 줄에 올라가는 방법의 수를 출력합니다.

입력 예제

7

출력 예제

21

과정

다리는 3번 계단 부터 n번 계단 까지이기 때문에 1, 2번 계단은 미리 구한 후 dy 배열에 초기화 시킨다.

3번 계단의 경우 1번 계단이 올라갈 수 있는 경우의 수 + 2번 계단이 올라갈 수 있는 경우의 수의 합이다. (그림 참고)

값이 나올 경우 dy에 기록 한다.

이를 i번째 계단 까지 반복하다 보면 dy[i] = dy[i - 2] + dy[i - 1]의 점화식이 도출되는 것을 확인할 수 있다.

이때, 이 마지막 요소가 답이 되는 것을 확인할 수 있다.

코드

function solution(n) {
  // dynamic array 생성
  let dy = Array.from({ length: n + 1 }, () => 0);
  let answer = 0;
  // 1번째 계단, 2번째 계단은 미리 초기화
  dy[1] = 1;
  dy[2] = 2;
  // 계단의 개수인 3 ~ n 까지 순회 -> 도출한 점화식을 통해 n번째 까지 dy에 값 할당
  for (let i = 3; i <= n; i++) {
    dy[i] = dy[i - 2] + dy[i - 1];
  }
  // dy 배열의 가장 마지막 요소를 answer에 추가
  answer = dy[n];
  return answer;
}

console.log(solution(7));