[백준] 9251. LCS 풀이 (Python, TypeScript)

9251번: LCS

접근한 방식

입력받은 문자열을 각각 A와 B라고 한다면 크기가 (A의 길이 +1) * (B의 길이+1)인 2차원 DP 테이블 d를 만듭니다. d[i][j]를 계산하기 위해 다음 점화식을 사용합니다

a[i-1]과 b[j-1]이 같은 글자라면 d[i][j] = d[i-1][j-1] + 1을 넣어줍니다. LCS에 값을 추가할 수 있다는 것을 의미합니다.

a[i-1]과 b[j-1]이 다르다면 d[i][j] = max(d[i-1][j], d[i][j-1])을 넣어줍니다. 현재까지의 LCS가 계산된 값들 중 가장 긴 LCS를 선택하는 것을 의미합니다.

 

이런식으로 진행하면 테이블의 마지막 요소가 최종적인 LCS의 길이가 됩니다.

      A  C  A  Y  K  P  
  [0, 0, 0, 0, 0, 0, 0]
C [0, 0, 1, 1, 1, 1, 1]
A [0, 1, 1, 1, 2, 2, 2]
P [0, 1, 2, 2, 2, 3, 3]
C [0, 1, 2, 2, 2, 3, 3]
A [0, 1, 2, 2, 2, 3, 4]
K [0, 1, 2, 3, 3, 3, 4]

 

Python

import sys
sys.stdin = open("input.txt", "r") # 제거
input = sys.stdin.readline

a, b = [input().rstrip() for _ in range(2)]
d = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(len(a)):
    for j in range(len(b)):
        if a[i] == b[j]:
            d[i + 1][j + 1] = d[i][j] + 1
        else:
            d[i + 1][j + 1] = max(d[i + 1][j], d[i][j + 1])
print(d[-1][-1])

TypeScript

function solution(a: string, b: string) {
  const d: number[][] = Array.from({ length: a.length + 1 }, () =>
    Array(b.length + 1).fill(0)
  );
  for (let i = 0; i < a.length; i += 1) {
    for (let j = 0; j < b.length; j += 1) {
      if (a[i] === b[j]) d[i + 1][j + 1] = d[i][j] + 1;
      else d[i + 1][j + 1] = Math.max(d[i + 1][j], d[i][j + 1]);
    }
  }
  console.log(d[a.length][b.length]);
}
solution("ACAYKP", "CAPCAK");