코딩테스트 - DP

개념

• 이전의 값을 재활용 하는 알고리즘
• 예시 : 1~10 숫자 중, 각각 이전값들을 합한 값 구하기
• 이전의 값을 활용해서 시간복잡도를 줄일 수 있음
• 점화식을 세워야하는게 키포인트
• 처음부터 대입해보면서 점화식을 찾아라

문제 : 11726

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
ex)
input:
9
output:
55

• 아이디어

  • A1:1, A2: 2, A3: 1+2
  • An = A(n-1)+A(n-2)
  • for문으로 3부터 N까지 돌면서
  • 이전값과, 그 이전값을 더해서 저장(이때 10007로 나눈 나머지 값)

• 시간복잡도

  • for: N> O(N)

• 자료구조

  • 방법의 수 배열 : int[]

코드

//DP
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", function (line) {
  input.push(line);
}).on("close", () => {
  /*
1. 아이디어
- 점화식 : An = An-1 + An-2
- N값을 구하기 위해, for문 3부터 N까지의 값을 구하기
- 이전값, 이전이전값 더해서, 10007로 나눠 저장

2. 시간복잡도
- O(N)

3. 자료구조
- DP값 저장하는 (경우의수) 배열 : int[]
- 최대값 : 10007 보다 작음
  */

  const n = parseInt(input[0]);
  const res = [0, 1, 2];

  for (let i = 3; i <= n; ++i) {
    res.push((res[i - 1] + res[i - 2]) % 10007);
  }

  console.log(res[n]);
});

알아야할것

• 어떻게 할지 모르겠을땐, 하나씩 그려보면서 규칙 찾기
• 점화식을 명확하게 세우고 코드 짜기