문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
문제회고
도저히 풀리지가 않아서 풀이를 봐도 이해가 안되었던 문제이다.
그림을 그려가면서 이해를 하려고 하니 이해가 가기 시작했다.
문자열에 대한 직관적인 느낌이 들어야 하는 문제 이기 때문에 풀이를 보지 않고 풀었다면 못 풀었을 것 같은 문제이다.
도출된 점화식
현재 비교하는 문자가 같으면 - (현재 비교하는 문자를 모두 제외했을 때 값) +1
현재 비교하는 문자가 다르면 - Math.max(순열1의 현재문자를 제외했을 때 값, 순열2의 현재문자를 제외했을 때 값)
LCS(백준9251) 구현코드
import java.util.*;
import java.io.*;
/*
* 문자열에 대한 직관적인 느낌이 들어야 하는 문제, 해결된 부분을 그림으로 묶어서 생각해보기
현재 비교하는 문자가 같으면 – (현재 비교하는 문자를 모두 제외했을 때 값) +1
현재 비교하는 문자가 다르면 – Math.max(순열1의 현재문자를 제외했을 때 값, 순열2의 현재문자를 제외했을 때 값)*/
public class Main {
static String A;
static String B;
static int[][] D;
public static void main(String[] args) throws Exception{
Scanner sc = new Scanner(System.in);
A = sc.nextLine();
B = sc.nextLine();
D = new int[A.length()+1][B.length()+1];
//이미 계산이 되었는지 확인하기 위한 초기화
for(int[] a: D) {
Arrays.fill(a, -1);
}
int result;
result = LCS(A.length(), B.length());
System.out.print(result);
}
public static int LCS(int a, int b) {
if(a == 0 || b == 0) {
D[a][b] = 0;
return D[a][b];
}
if(A.charAt(a-1) == B.charAt(b-1)) {
if(D[a-1][b-1] == -1) {
D[a][b] = LCS(a-1, b-1) + 1;
}
else D[a][b] = D[a-1][b-1] + 1;
}else {
if(D[a-1][b] == -1) {
D[a-1][b] = LCS(a-1,b);
}
if(D[a][b-1] == -1) {
D[a][b-1] = LCS(a, b-1);
}
D[a][b] = Math.max(D[a-1][b], D[a][b-1]);
}
return D[a][b];
}
}LCS 2(백준9252)
위의 구현코드로 제일 긴 부분수열의 크기를 찾는것은 가능 하지만 부분 수열을 이루는 문자열을 찾기 위해서는 추가적인 로직이 필요함
구현방안
- 위의 재귀함수를 수정하여 구하기
-
현재 문자열이 동일한 경우 문자를 추가하여 다음 재귀를 진행하는 방식 – 재귀의 순서가 일정하지 않아서 문제가 발생한다.
위와 같이 (A-B-C-D) (A-E-D)의 순으로 재귀를 하는 경우
가장 긴 문자열을 찾는 것이기 때문에 ABCD가 출력되야 한다. 하지만 A에서 B가 아닌 E로 먼저 재귀해버릴 경우 D는 이미 계산되어 있기 때문에 D까지 재귀가 되지 않는다.
따라서 출력은 A,B,C 또는 A,E,D가 된다. -
모든 경우의 중복되는 문자열을 저장하는 방식 – 문자열 처리과정에서 시간초과 발생
구현한 함수
//모든 경우의 중복되는 문자열을 저장하여 구현하는 함수 - 문자열을 처리하는 과정에서 시간초과 발생
public static String LCS(int a, int b) {
if(a == 0 || b == 0) {
D[a][b] = "";
return D[a][b];
}
//추가한 문자열이 같은경우
if(A.charAt(a-1) == B.charAt(b-1)) {
if(D[a-1][b-1] == null) {
D[a][b] = LCS(a-1, b-1) + A.charAt(a-1);
}
else D[a][b] = D[a-1][b-1] + A.charAt(a-1);
//추가한 문자열이 다른 경우
}else {
if(D[a-1][b] == null) {
D[a-1][b] = LCS(a-1,b);
}
if(D[a][b-1] == null) {
D[a][b-1] = LCS(a, b-1);
}
if(D[a-1][b].length() > D[a][b-1].length()) D[a][b] = D[a-1][b];
else D[a][b] = D[a][b-1];
}
return D[a][b];
}- 시간초과 원인 관련댓글
2. 탑-다운 방식에서 바텀-업 방식으로 변경하여 점화식 배열을 모두 채운 후 문자열 구하기
- 구현코드
import java.util.*;
import java.io.*;
/*
* 문자열에 대한 직관적인 느낌이 들어야 하는 문제, 해결된 부분을 그림으로 묶어서 생각해보기
현재 비교하는 문자가 같으면 – (현재 비교하는 문자를 모두 제외했을 때 값) +1
현재 비교하는 문자가 다르면 – Math.max(순열1의 현재문자를 제외했을 때 값, 순열2의 현재문자를 제외했을 때 값)*/
public class Q90 {
static String A;
static String B;
static int[][] D;
public static void main(String[] args) throws Exception{
Scanner sc = new Scanner(System.in);
A = sc.nextLine();
B = sc.nextLine();
D = new int[A.length()+1][B.length()+1];
//LCS(A.length(),B.length());
for(int i =1; i<= A.length(); i++) {
for(int j = 1; j<= B.length(); j++) {
if(A.charAt(i-1) == B.charAt(j-1)) {
D[i][j] = D[i-1][j-1] + 1;
}else {
D[i][j] = Math.max(D[i-1][j], D[i][j-1]);
}
}
}
System.out.println(D[A.length()][B.length()]);
if(D[A.length()][B.length()] != 0) {
System.out.print(getText());
}
}
중복되는 문자를 출력하는 함수
public static String getText() {
String answer = "";
int i = A.length();
int j = B.length();
while(D[i][j] != 0) {
//왼쪽값과 비교해서 왼쪽값과 같으면 왼쪽으로 이동
while(j>=1 && D[i][j] == D[i][j-1]) {
j--;
}
//현재행의 마지막 지점에서 행과열의 문자가 다르면 위의 행으로 이동하여 행과열의 문자가 같을 때 해당 문자 저장
if(A.charAt(i-1) != B.charAt(j-1)) {
i--;
}else {
answer = A.charAt(i-1) + answer;
i--;
j--;
}
}
return answer;
}
}기념사진
