Algorithm/Baekjoon Online Judge

[BOJ] 9251번: LCS

mirae.kwak 2022. 4. 15. 00:22
728x90

https://www.acmicpc.net/

 

문제풀이

https://www.acmicpc.net/problem/9251

 

9251번: LCS

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

www.acmicpc.net

두 개의 문자열이 주어질 때 두 문자열에서 매치되는 가장 긴 문자열의 길이를 구하는 문제이다. 사실 어떻게 하면 풀 수 있을지 고민을 좀 했다. 생각보다 쉽게 방식이 안 떠올라서 이전에 계산한 값을 어떻게 하면 현재 계산에 적용할 수 있을지 방법을 알기위해 노력했다. 

이 문제에서는 알파벳 하나가 어떤 알파벳과 매치될지 알 수 없다는 점이 가장 어려운 점이었다. 동일한 알파벳이 반복적으로 나온다면 그 중 어떤 알파벳과 매치될지 알고 이전 값을 활용한다는게 와닿지 않았던 것 같다. 그래서 생각하다보니 문자열 두개가 있을 때 하나의 문자열에서 한개의 알파벳을 기준으로 다른 문자열에서 모든 알파벳을 찾아봐야했다. 이후 일치하는 알파벳이 나온다면 이전의 이미 검사해서 저장해뒀던 개수 값에서 최대값을 이용해서 계산할 수 있었다. 

 

예를 들어보자!

다음의 문자열이 입력으로 주어졌다고 생각한다.

ACAYKP
CAPCAK

 

첫번째 줄의 문자열을 차례로 기준으로 보고 두번째 줄의 문자열과 모두 비교한다.

 

  C A P C A K
A 0 1 0 0 1 0
  C A P C A K
C 1 1 0 2 1 0
  C A P C A K
A 1 2 0 2 3 0
  C A P C A K
Y 1 2 0 2 3 0
  C A P C A K
K 1 2 0 2 3 4
  C A P C A K
P 1 2 3 2 3 4

다음과 같이 배열이 변화하게된다. 같은 알파벳이 나온다면 지나온 배열에서 제일 큰 값, 개수를 가져다가 1을 더한 값을 개수로 저장한다. 

 


Python3

import sys
str1 = list(map(str, sys.stdin.readline().rstrip()))
str2 = list(map(str, sys.stdin.readline().rstrip()))
dp = [0]*len(str2)
for i in range(len(str1)):
    cnt = 0
    for j in range(len(str2)):
        if cnt < dp[j]:
            cnt = dp[j]
        elif str1[i] == str2[j]:
            dp[j] = cnt + 1
print(max(dp))

2차원 배열로도 dp배열을 구현할 수 있지만 메모리 절약을 위해 1차원 배열을 사용하여 구현했다.

여기서 중요한 점은 cnt에 큰 값을 저장해둔다는 것이다. dp배열을 돌면서 최대 개수를 저장한다. 만약 두 알파벳이 같다면 배열의 dp값은 cnt보다 작거나 같을 것이다. 그럼 두번째 조건문을 통해 구했던 최대 개수에 본인 것 카운트 1을 더해 저장한다. 마지막엔 최대 값을 출력!

728x90