[백준] 9251 - LCS(Longest Common Subsequence)

백준 바로가기

9251번: LCS

DP 알고리즘 이어서 푸는 중입니다. 문제 난이도는 solved.ac 기준 풀었던 것중 최상이었고 Gold5 였습니다. 난이도 체감은 알고리즘 개념보다 수학적 사고능력에 따라 높낮이가 결정되는 것 같습니다. DP를 알고있지만 위 문제는 어떻게 적용해야 할지 감이 오지 않았습니다. DP 알고리즘 문제의 특징인듯 합니다. 따라서 많이 풀어보고 다양한 형태의 문제를 접할수록 유리합니다.

제가 참고한 블로그 입니다. 바로가기

백준 온라인 저지 LCS

답안 출력은 데이터 타입 int인 2차원 배열을 사용했습니다. 형태를 텍스트로 표현하면 LCS[1st][2nd], 1st에 문제로 주어지는 String1의 n번째라고 보면 됩니다. 2nd는 Sting2의 m번째겠죠? 그리고 배열의 값에는 String1의 n번째, String2의 m번째까지 비교한 LCS가 들어갑니다. 여기까지 이해가 되지 않으셨다면 댓글로 남겨주세요. 풀어서 설명해드리겠습니다 :)

답안 '틀'을 설계했으니 이제 채워넣을 차례입니다. 당연히 두 문자열 간 비교가 들어가야겠고, 같거나 다를때 분기가 나누어져야 합니다. 막막합니다. 저도 그랬어요. 집단지성의 힘을 빌려 참고한 블로그에 나와있는대로 설명드릴게요. (다시 한번 감사합니다) 비교 반복문은 한 번만 돕니다.

기준되는 문자열을 aChar로 설정하겠습니다. bChar와 같은 문자일 때, 즉 aChar[i] == bChar[j] 일 때 답안 '틀' LCS[i][j] = LCS[i-1][j-1] + 1 이 됩니다. 다시 말씀드리지만 LCS[i][j]의 값은 String1 i번째 글자까지, String2 j번째 글자까지 비교했을 때 LCS 값입니다. aChar[i] == bChar[j]가 성립하기 때문에 LCS에 1을 추가해주는거죠. 순서는 왜 고려하지 않냐고 자문했습니다. 고려할 필요없어요. 왜냐하면 이미 순서대로 가고있기 때문입니다. 설정은 반복문을 1번만 돌도록 하고, 기준 문자열을 aChar로 정해둔 이유가 순서대로 비교해주기 때문이거든요.

다시 돌아와서, 만약 aChar[i] != bChar[j] 처럼 같지 않을 경우 LCS[i][j] 점화식은 어떻게 세워야할까요? 이 부분이 까다로워서 블로그를 3~4개 찾아봤습니다. 우선 식부터 날리고 설명하겠습니다. LCS[i][j] = Math.max(LCS[i -1][j], LCS[i][j - 1])  

if i = 3, j = 3 일 때 i번째와 j번째 char가 같지 않아야 되니 아래와 같습니다.(편의상 배열 index가 아닌 일반적인 index로 지칭할게요)

String1 A C A

String2 C A P

String1 A C A

String2 C A P

같지 않을 땐 빨간색과 파란색의 경우에서 max인 LCS를 받아줘야 합니다. 그리고 그 값은 이미 반복문과 DP 점화식에 따라 구해져 있습니다. 이제 이해가 되셨나요? 확실히 시각을 이용한 설명이 효율적입니다. 이제 코드를 보며 마치겠습니다. 무려 2시간 30분 동안 한 문제를 다뤘습니다. 깨어있는 시간(약 17시간) 중 약 17%를 썼네요... 오늘도 화이팅 입니다!

※ 코드에서 반복문 제어변수 i가 1부터 시작하는 이유는 LCS 점화식 때문입니다. LCS[i][j] = LCS[i-1][j-1] + 1... 이니 0부터 시작하면 ArrayOutofBound Exception이 발생하거든요. 그래서 aChar[0]과 bChar[0]은 LCS[1][1]과 대응된다고 보시면 됩니다 :)

package baekJoon.week12;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class LCS_9251 {
 
    static String a;
    static String b;
    static int aLeng;
    static int bLeng;
    static char[] aChar = new char[1001];
    static char[] bChar = new char[1001];
    static int[][] LCS = new int[1001][1001];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        a = br.readLine();
        b = br.readLine();
        aLeng = a.length();
        bLeng = b.length();
 
        aChar = a.toCharArray();
        bChar = b.toCharArray();
 
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                if (aChar[i - 1] == bChar[j - 1]) {
                    LCS[i][j] = LCS[i - 1][j - 1] + 1;
                } else {
                    LCS[i][j] = Math.max(LCS[i - 1][j], LCS[i][j - 1]);
                }
            }
        }
 
        System.out.println(LCS[aLeng][bLeng]);
        br.close();
 
 
    }
 
 
}