[백준] 단계별로 풀어보기(단계:15,동적계획법1,JAVA)9251번, LCS

문제 링크

9251번: LCS

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적계획법이란 위 문제와 같이 동일한 연산을 계속 반복하여 비효율적으로 코드가 실행되어 그것을 향상시키기 위하여반복되는 연산의 결과를 따로 저장하여 적재적소에 코드가 더 효율적으로 만드는 방법입니다.

 

LCS에 대한 정의는 문제에서 알려주고 있지만 알고리즘을 구성할 때 감이 잡히지 않아서 위키백과에서 LCS에 관련 글을 참고하여 풀어보았습니다.

최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전

 

ko.wikipedia.org

입력받은 2가지 문자열을 중 하나의 문자열이 끝에 온다고 생각하고 나올 수 있는 수열을 표현하는 것입니다.예제 입력 1로 살펴보겠습니다.

아래 표에서 CAPCAK에 첫번째 글자 C를 마지막 글자로 보았을 때입니다.

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0
P	0
C	0
A	0
K	0

ACAYKP가 있을 때 순서대로 확인하는 것입니다.

(1,1) : A와 C를 비교하는 것으로 공통 수열이 없습니다 = 0

(1,2) : 는 AC와 C를 비교하는 것으로 공통 수열이 C가 존재하여 = 1

(1,3)~(1,6) :  ACA, ACAY, ACAYK, ACAYKP 에서 C를 마지막으로 하는 수열은 C하나 뿐 = 1

 

첫번째 글자 CA에서 A를 마지막 글자로 보았을 때입니다.

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0
C	0
A	0
K	0

(2,1) : A와 CA를 비교하는 것으로 공통 수열이 A가 존재하여 = 1

(1,2) : AC와 CA를 비교하는 것으로 공통 수열이 C가 존재하여 = 1

(1,3) : ACA와 CA를 비교하는 것으로 공통 수열 CA가 존재하여 = 2

(1,4)~(1,6) : ACA, ACAY, ACAYK, ACAYKP 에서 CA와 비교하여 공통 수열은 CA = 2

 

첫번째 글자 CAP에서 P를 마지막 글자로 보았을 때입니다.

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0
A	0
K	0

(2,1) : A와 CAP를 비교하는 것으로 공통 수열이 A가 존재하여 = 1

(1,2) : AC와 CAP를 비교하는 것으로 공통 수열이 C가 존재하여 = 1

(1,3) : ACA와 CAP를 비교하는 것으로 공통 수열 CA가 존재하여 = 2

(1,4)~(1,5) : ACA, ACAY, ACAYK 에서 CAP와 비교하여 공통 수열은 CA = 2

(1,6) : ACAYKP와 CAP를 비교하는 것으로 공통 수열 CAP가 존재하여 = 3

 

결과적으로 표를 완성했을 때 아래와 동일하게 나옵니다.

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

 

표를 확인하면 규칙이 존재합니다.

글자가 같으면)  check[i-1][j-1] + 1

예를 들어 (5,3)에서 A와 A가 같아서 (4,2)의 값 2 + 1을 해서 (5,3)의 값은 3이 됩니다.

글자가 다르면) Math.max(check[i-1][j],check[i][j-1])

예를 들어 (3,3)에서 P와 A가 달라서 (2,3)과 (3,2) 중 큰 값을 사용하여 값은 2가 됩니다.

 

이 규칙을 이용하여 알고리즘을 작성하였으며 마지막 행에서 가장 큰 값이 공통 수열에 가장 긴 길이로 출력하였습니다.

왜냐하면 마지막 행은 입력값의 길이를 토대로 경우의 수를 전부 확인한 값들이기 때문입니다.

입력된 문자열 길이에 따라 저장하기 위해  [첫번째 문자열길이 +1][두번째 문자열 길이 +1]으로 2차원 배열의 메모이제이션을 구성하였습니다.

 

 

• 공통수열의 길이 값 저장할 메모이제이션 배열 check를 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• 공통 수열의 길이를 얻는 함수 LCS을 만들었습니다.
• for문을 통하여 문자별 LCS함수를 실행하였습니다.
• for문을 통하여 메모이제이션에 저장된 공통수열의 최대 길이를 Math.max 이용하여 얻었습니다.
• System.out.println을 사용하여 가장 긴 공통수열의 길이를 출력하였습니다.

• 행의 첫번째 열의 값이 0인 경우는 그 행이 탐색되지 않았다고 판단하고 연산을 실행합니다.
• check가 0이 아니면 탐색된 값이기 때문에 메모이제이션에 값을 가져온다.
• for문을 이용하여 위에 알고리즘처럼 작동하게 LCS함수를 작성하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[][] check;	//메모이제이션 배열
	static String s1,s2;	//입력값
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
        //----------입력값 저장 및 배열 초기화---------
    	s1 = br.readLine();
    	s2 = br.readLine();
    	check = new int[s2.length()+1][s1.length()+1];
    	int max = Integer.MIN_VALUE;
    	for(int i=1;i<=s2.length();i++) //함수실행
    		LCS(i);
    	for(int i=1;i<=s1.length();i++)	//최대값 구하기
    		max = Math.max(max, check[s2.length()][i]);

    	System.out.println(max);	//결과 출력
    	br.close();
	}
    //-------------LCS함수 실행-----------
	public static void LCS(int depth) {
		if(check[depth][1]==0) {		//메모제이션 없을 시 진행
			for(int i=1;i<=s1.length();i++) {
				if(s2.charAt(depth-1)==s1.charAt(i-1))	//글자가 같을때
					check[depth][i] = check[depth-1][i-1] + 1;
				else		//글자가 다를 때
					check[depth][i] = Math.max(check[depth-1][i], check[depth][i-1]);
			}
		}
	}
}