백준 - 9251 LCS [LCS]

 

9251번: LCS

 

1. 문제 요약

최장 공통 부분 수열의 길이를 구하시오.

 

2. 접근 방법

LCS는 굉장히 잘 알려진 유명한 알고리즘입니다.

 

범위를 지정하여 끝의 문자를 비교하는 방식입니다.

 

m = "ACAYKP"

n = "CAPCAK"

 

문자를 하나씩 비교하여 같을 경우는 dp[i][j] = [i-1][j-1] +1 이 됩니다.

• ACA와 CA를 비교할 경우 A가 같습니다.
• A를 떼놓고 비교한다면 AC와 C를 비교한값 + 1(A가 같으므로) 이 됩니다.

 

다를 경우는 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 이 됩니다.

• ACA와 CAP를 비교할 경우 A와 P가 다릅니다.
• (ACA, CA) 혹은 (AC, CAP) 모두 ACA, CAP의 부분수열입니다.
• 맨 뒤의 문자를 하나 제외한 값을 각각 비교하여 더 큰 경우를 재사용해주면 됩니다.

 

3. 파이썬

dp = [[0 for _ in range(len(n)+1)] for _ in range(len(m)+1)]

for i in range(1, len(m)+1):
    for j in range(1, len(n)+1):
        if m[i-1] == n[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

print(dp[-1][-1])

 

4. 자바

char[] m = bf.readLine().toCharArray();
char[] n = bf.readLine().toCharArray();

int[][] dp = new int[m.length + 1][n.length + 1];

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

System.out.println(dp[m.length][n.length]);

 

5. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Gold/9251.%E2%80%85LCS