[백준] LCS

🔗 문제 보기 - [백준] LCS

📖 문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

✍ 입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

📄 출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

✅ 코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
  
public class Main {  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        String firstLine = br.readLine();  
        String secondLine = br.readLine();  
        int[][] arr = new int[firstLine.length() + 1][secondLine.length() + 1];  
  
        for(int i = 1; i <= firstLine.length(); i++) {  
            for(int j = 1; j <= secondLine.length(); j++) {  
                if(firstLine.charAt(i - 1) == secondLine.charAt(j - 1)) {  
                    arr[i][j] = arr[i-1][j-1] + 1;  
                } else {  
                    arr[i][j] = Math.max(arr[i-1][j], arr[i][j-1]);  
                }  
            }  
        }  
  
        System.out.println(arr[firstLine.length()][secondLine.length()]);  
    }  
}

🧩 코드풀이

LCS를 푸는 문제인데 접해보지 않아서 어떤 방식으로 풀어야할지 감이 잡히지 않아 아래 주소에서 참고하여 DP 알고리즘으로 문제를 해결했습니다.
한번 알아두면 LCS가 나오는 문제들을 풀때 좀더 생각을 확장하여 풀 수 있을 것 같다는 생각이 들었습니다.

1. 한글자씩 비교하여 문자열이 동일하다면 지금까지의 최대 공통 부분수열인 arr[i-1][j-1]에 1을 더해준 값을 입력해주고,
2. 문자열이 동일하지 않다면  '현재의 문자를 비교하는 과정' 이전의 과정인 배열의 arr[i-1][j] 혹은 arr[i][j-1] 중 큰 값을 입력해줍니다.
3. 끝으로 배열의 끝부분을 출력해주면 수열 중 가장 긴 길이가 됩니다.

참고 - https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence#longest-common-subsequence-substring