[코딩테스트] 1904 : 01타일 - 다이나믹 프로그래밍

◽️ 계기

오늘은 처음 보는 알고리즘을 접했다. 바로 다이나믹 프로그래밍! 뭔소리인지 몰라서 한참 검색하다가 감을 잡고 풀게 되었다. 다이나밍 프로그래밍 문제를 풀기 위해서는 먼저 점화식을 작성해야한다. 점화식이란 '수열에서 나타나는 패턴을 나타내는 방정식으로, 한 항의 값을 이전 항들의 값과의 관계로 표현한 것' 이라고 한다. (뤼튼이 알려줬다) 이 개념을 깨닫고 곰곰히 생각을 한 후 다음과 같은 점화식을 적을 수 있었다.

T[i] = T[i - 2] + T[i - 1]

다이나믹 프로그램을 구현하는 방식은 두 가지가 있다고 한다.

• Top-Down: 재귀적으로 구현
• Bottom-Up: 반복문으로 구현

이중에서 나는 반복문을 이용해서 구현해보았다. 출력은 잘 되는데 왜인지 백준에서 계속 틀렸다고 해서 다른 사람의 풀이를 보며 약간씩 고치긴 했지만 풀이를 맞춰서 뿌듯하다!

사실 다이나믹 프로그래밍을 몰랐을 때는 만들 수 있는 경우의 수 다 찾아서 배열 저장해두고, 배열을 2개의 인덱스씩 쪼갠다음 01, 10이 속한 배열 삭제후 count할까 생각했었는데 훨씬 좋은 방법이 있다는 것에 놀랐다. 너무 신기한 알고리즘을 배운 하루.. 뿌듯😚

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim();
const n = Number(input); //길이

let memo = new Array(n + 1).fill(0); //경우의 수 저장
memo[0] = 0;
memo[1] = 1;
memo[2] = 2;

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

console.log(memo[n]);