[Algorithm] BOJ_9251_LCS - JAVA

문제 설명

문제 해설

LCS

문제 설명에도 나오지만 두 수열에 부분 수열이 되는 수열 중 가장 긴 것을 찾는 것.
DP를 사용하는 가장 대표적인 방식 중 하나.

해결 방법

String str1 = "ACAYKP"
String str2 = "CAPCAK"
int dp[str1문자열길이][str2문자열길이]일 때
DP의 풀이 방법에 따라

\1. 문제를 작은 문제로 나눈다.

• 문자열 str1의 문자를 가리키는 인덱스를 i1, str2의 문자를 가리키는 인덱스를 i2라 둔다.
• 문자열 str1과 str2의 인덱스가 가리키는 문자를 비교한다.
• 나타날 수 있는 경우의 수는 (1)i1, i2가 가리키는 문자가 같을 때 (2)i1, i2가 가리키는 문자가 다를 때
  (1)
  i1, i2가 같이 커진다. -> i1 = i1 + 1, i2 = i2 + 1
  기존의 i1, i2가 가리키던 문자가 같았기 때문에 현재 dp[i1][i2]가 가지게 될 값은 dp[i1-1][i2-1]+1
  -> dp[i1][i2] = dp[i1-1][i2-1]+1
  (2)
  i1, i2둘 중 하나의 인덱스값만 커진다. -> i1 = i1 + 1, i2 = i2 OR i1 = i1, i2 = i2 + 1
  기존의 i1, i2가 가리키던 문자가 달랐기 때문에 dp의 값은 이전 값에서 큰 값을 가져온다.
  -> dp[i1][i2] = dp[i1][i2-1]과 dp[i1-1][i2] 중 큰 값

\2. 점화식을 생각한다.

• 문자열을 가리키는 인덱스가 0인 경우는 공집합이라 생각하고 dp[...][0], dp[0][...]에 0을 채워둔다. 공집합과 공집합이 같다고 문자가 같은건 아니다...
• if(str1[i1] = = str2[i2])
  dp[i1][i2] = dp[i1-1][i2-1]+1
• if(str1[i1] ! = str2[i2])
  dp[i1][i2] = dp[i1][i2-1]과 dp[i1-1][i2] 중 큰 값

\3. 점화식을 토대로 코드를 작성한다.
JAVA로 구현

import java.util.Scanner;

public class Q9251 {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String str1 = scan.nextLine();
        String str2 = scan.nextLine();
        int str1Size = str1.length();
        int str2Size = str2.length();
        int[][] dp = new int[str1Size+1][str2Size+1]; // 0번째 인덱스를 공집합으로 사용하기 위해 +1
        //LCS
        for(int i1 =1; i1<=str1Size; i1++){
            for(int i2 =1; i2<=str2Size; i2++){ 
                // i1, i2 인덱스가 카리키는 문자가 같을 때
                if(str1.charAt(i1-1)==str2.charAt(i2-1)){ // i1,i2는 dp테이블에서의 인덱스. 문자열에 적용하기 위해 -1
                    dp[i1][i2] = dp[i1-1][i2-1]+1;
                }
                // i1, i2 인덱스가 카리키는 문자가 다를 때
                else{ 
                    dp[i1][i2] = Math.max(dp[i1-1][i2], dp[i1][i2-1]);
                }
            }
        }
        System.out.println(dp[str1Size][str2Size]); //가장 긴 값은 dp의 마지막에 저장된다.

    }
}