BOJ_LCS_9251

문제 링크

성능 요약

Java- 메모리: 18632 KB, 시간: 132 ms
C++ - 메모리: 5984 KB, 시간: 4 ms

분류

다이나믹 프로그래밍, 문자열

제출 일자

2024년 12월 20일 22:36:47

문제 설명

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

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

입력

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

출력

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

풀이

느낀점

• 최장 부분 수열이라는 말부터 이해가 잘 안됨.
• 문자열처럼 연속되지 않더라도 인덱스 순서대로 나열했을때 두 문자열에 공통으로 속하는 문자들의 수열을 말한다,,
• 순서는 앞뒤로 섞거나 할 순 없다.

설계 : 40분 (참고했음)

• 최장 부분 수열 알고리즘 기본문제인 것 같다.
• 첫번째 문자열을 탐색하는 인덱스를 i, 두번째 문자열을 탐색하는 인덱스를 j라고 가정할때 i번째와 j번째까지 비교했을때 최장 부분수열의 길이를 dp[i][j]에 저장해 나간다.
  • i번째 문자와 j번째 문자가 일치할때: 두 문자를 제외하고 각 -1 인덱스까지의 최장 부분수열 길이에 +1한 수를 테이블에 저장 → 두 문자가 일치하면 이전에 다른 인덱스의 문자와 일치했더라도 더이상 의미가 없기 때문
    
  • 일치하지 않을때: 각각의 상대문자열의 -1 인덱스까지의 최장 부분수열 길이 중 더 큰 값을 끌어온다. → 다른 인덱스의 문자와는 일치할 수 있기 때문에 상대 인덱스를 하나 줄였을때의 dp테이블을 확인해보고 더 큰 값으로 유지

코드(Java)

• 구현 시간: 30분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: LCS_9251
 * Date: 2024.12.20
 */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		char[] str_1 = input();
		char[] str_2 = input();
		int[][] dp = new int[str_1.length][str_2.length];

		for (int i = 1; i < str_1.length; i++) {
			for (int j = 1; j < str_2.length; j++) {
				if (str_1[i] == str_2[j]) dp[i][j] = dp[i-1][j-1] + 1;
				else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
			}
		}

		bw.write(String.valueOf(dp[str_1.length-1][str_2.length-1]));
		bw.flush();
		bw.close();
		br.close();
	}

	public static char[] input() throws IOException {
		char[] input = br.readLine().toCharArray();
		char[] result = new char[input.length + 1];
		int idx = 1;
		for (char c : input) {
			result[idx++] = c;
		}
		return result;
	}
}

코드(C++)

• 구현 시간: 15분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: LCS_9251
 * Date: 2024.12.20
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int main() {

    string a, b;
    cin >> a >> b;

    vector<char> first(a.begin(), a.end());
    vector<char> second(b.begin(), b.end());

    vector<vector<int> > dp(first.size() + 1, vector<int>(second.size() + 1));

    for (int i = 1; i <= first.size(); i++) {
        for (int j = 1; j <= second.size(); j++) {
            if (first[i-1] == second[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    cout << dp[first.size()][second.size()] << "\n";

    return 0;
}