동적계획법이란?
전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 전체 문제를 해결하는 방식
큰 의미에서 분할 정복과 같은 접근 방식을 의미한다.
→ 처음 주어진 ① 문제를 더 작은 문제들로 나눈 뒤 ② 각 조각의 답을 계산하고, ③ 이 답들로부터 원래 문제에 대한 답을 계산해 낸다.
동적 계획법과 분할 정복의 차이가 발생하는 부분은 문제를 나누는 방식이다.
→ 동적 계획법에서 어던 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에 값을 저장한 후, 같은 문제가 나왔을 경우 계산 결과를 재활용함으로써 속도의 향상을 꾀한다.
부분 문제(overlapping subproblems) : 두 번 이상 계산되는 부분 문제
그리디 알고리즘과 비교
우리가 차량 정체 구간에서 A라는 지점에서 B라는 지점까지 가능한 빨리 이동하는 경로를 찾고 싶다고 하자. 이 문제에서
동적 계획법
→ 우리가 갈 수 있는 모든 상황과 교통 정체를 전부 감안하여 최적의 경로를 찾아낸다.
- 단점
약간의 시간이 걸린다
- 장점
이렇게 얻어낸 경로는 (교통 환경이 변하지 않았다는 가정 하에) 우리가 갈 수 있는 가장 빠른 길이 된다고 장담할 수 있다.
그리디 알고리즘
→ 전체적인 상황을 고려하지 않고, 순간순간 교차로가 보일 때마다 가장 빠른 경로를 검색하여 찾아줄 것이다.
- 단점
항상 최적의 경로를 찾아주지 않는다.
→ 각 구간마다 최적의 경로를 찾는다고 해도 그것이 전체적으로 최적의 경로가 되지 않기 때문
- 장점
즉효성이 있다.
적용
- 완전 탐색 알고리즘 설계
- 문제를 여러 조각으로 나눈 후, 한 조각을 해결
- 나머지는 재귀 호출을 통해 해결
- 메모이제이션 - 최적화
동적계획법 문제가 풀리지 않을 때 '캐시를 어떻게 적용할지 몰라서 못 풀겠다'라고 생각하며 막막해 했다. 그런데 그것이 점화식을 만들지 못해 발생했던 문제였던 것 같다.
만약 최적화가 잘되지 않는다면 재귀적인 구조를 활용할 수 있는 '점화식'을 어떻게 작성할 것인지 고민해보자.
- 부분 문제 정의
- 점화식 작성
으로 생각하고 문제를 풀어 나가보자.
( 항상 초점을 어디에 맞추느냐에 따라 생각 방식이 많이 바뀌게 되는 것 같다. )
연습문제
최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용된다.
🔗 프로그래머스, 타일 장식물
타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다.
타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다.
[1, 1, 2, 3, 5, 8, .]
타일의 개수 N이 주어질 때, N개의 타일로 구성된 직사각형의 둘레를 return 하도록 solution 함수를 작성하시오.
풀이
- 부분 문제 정의
→ 한 변의 길이는? 이전 정사각형 두 개를 합한 변으로 만들어진 정사각형이다.
- 점화식 작성
🔑N번째 정사각형 변 = (N-1)번째 변 + (N-2)번째 변
class Solution { public long solution(int N) { long[] nArr = new long[N]; nArr[0] = 1; nArr[1] = 1; for(int i=2; i<N; i++){ nArr[i] = nArr[i-1]+nArr[i-2]; } long answer = (nArr[N-1]*2 + nArr[N-2])*2; return answer; } }- 부분 문제 정의
🔗 프로그래머스, 등굣길
집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.
가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.
격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.
풀이
- 부분 문제 정의
→ 경우의 수에서 경로 수 구하는 법을 떠올려보면,
시작점에서 1부터 시작하여 아래-오른쪽으로 뻗어나가면서 대각선에 있는 것끼리 더해 다음 만나는 지점의 경우의 수가 정해진다.
지나가지 못하는 곳은 0으로 더해나간다.
- 점화식 작성
🔑현재 있는 곳의 경로 수 = 이전 위의 경로 수 + 왼쪽의 경로 수
예외 혹은 조건들을 잘 걸러 주는 것도 중요하다.
import java.util.*; class Solution { public int solution(int m, int n, int[][] puddles) { int[][] cache = new int[m+1][n+1]; for(int[] v:puddles){ cache[v[0]][v[1]] = -1; } for(int i=1; i<m+1; i++){ for(int j=1; j<n+1; j++){ if(i==1 && j==1) cache[i][j] = 1; else if(cache[i][j] == -1) cache[i][j] = 0; else cache[i][j] = (cache[i-1][j] + cache[i][j-1])%1000000007; } } return cache[m][n]; } }+ 이 문제는 약간의 논란(+오류)이 있는데, 오른쪽-아래로만 이동 가능하다는 가정 하에 풀어야 한다.
예를 들어, 우물이 위아래로 있다면 구불구불한 길이라도 갈 수 있는 path 중 가장 짧은 거리를 구하는 것이 답이 된다. 하지만 지금 이 문제를 풀면 그 상황을 고려하지 않고 무조건 오른쪽-아래로만 이동이 가능할 때 답이 맞게 되어있다. 따라서 위아래로 있다면 무조건 0이 나오게 된다.
- 부분 문제 정의
🔗 LeetCode, Coin Change ✨
각각 다른 액수의 동전들 coins와 만들어야하는 총 금액 amount가 주어집니다.
동전들을 사용(중복 사용 가능)하여 amount를 만들 수 있는 가장 적은 동전 개수를 반환하세요.
가진 동전들로 amount를 만들 수 없다면, -1을 반환하세요.
풀이
바로 재귀적으로 풀고 메모이제이션을 적용하려 했을 때 (당연히) 감이 잡히지 않았던 문제였다. 부분 문제를 잘 정의해 풀어야 한다.
- 부분 문제 정의
- 완전탐색으로 정의한 부분 문제 : 코인들을 더하면 금액이 만들어진다.
🛠코인 종류별로 하나씩 개수를 늘려 만들 수 있는 amount 중 최소 개수
→ coin개수와 amount가 늘어날수록 만들어지는 수들은 기하급수적으로 늘어난다. 메모이제이션을 적용하기도 까다롭다.
- 부분 문제 정의 수정 : 만들어질 수 있는 금액을 만들고 그 금액을 만들 수 있는지 검사한다.
🛠제일 작은 코인 금액부터 시작하여 amount를 만들기까지 현재 가지고 있는 코인으로 만들 수 있는 수 인지 확인한다.
→ (amount-min(coins))*coin 개수만큼만 검사하면 된다.
- 만들어질 수 있는 금액을 배열주소로 하여 사용한 코인 개수를 기록할 수 있는 amount+1 길이의 배열을 만든다
- 그 수가 만들어질 수 있는지의 진위 여부는 우리가 생각하지않고 각 코인으로 만들 수 있는지 이전 기록들을 이용해 그 수를 만든다.
- 그리고 그 중 최소값을 계속 남겨 나간다.
- 완전탐색으로 정의한 부분 문제 : 코인들을 더하면 금액이 만들어진다.
- 점화식 작성
🔑현재 검사하는 금액 = (현재 금액 - 각 코인 금액)의 기록 +1 과 현재 검사하는 금액에 들어가 있는 수 중 최소
- cache 배열 초기화
- 가장 큰 수(답이 될 수 없는 코인 개수 아무거나)로 초기화
- 제시된 코인 금액과 동일하다면, 1로 초기화
- 배열의 길이에 맞게 조건 검사 후 점화식 작성
- cache 배열 초기화
import java.util.*; class Solution { public int coinChange(int[] coins, int amount) { if(amount == 0) return 0; Arrays.sort(coins); int[] cache = new int[amount+1]; Arrays.fill(cache, amount+1); int min=amount; for(int c: coins){ if(c < amount){ cache[c] = 1; min = Math.min(min, c); } else if(c == amount) return 1; } for(int i=min; i<amount+1; i++){ for(int c: coins){ if(i >= c){ cache[i] = Math.min(cache[i], cache[i-c]+1); } } } if(cache[amount] == amount+1) return -1; else return cache[amount]; } }- 부분 문제 정의
🔗 LeetCode, Word Break ✨
비어 있지 않은 문자열 s와 비어 있지 않은 단어 목록 wordDict가 주어집니다.
주어진 단어 목록 문자열을 연속으로 조각낼 수 있다면 true를 그럴 수 없다면 false를 반환하세요.
풀이
- 부분 문제 정의
처음 문제를 보고 단순화 시킬 때 단어가 일치할 경우를 있던 지점에서 단어 끝으로 'jump한다'고 생각하여 접근했다. 징검다리처럼 연속해서 끝까지 갈 수 있다면 true, 중간에 비는 곳이 있다면 false.
- 완전 탐색으로 정의한 부분 문제 : jump 지점을 만들어 가며 끝에 도달할 수 있는지 확인
🛠일치하는 단어들의 끝점을 저장한 후 가장 멀리 간 지점 순서대로 다시 검사
- 가장 멀리 간 지점이 답이 아닐 경우 그 다음 멀리 간 지점을 검사하며 점점 뒤로 간다.
→ 여기에서 가장 긴 단어 길이보다 더 뒤로가게 되는 경우는 답이 만들어질 수 없는 경우이기 때문에 false를 반환한다.
→ 처음 이렇게 문제를 풀었는데 이렇게 풀기까지의 과정이 아주 복잡했다...
- 가장 멀리 간 지점이 답이 아닐 경우 그 다음 멀리 간 지점을 검사하며 점점 뒤로 간다.
- 부분 문제 정의 수정 : 각 지점들을 나열한 후 그 까지 도달할 수 있는지를 검사
🛠각 지점들(s의 인덱스들)을 배열로 만들어 해당 지점에서 단어들 중 연속해 지나갈 수 있는지 검사
- 각 지점들(s의 인덱스들)에 도달할 수 있는지를 저장하는 s.length()+1 길이의 배열을 만든다
- 각 인덱스를 지나가며 wordDict를 검사하는데 해당 지점에 오기까지 검사하는 단어를 사용했을 때,
- 이전 지점이 연속되지 않는 지점(false)이라면 그대로 false
- 이전 지점이 연속되는 지점이라면 해당 단어로 jump할 수 있는지(substring이 단어와 같은 단어 인지) 확인
- 해당 단어로 jump할 수 있다면 나머지 단어들을 검사할 필요 없이 다음 index로 넘어간다.
- 끝까지 검사하면 마지막에 결과가 나온다.
- 완전 탐색으로 정의한 부분 문제 : jump 지점을 만들어 가며 끝에 도달할 수 있는지 확인
- 점화식 작성
🔑index까지 도달 가능 여부 = (index - 비교 단어 길이)의 지점 도달 가능 여부 && (비교 단어 길이, index에서 끝나는 s의 substring)단어 일치 여부
- 배열의 길이에 맞게 조건 검사 후 점화식 작성
class Solution { public boolean wordBreak(String s, List<String> wordDict) { if(s.length() == 0 || wordDict.size() == 0) return false; boolean[] cache = new boolean[s.length()+1]; cache[0] = true; for(int i=1; i<cache.length; i++){ for(String v: wordDict){ if(i-v.length() >= 0){ if(!cache[i-v.length()]) continue; else if(v.equals(s.substring(i-v.length(), i))){ cache[i] = true; break; } } } } return cache[s.length()]; } }- 부분 문제 정의
⍞ Reference
- 도서 : 알고리즘 문제해결전략, 인사이트
'Algorithm' 카테고리의 다른 글
| 이분 탐색(Binary Search), 어떨 때 적용할까? (0) | 2020.05.26 |
|---|
댓글