•
DP(동적 계획법)란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 의미한다.
•
DP 알고리즘은 메모이제이션 기법을 이용하여 효율적으로 답을 구하는 알고리즘이다.
•
DP 알고리즘을 이용하려면 문제의 재귀적인 구조(관계식)를 파악해야 한다.
•
문제의 재귀적인 구조가 없다면
◦
브루트포스, 그리디, 수학과 같은 다른 방식의 접근이 필요함
•
내가 생각한 DP 알고리즘이 타당한지 판단하는 법
◦
DP 관계식이 타당한지 판단
: DP Table의 정의에 대해 DP 관계식이 논리에 오류가 없어야 한다.
◦
초기값을 구할 수 있는지에 대한 판단
: DP Table의 초기값을 구할 수 있어야 한다.
•
Bottom-Up 방식과 Top-Down 방식 중에 뭐가 더 좋은가?
◦
대부분의 문제는 두 가지 방식 모두 사용할 수 있으므로 선호하는 방식으로 풀면 된다.
◦
DP Table 전체를 완성해야 하는 경우에는 Bottom-Up 방식의 풀이가 더 좋다.
◦
DP Table의 일부만 완성해도 되는 경우에는 Top-Down 방식의 풀이가 더 좋을 수 있다.
•
DP는 최적해를 구하는 알고리즘이므로 다음과 같은 경우에 많이 사용된다.
◦
~한 경우의 수를 구하시오.
◦
~의 최소값을 구하시오.
◦
~의 최대값을 구하시오.
BOJ_11048_이동하기_JS
•
DP 테이블에 저장할 값을 정의하기.
•
관계식을 찾으려고 노력하자.
◦
DP 테이블 설계는 주로 N에서 끝나는, N까지 살펴봤을 때
function solution(input) {
const [n, m] = input[0].split(' ').map(Number);
const map = input.slice(1).map((item) => item.split(' ').map(Number));
const dp = map.slice((item) => item.slice());
// 0행, 0열을 0으로 만들어준다면 초기화를 할 필요가 없다.
for (let i = 1; i < m; i++) dp[0][i] = dp[0][i] + dp[0][i - 1];
for (let i = 1; i < n; i++) dp[i][0] = dp[i][0] + dp[i - 1][0];
// Bottom-Up
for (let i = 1; i < n; i += 1) {
for (let j = 1; j < m; j += 1) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + dp[i][j];
}
}
return dp[n - 1][m - 1];
JavaScript
복사