[백준 9251번 LCS]
오늘의 문제는 LCS이다.
#고민의 흐름
처음엔 무조건 완전탐색!
최악의 경우 길이가 1000인 2개의 문자열을 각자 만들어지는 모든 문자열의 종류를 비교해 준다면..?
당연히 시간 초과가 날 것이라 생각했다.
(애초에 문제 이름이 LCS이기도 하고,,)
그렇다면 LCS란 무엇일까?
문제에 나와있듯이, LCS(Longest Common Subsequence, 최장 공통부분 수열) 문제란
문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
과거에 이미 다른 문제(공통부분문자열)로 LCS를 다룬 적이 있다!
(한번 설명했던 내용기반이라 해당 문제가 보다 설명이 자세할 수 있다. 부족한 부분은 해당 문제로 채워보자.)
기억이 가물가물하지만 이참에 제대로 혼자 풀어보려 했다.
메모장을 켜고 각 문자열로 표를 만들어 각 칸들을 채워나가는 규칙을 기억해 냈다.
사진과 함께 규칙을 찾아보자.
예시는 문제에서 제시된 예시를 차용했다.
첫 줄들을 0으로 채운 이유는 추후 코드로 구현할 때, Array 범위 오류를 미리 배제하기 위함이다.
표에서 각 숫자는 처음부터 교차하는 지점까지 해당하는 각 문자열들이 몇 개나 겹치는지.
즉 해당 부분까지의 최장 부분 문자열의 길이들이 표를 채워나간다.
표를 채워나가는 규칙으론
1. 1번 문자열의 해당 문자와 2번 문자열의 해당 문자가 같다면?
dp [i-1][j-1] + 1이 dp [i][j]의 값이 된다.
왜냐하면 dp [i-1][j-1]이 해당 문자 전까지의 최장 부분 문자열이기 때문이다.
2. 1번 문자열의 해당 문자와 2번 문자열의 해당 문자가 다르다면?
dp [i-1][j] 값과 dp [i][j-1] 값중 더 큰 수를 차용한다.
왜냐하면 해당포함 / 비포함 최장 부분 문자열이 dp[i][j-1] / dp [i-1][j] 값이기 때문이다.
그럼 첫 줄부터 채워나가 보자.
1번째 문자열의 A만 가지고 2번째 문자열과 비교한 결과이다.
A끼리 같은 문자를 만났을 때 dp [i][j] 값을 dp [i-1][j-1] + 1로 채워준 부분!
이와 같은 규칙으로 표들을 채워나가 보자.
첫 문자열에서 Y부분은 두 번째 문자열에 Y가 없기 때문에 과정 사진을 생략했다!
최종적으로 맨 마지막 칸이 두 문자열의 LCS 값이다!!
Bottom-Up 방식으로 dp표를 채워간 방법이었다.
코드는 다음과 같다.
( 코드가 너무 커 보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보여요! )
( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )
import java.util.*;
import java.io.*;
public class Main {
public static void main (String [] arg) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1 = br.readLine();
String str2 = br.readLine();
char [] arr1 = new char [str1.length() + 1];
char [] arr2 = new char [str2.length() + 1];
for(int i = 0; i<str1.length(); i++){
arr1[i + 1] = str1.charAt(i);
}
for(int i = 0; i<str2.length(); i++){
arr2[i + 1] = str2.charAt(i);
}
//여기까지가 입력!
int [][] dp = new int [str1.length() + 1][str2.length() + 1];
//dp[i-1][j-1]의 경우 Array범위 오류를 범하지 않기 위해서 1더 크게 만들어줬다.
//각 문자열의 길이만큼 돌면서..! (idx를 유의해주자)
for(int i = 1; i<str1.length() + 1; i++){
for(int j = 1; j<str2.length() + 1; j++){
if(arr1[i] == arr2[j]){ // 같다면 이전최장길이 + 1를,
dp[i][j] = dp[i-1][j-1] + 1;
}else{ // 다르다면 제외 / 포함당시 최장 길이를 dp[i][j]에 넣어준다.
dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
}
}
}
//맨 마지막 칸의 값을 출력해주면 끝!
System.out.println(dp[str1.length()][str2.length()]);
}
}
블로그를 작성하다 보니 저번 문제에서 Bottom-Up DP방식으로 문제를 풀고 Top-Down방법으로도 풀었던 기억이 났다.
이왕 공부하는 거 이번 문제도 Top-Down 방식으로 풀어봐야겠다는 생각이 들어 다시 풀어보았다.
다음은 탑다운 방식으로 풀어본 코드를 보자.
import java.util.*;
import java.io.*;
public class Main {
static Integer dp[][];
static char arr1[], arr2[];
public static void main (String [] arg) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1 = br.readLine();
String str2 = br.readLine();
arr1 = new char [str1.length() + 1];
arr2 = new char [str2.length() + 1];
for(int i = 0; i<str1.length(); i++){
arr1[i + 1] = str1.charAt(i);
}
for(int i = 0; i<str2.length(); i++){
arr2[i + 1] = str2.charAt(i);
}
//여기까지 입력, dp함수를 이용하기 위해서 static으로 선언해주었다.
dp = new Integer [str1.length() + 1][str2.length() + 1];
System.out.println(dp(str1.length(), str2.length()));
}
static int dp(int i, int j){
if(i < 1 || j < 1){ // 1이하의 범위, 문자열범위 미만일시 0을 return해준다.
return 0;
}
// 아래의 조건문이 없으면 코드가 매 순간 끝까지 구하러가기 때문에 시간초과가 난다.
// 한번 내보고 수정한건 안비밀 ,,ㅎ
if(dp[i][j] != null){
return dp[i][j];
}
//아래의 내용은 바텀업 방식과 비슷하다.
if(arr1[i] == arr2[j]){
dp[i][j] = dp(i-1, j-1) + 1;
}else{
dp[i][j] = Math.max(dp(i-1, j), dp(i, j-1));
}
return dp[i][j];
}
}
LCS, DP에 대해서 공부를 더 해야겠다는 생각이 있었는데 한번 더 풀어볼 수 있었던 문제였다.
요즘 Solved.ac의 클래스 문제를 밀고 있는데 클래스 4에 들어오자 어려운 문제들이 잦아진다..
끝까지 열심히 하기를 바라며 ㅎ
궁금한 점이 있거나 보충할 점이 있다면 언제든 댓글 부탁드립니다 ~
https://www.acmicpc.net/problem/9251