[백준 / Java] 9251번: LCS (DP)

 

 

코테99 23일차 문제는 백준 9251번 LCS다.

 

 

문제 이해

LCS(최장 공통 부분 수열) 문제는 두 개의 문자열이 주어졌을 때, 두 문자열에서 공통으로 등장하는 가장 긴 부분 수열의 길이 를 찾는 문제다.
여기서 부분 수열 은 연속될 필요가 없지만, 원래 순서를 유지해야 한다.

 

제한 조건

• 문자열 길이는 최대 1000
• 시간 제한 0.1초 (O(N^2) 알고리즘까지 가능)

---

접근 방법

이 문제는 동적 계획법(DP) 을 활용하여 해결할 수 있다.
2차원 DP 배열을 사용해 비교하는 방식이 핵심.

 

점화식 도출

1. 문자열을 2차원 표로 비교
   • dp[i][j]는 첫 번째 문자열의 i번째 문자까지와 두 번째 문자열의 j번째 문자까지 비교했을 때 LCS의 길이 를 저장한다.
2. 문자가 같을 때
   • dp[i][j] = dp[i-1][j-1] + 1
   • (이전까지의 LCS 길이 + 1)
3. 문자가 다를 때
   • dp[i][j] = max(dp[i-1][j], dp[i][j-1])
   • (위쪽 값과 왼쪽 값을 비교하여 최댓값 선택)

 

예제 풀이

입력: ACAYKP, CAPCAK

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

• 최종 dp[6][6] = 4
• 즉, ACAK 의 길이인 4가 정답

---

알고리즘 진행 순서

1. 2차원 dp 배열 선언 (dp[N+1][M+1])
2. 두 문자열을 순차적으로 비교
   • 문자가 같다면 dp[i][j] = dp[i-1][j-1] + 1
   • 문자가 다르면 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
3. 최종적으로 dp[N][M] 출력

---

구현 코드

package Boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Boj9251 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input1 = br.readLine();
        String input2 = br.readLine();

        int len1 = input1.length();
        int len2 = input2.length();
        int dp[][] = new int[len1 + 1][len2 + 1];

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (input1.charAt(i - 1) == input2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        System.out.println(dp[len1][len2]);
    }
}​

---

회고

기존 코드 문제점

1. 1차원 dp 배열을 사용했지만, 2차원 dp 배열이 필요함
   • LCS는 두 개의 문자열을 비교해야 하므로 2차원 테이블이 필요하다.
2. arr1[i] == arr2[j] 를 제대로 비교하지 않음
   • dp[j + 1]을 사용한 비교는 LCS의 흐름을 반영하지 못함.
3. 최대 길이 추적이 어려움
   • 단순 count 방식이 아니라, 각 부분 문자열을 저장하는 방식이 필요

개선된 점

1. 2차원 dp 테이블 사용
   • 두 문자열을 행렬로 비교하여 최적의 LCS 길이를 저장
2. 문자가 같을 때 / 다를 때 조건 처리
   • dp[i][j] = dp[i-1][j-1] + 1
   • dp[i][j] = max(dp[i-1][j], dp[i][j-1])
3. 최종 dp[N][M] 값 출력
   • 전체 문자열을 고려한 최적의 길이 반환