[Algorithm] 백준 - LCS (9251번)

문제

[백준] LCS

9251번: LCS

 

사용 알고리즘

- 다이나믹 프로그래밍 (Dynamic Programming)

해결방법

• 입력 받은 두 문자열 X, Y의 위치 인덱스를 각각 i, j라 할 때, 두 문자열의 최장 공통 부문 수열을 LCS(i, j)라 하자
• if Xi = Yj 일 때, (두 문자열의 마지막 글자가 같을 때)
  LCS(i, j) = LCS(i-1, j-1) + 1
• if Xi != Yj 일 때, (두 문자열의 마지막 글자가 다를 때)
  LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1))

https://www.youtube.com/watch?v=EAXDUxVYquY

 

 

 

소스코드

사용언어 : c++

#include <iostream>

using namespace std;

/*
    LCS(i, j) = LCS(i-1, j-1) + 1 if xi = yj
    LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1)) if xi != yj        
*/

int dp[1001][1001];

int main()
{
    string str1, str2;

    cin >> str1 >> str2;

    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()];
    
    return 0;
}

 

사용언어 : java

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

class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String firstStr = br.readLine();
        String secondStr = br.readLine();
        int firsthLength = firstStr.length();
        int secondLength = secondStr.length();
        int[][] dp = new int[firsthLength+1][secondLength+1];

        for (int i=1; i<=firsthLength; i++) {
            for (int j=1; j<=secondLength; j++) {
                if (firstStr.charAt(i-1) == secondStr.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[firsthLength][secondLength]);
    }
}

문자열 입력받을 때

* String str = br.readLine() << String 타입으로 받는 경우, 인덱스 접근을 할 수 없어 charAt() 메서드를 사용해야 한다

* char[] str = br.readLine().toCharArray() 사용해 char타입의 배열형으로 받을 수 있다

 

한줄평

java 공부를 위해 java로 다시 풀고 있는데, c++랑 크게 다르진 않은 것 같다. (입출력이 좀 빡센 것 말곤. .)