[Gold V] LCS - 9251

문제 링크

성능 요약

메모리: 6004 KB, 시간: 4 ms

분류

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

제출 일자

2025년 1월 5일 22:52:41

문제 설명

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

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

입력

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

출력

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

문제 풀이

상세 로직 설명

1. 문자가 같은 경우 (str1[i-1] == str2[j-1])

• 현재 문자를 LCS에 포함
• 이전 상태(dp[i-1][j-1])에 1을 더함
• 예: "AB"와 "AC"에서 'A' 매칭 시 dp[1][1] = dp[0][0] + 1

2. 문자가 다른 경우

• 이전 상태들 중 최대값 선택
• 위쪽(dp[i-1][j])과 왼쪽(dp[i][j-1]) 중 큰 값
• 현재 문자를 포함하지 않는 최적해 유지

예시로 보는 알고리즘 진행 과정

str1 = "ABCD"
str2 = "AEBD"

단계별 DP 테이블 변화

1. 초기 상태

   '' A  E  B  D
'' 0  0  0  0  0
A  0  0  0  0  0
B  0  0  0  0  0
C  0  0  0  0  0
D  0  0  0  0  0

2. 첫 번째 행 처리 (A)

   '' A  E  B  D
'' 0  0  0  0  0
A  0  1  1  1  1
B  0  0  0  0  0
C  0  0  0  0  0
D  0  0  0  0  0

3. 최종 DP 테이블

   '' A  E  B  D
'' 0  0  0  0  0
A  0  1  1  1  1
B  0  1  1  2  2
C  0  1  1  2  2
D  0  1  1  2  3

시간 복잡도 분석

• 시간 복잡도: O(N × M)

  • N: 첫 번째 문자열의 길이
  • M: 두 번째 문자열의 길이

• 공간 복잡도: O(N × M)

  • 2차원 DP 테이블 사용

코드

Java 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

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

	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String str1 = br.readLine();
		String str2 = br.readLine();
		
		int[][] dp = new int[str1.length() + 1][str2.length() + 1];
		for(int i=1; i<=str1.length(); i++) {
			for(int j=1; j<=str2.length(); j++) {
				if(str1.charAt(i-1)==str2.charAt(j-1)) dp[i][j] = Math.max(dp[i-1][j-1] + 1, dp[i][j]);
				else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
			}
		}
//		for(int i=0; i<=str1.length(); i++) {
//			for(int j=0; j<=str2.length(); j++) {
//				System.out.print(dp[i][j] + " ");
//			}
//			System.out.println();
//		}
		bw.write(String.valueOf(dp[str1.length()][str2.length()]));
		bw.flush();
		bw.close();
		br.close();
	}
}

---

C++ 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    string str1, str2;
    cin >> str1 >> str2;

    vector<vector<int>> dp(str1.length() + 1,
                           vector<int>(str2.length() + 1, 0));

    for (int i = 1; i <= str1.length(); i++) {
        for (int j = 1; j <= str2.length(); j++) {
            if (str1[i - 1] == str2[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[str1.length()][str2.length()] << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    // cin >> tt;    // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}