9 min to read
백준-9251-1520-LCS-최장공통부분수열-DP-다이나믹프로그래밍
알고리즘 좀 꾸준히 해라 대훈아 제발
알고리즘 좀 매일 하자 매일 대훈아
카카오 블라인드 채용 알고리즘 문제들을 풀면서
문자열 문제들이 진짜 많이 나왔다.
그리고 효율성 또한 많이 따지는 문제들이 나와서
DP알고리즘은 필수라고 생각해서 DP 문제들을 풀어보려고 한다.
DP 동적 계획법 Dynamic programming
학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. - 위키백과
원리는 간단하다. 코드말고
어떠한 주어진 큰 문제가 있다면 이 문제를 여러개의 하위 문제로 나누어 푼다.
그리고 하위 문제들을 해결하고 계산한뒤 그 값을 저장한다.
방금 저장했던 하위 문제들이 또 나오게 되면 저장해놓은 값을 사용한다.
아주 큰 문제를 해결할때 유용한 방법.
최단경로문제, 행렬의 제곱, 최적화 문제에 자주 등장한다.
가장 대표적인 예시 피보나치수열
피보나치 수열이라고
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
이전 항 2개를 더하면 다음 항 나오는 수열
만약 fib(5)를 구하고 싶다
그럼 fib(4)+fib(3) 를 구해야하고 이것은
(fib(3) + fib(2)) + (fib(2) + fib(1)) 를 의미하며 이것은 또
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
를 의미한다.
결국 fib(5)는
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
이걸 의미하는데 이런식으로 계속해서 재귀함수를 호출해서 시간이 아주 많이 걸린다.
이걸 해결하는 것이 DP
int dp[] = new int[5];
//이런식으로 저장할 DP배열을 만든다음
static int fibona(n){
if(n==0)return 0;
if(n==1)return 1;
//이미 들린적이 있다면 저장했던값 바로 리턴해주기
if(dp[n] != -1)return dp[n];
//한번도 저장 해놓은적 없는 하위문제라면 저장하고 리턴
dp[n]= fibona(n-2) + fibona(n-1);
return dp[n];
}
이렇게 계산값을 저장해놓으면 중복 계산이 줄어든다.
아무튼 백준 문제들을 풀어보자
백준 9251 LCS
문제출처 - https://www.acmicpc.net/problem/9251
문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.
예시입력
ACAYKP CAPCAK
예시출력
4
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class LCS {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input1 = br.readLine();
String input2 = br.readLine();
int dp[][] = new int [input1.length()+1][input2.length()+1];
for(int i = 1 ; i < input1.length()+1;i++) {
char input1Char = input1.charAt(i-1);
for(int j = 1 ; j< input2.length()+1; j++) {
char input2Char = input2.charAt(j-1);
if(input1Char==input2Char) {
dp[i][j] = dp[i-1][j-1]+1;
}else {
dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
System.out.println(dp[input1.length()][input2.length()]);
}
}
엄청 어려워 보였던 문제가 몇 줄만에 뚝딱 해결됬다..
이와 같은 방식은 유튜브에 외국인이 설명해준 방식으로 문제를 풀었는데
https://youtu.be/P-mMvhfJhu8
이걸 참고하도록 하자.
DP 한문제 더
백준 1520 내리막길
출처 https://www.acmicpc.net/problem/1520
문제
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.
현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.
지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.
출력
첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.
예제입력
4 5 50 45 37 32 30 35 50 40 20 25 30 30 25 17 28 27 24 22 15 10
예제출력
3
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class 내리막길 {
static int M,N,dp[][],map[][];
static int dx[]= {0,1,0,-1};
static int dy[]= {1,0,-1,0};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
dp = new int [M][N];
map = new int[M][N];
for(int i = 0 ; i < M; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0 ; j<N ; j++) {
map[i][j]=Integer.parseInt(st.nextToken());
}
}
for(int i = 0 ; i < M; i++) {
Arrays.fill(dp[i], -1);
}
int result = dfs(0,0);
System.out.println(result);
}
private static int dfs(int i, int j) {
if(i==M-1&&j==N-1) {
return 1;
}
if(dp[i][j]!=-1) {
return dp[i][j];
}else {
dp[i][j]=0;
for(int k = 0 ; k < 4; k++) {
int nextX = i+dx[k];
int nextY = j+dy[k];
if(nextX>=M||nextY>=N||nextX<0||nextY<0||map[nextX][nextY]>=map[i][j]) {
continue;
}
dp[i][j] = dp[i][j]+dfs(nextX,nextY);
}
}
return dp[i][j];
}
}
dp를사용해서 갔던 경로면 다시 탐색 하지않도록
private static int dfs(int i, int j) {
if(i==M-1&&j==N-1) {
return 1;
}
if(dp[i][j]!=-1) {
return dp[i][j];
}else {
dp[i][j]=0;
for(int k = 0 ; k < 4; k++) {
int nextX = i+dx[k];
int nextY = j+dy[k];
if(nextX>=M||nextY>=N||nextX<0||nextY<0||map[nextX][nextY]>=map[i][j]) {
continue;
}
dp[i][j] = dp[i][j]+dfs(nextX,nextY);
}
}
return dp[i][j];
}
Comments