[Baekjoon/🥇Ⅴ] 9251: LCS⭐

🙋‍♀️ LCS

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

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

🙋‍♀️ 입력

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

🙋‍♀️ 출력

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

👩‍💻 Algoritm: dp 적용

해당 문제는 시간 제약이 있다. 따라서 어떻게 코드를 효율적으로 작성하나가 무척 중요하다.

이 문제에서는 dp를 통해 해결할 수 있다. 1차원 배열의 누적값을 통해 해결할 수도 있고, 2차원 배열의 캐시를 만들어 해결할 수도 있다.

⌨️ dp: 누적합

• 문자열a를 기준으로 1차원 배열을 생성한다.
• 문자열b의 문자 하나하나를 돌 때마다 문자열a 전체를 확인한다.
  • 문자가 같을 경우, 해당 위치 전까지의 최대 누적합 + 1로 누적합을 업데이트 한다.

코드를 통해서 위 과정을 확인해보자!!

누적합 알고리즘1: 시간초과

str1 = input()
str2 = input()

if str1 == str2:
  print(len(str1))
else:
  dp = [0]*len(str1)

  for i in range(len(str2)):
    for j in range(len(dp)-1, -1, -1):
      if str2[i] == str1[j]:
        try:
          dp[j] = max(dp[0:j])+1
        except:
          dp[j] = 1

  print(max(dp))

• 업데이트되는 누적합이 다음 단계에 영향을 미치지 않도록 하기 위해 두 번째 반복문에서는 문자열을 끝에서 부터 확인한다.
• 문자열의 첫 번째 원소일 때는 해당 위치 전 누적합의 최댓값을 구할 수 없기 때문에 1을 설정해준다.

해당 풀이는 단순 반복문이므로 pypy3로는 간신히 통과하지만 python3로는 시간초과의 결과가 나온다. 위 풀이에서 반복문을 돌 때마다 max를 계산하는 부분이 시간을 많이 잡아먹는 것이라 생각해 해당 부분을 고려해 다음과 같이 수정하였다.

누적합 알고리즘2

str1 = input()
str2 = input()

if str1 == str2:
  print(len(str1))
else:
  dp = [0]*len(str1)

  for i in range(len(str2)):
    v_max = 0 # max 값 저장 변수
    for j in range(len(str1)):
      if dp[j] > v_max: # max 값 업데이트
        v_max = dp[j]
      elif str1[j] == str2[i]: # max+1 값으로 누적합 업데이트
        dp[j] = v_max + 1
    print(dp)
  
  print(max(dp))

이렇게 알고리즘을 수정하면 현저히 속도가 빨라진 것을 확인할 수 있다.

⌨️ dp: 2차원 배열 캐시 사용

해당 풀이는 위 풀이와는 다르게 2차원 배열을 사용한다. 그 과정을 그림을 통해 알아보자!!

• 하나의 문자열b의 문자 하나하나를 돌 때마다 문자열a 전체를 확인한다.
  • 문자가 같을 경우 해당 글자가 있기 전의 LCS 값 + 1로 dp 값을 업데이트 한다.
  • 문자가 서로 다를 경우, 그 상황에서의 최대 LCS 값을 dp에 저장한다.

이제 코드를 통해서 위 과정을 더 자세히 살펴보자!

str1 = input()
str2 = input()
matrix = [[0]*(len(str2)+1) for _ in range(len(str1)+1)]

for i in range(1, len(str1)+1):
  for j in range(1, len(str2)+1):
    if str1[i-1] == str2[j-1]:
      matrix[i][j] = matrix[i-1][j-1] + 1
    else:
      matrix[i][j] = max(matrix[i][j-1], matrix[i-1][j])

print(matrix[-1][-1])

📝 참고 자료

• https://www.acmicpc.net/problem/9251
• https://myjamong.tistory.com/3179
• https://suri78.tistory.com/11