동적 계획법
문제를 해결할 때 작은 문제부터 해결하여서 큰 문제를 해결하는 문제 풀이 방식이다.
백트래킹과 같이 특정 알고리즘이 아니고 문제 해결 방식이다. Dynamic Programming(DP)라고도 부른다.
메모리를 많이 사용하지만 빠른 성능을 보이므로 효율이 좋을 때가 있다.
동적계획법은 Memoization(하향식 접근법)과 Tabulation(상향식 접근법)으로 두 방법론이 있다.
Memoization (하향식 접근법)
작은 문제들의 결과를 메모리에 저장하고 이를 필요할 때 꺼내쓰는 방법이다.
기존 백트래킹 방식으로 문제를 해결하다보면 중복되는 탐색이 존재할 수 있다.
이럴 경우 해당 탐색 결과를 메모리에 저장해두고 중복이 발생하면 꺼내쓰는 방식이 Memoization이다.
- 피보나치 수열
f(n) = f(n-1) + f(n-2)이라는 규칙을 가지는 수열이다.
Memoization 방식을 적용하면 1, 2번째 결과값을 알고 있으면 그 이후 모든 결과값을 도출해낼 수 있다.
Tabulation (상향식 접근법)
필요한 값들을 미리 계산해두는 방식으로 문제를 해결하는 방식이다.
Memoization이 필요할 때 계산하는 것이라면 Tabulation은 미리 계산해둔다는 차이점이 있다.
코딩 테스트에서는 대부분 Memoization이 많이 사용된다.
동적계획법을 문제에 적용하는 방법
동적 계획법 유형은 딱 봐서는 동적계획법을 사용해야 하는지 파악하기가 어렵다.
따라서 문제가 다음과 같은 형태를 띄는지 확인해본다.
- 가장 작은 문제 또는 결과값이 존재하는지 알아본다.
- 1.의 작은 문제를 통해 확장되는 큰 문제가 있는지 그에 규칙이 존재하는지 알아본다.
위 두가지 조건이 만족한다면 동적계획법을 활용 가능하다.
하지만 활용가능하다고 반드시 동적계획법으로 해결할 수 있는 것은 아니다.
동적계획법은 메모리를 많이 사용하므로 시간복잡도가 초과되어 문제 해결이 불가능할 수도 있다.
이럴 경우에는 백트래킹으로 통해서 해결해야 하나 자주 출제되는 문제 유형은 아니다.
실습 문제 : 단어 퍼즐 (Lv 4)
동적 계획법 강의를 들었기에 작은 문제부터 찾아보았으나 1시간 동안 감을 잡지 못하였다.
괜히 레벨 4가 아니었다.
해설의 아이디어를 참고하여 문자열을 잘라 단어 퍼즐 유무를 확인하면서 기존에 구한 최소 갯수를 갱신하는 방식으로 해결하였다.
function solution(strs, t) {
// dp 배열 생성 t의 길이 + 1만큼
const dp = Array(t.length + 1).fill(0);
// 일반 배열보다 Set 객체가 탐색이 빠르다.
const sets = new Set(strs);
// 문자열 길이만큼 탐색
for (let i=1; i<t.length + 1; i++) {
// 최솟값을 구하므로 기본값은 무한이다.
dp[i] = Infinity;
// 문자열을 단어 조각만큼 자르면서 탐색한다.
for (let j=1; j < Math.min(i + 1, 6); j++) {
const start = i - j;
const end = i;
// 단어 조각이 이미 있으면
if (sets.has(t.slice(start, end))) {
// 이전 조합 + 1과 현재값 비교 후 최솟값 대입
dp[i] = Math.min(dp[i], dp[i-j] + 1);
}
}
}
return dp[dp.length - 1] === Infinity ? -1 : dp[dp.length - 1];
}- 다른 풀이
https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.4-%EB%8B%A8%EC%96%B4-%ED%8D%BC%EC%A6%90
같은 팀원의 검색으로 찾은 endswith 메서드를 활용한 해결 방법도 있었는데 정말 신박했다. 기존 방식은 문자열을 잘라 순회하는데 이 풀이는 비교적 작은 갯수의 요소를 가진 단어 퍼즐 배열을 순회하면서 극강의 효율성을 가진 코드였다.
😅 해당 내용은 공부하면서 정리한 글입니다. 틀린 부분이나 오해하고 있는 부분이 있다면 피드백 부탁드립니다.
