BOJ_9251 LCS

• TOC {:toc}

이 글은 백준 온라인 저지의 9251번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.06.17

틀린 풀이입니다. 정답은 참고 답안을 참고해주세요.

import sys
from bisect import bisect_left, insort_left
input = lambda: sys.stdin.readline().rstrip()

C = {}
for i, c in enumerate(input()):
    if c in C:
        insort_left(C[c], i)
    else:
        C[c] = [i]

count = {}
for key in C.keys():
    count[key] = 0

LCS = []
LCS_i = []
for x in input():
    if x not in C:
        continue

    i = C[x][min(count[x], len(C[x]) - 1)]
    if not LCS or i > LCS_i[-1]:
        LCS.append(x)
        LCS_i.append(i)
        count[x] += 1
    else:
        target = bisect_left(LCS_i, i)
        count[LCS[target]] -= 1
        count[x] += 1
        LCS[target] = x
        LCS_i[target] = i

print(len(LCS))

아이디어 & 풀이

• 기준이 될 문자열은 {문자: [인덱스]} 의 딕셔너리로 바꾼다
• 비교할 문자열을 순회하면서 인덱스값의 가장 긴 증가하는 부분 수열을 구하면 된다.
• 한 문자가 여러 번 나올 경우 어떻게 처리할지를 정해야 한다.
  • 인덱스를 오름차순으로 정리하고 사용할 때마다 pop 하면 되겠다.

디버그

• 나중에 또 써야 할 수도 있어서 그냥 pop 하면 안 됐었다.
  • LCS에 안에 존재하면 그 다음번째 인덱스를 쓰고 아니면 계속 처음 값을 써야 한다.
  • 해당 문자가 LCS 안에 존재하는 개수를 구해야 하는데 매번 세는 것보다 count 변수를 관리하는 게 나을 것 같아서 그렇게 하기로 했다.
  • 인덱스랑 문자 둘 다 필요해서 문자인 LCS와 인덱스인 LCS_i를 따로 관리하기로 했다.
• 특정 문자가 기준보다 많이 나왔을 경우에 count에서 에러가 발생했다.
  • 예를 들어 첫 문자열에서는 C가 한 개밖에 존재하지 않는데 다음 입력한 문자열에서는 두 번 나오는 경우.
  • count[x] 값을 비교 값과 상관없이 먼저 받아와서 쓰기 때문에 이 경우 C[x]의 count[x]가 range 밖의 인덱스가 된다.
  • count[x]가 len(C[x])보다 크거나 같으면 마지막 원소를 가리킬 수 있도록 max(count[x], len(C[x]) - 1)을 인덱스로 갖도록 수정했다.
• 한 문자에 해당하는 인덱스가 여러 개일 때 무조건 첫 번째 인덱스부터 사용하면 안 된다.
  • 예를 들어 CDCACDAA & BACBACAB 두 문자열을 입력했을 때 LCS는 ACAA인데 결과가 CAA로 틀리다.
  • 첫 번째 C가 A 다음에 이어져야 LCS가 더 길어지는데 이를 C의 첫 인덱스가 0으로 A의 첫 인덱스인 3보다 작아서 C가 A를 대체하면서 LCS가 CAA가 되는 것이다.
    • 인덱스 딕셔너리: {'C': [0, 2, 4], 'D': [1, 5], 'A': [3, 6, 7]}

피드백

디버그 마지막 문제 해결하기.

• DP 문제는 주로 비효율적인 것 같이 보여도 하나씩 비교해나가는 방식을 취해야 하는 것 같다.

참고 답안 1

x, y = "0" + input(), "0" + input()
LCS = [[0] * (len(y)) for _ in range(len(x))]

for i in range(1, len(x)):
    for j in range(1, len(y)):
        if x[i] == y[j]:
            LCS[i][j] = LCS[i - 1][j - 1] + 1
        else:
            LCS[i][j] = max(LCS[i][j - 1], LCS[i - 1][j])

print(LCS[-1][-1])

아이디어 & 풀이

두 문자열을 일일이 순회하면서 비교해, 그 문자까지의 LCS의 문자 수를 입력한다.

예를 들어 예제 입력의 두 문자열 ACAYPK, CAPCAK로 다음과 같은 행렬을 구성할 수 있다.

• 특정 행렬에 해당하는 값은 두 문자열을 각 행과 각 열까지 비교했을 때 만들 수 있는 LCS의 문자 수이다.
• 4행 5열에 해당하는 값은 ACA와 CAPC를 비교했을 때 LCS의 문자 수이다.
• 0 행은 각 1행, 1열에서도 ‘이전’ 값을 참조하는 논리를 일관적으로 유지하기 위해서 추가한 것이다.

각 행(e.g., i)과 각 열(e.g., j)을 순회할 때,

• 행과 열의 문자(e.g., A)가 같으면 그 행과 열의 이전 문자까지 비교한 LCS에 해당 문자(e.g., A)를 추가한다.
  • 즉, 직전 행(i - 1)과 직전 열(j - 1)에 해당하는 값에서 1 증가한 값이 현재 행렬의 값이 된다.
• 문자가 같지 않으면 직전 문자까지 비교했을 때 만들 수 있는 LCS 중 길이가 가장 긴 것을 유지한다.
  • 여기서 ‘직전 문자까지’는 행의 문자열은 유지한 채 열의 직전 문자까지 비교한 것일 수도 있고 그 반대가 될 수도 있다.
  • 예를 들어 현재 CAP의 P와 ACA의 A를 비교하고 있다면, CAP와 AC의 LCS와 CA와 ACA의 LCS 중 더 긴 것을 유지하면 된다.
  • 즉, 현재 행(i)의 직전 열(j - 1) 값과 현재 열(j)의 직전 행(i - 1)의 값 중 더 큰 값이 현재 행렬의 값이 된다.

이를 이용해서 각 행렬값을 채우면 다음과 같다.

이해를 위해 3행의 진행을 살펴보자.

3행은 CAPCAK의 문자를 하나씩 늘려가면서 AC와 비교하는 과정이다. 2열인 C부터 시작한다.

1. 2열: AC와 C를 비교한다.
   • C와 C는 같다.
   • AC와 C의 LCS는 A와 None의 LSC에 C를 추가한 C이고 길이는 1이다.
2. 3열: AC와 CA를 비교한다.
   • C와 A는 같지 않다.
   • 전 열은 AC와 C를 비교한 것으로 LCS는 C이고 길이는 1이다.
   • 전 행은 A와 CA를 비교한 것으로 LCS는 A이고 길이는 1이다.
   • AC와 CA의 LCS는 C 또는 A로 유지되고 길이는 1이다.
3. 4열: AC와 CAP를 비교한다.
   • C와 P는 같지 않다.
   • 전 열은 AC와 CA를 비교한 것으로 LCS는 C 또는 A이고 길이는 1이다.
   • 전 행은 A와 CAP를 비교한 것으로 LCS는 A 이고 길이는 1이다.
   • AC와 CAP의 LCS는 C 또는 A로 유지되고 길이는 1이다.
4. 5열: AC와 CAPC를 비교한다.
   • C와 C는 같다.
   • AC와 CAPC의 LCS는 A와 CAP의 LSC A에 C를 추가한 AC이고 길이는 2이다.
5. 6열: AC와 CAPCA를 비교한다.
   • C와 A는 같지 않다.
   • 전 열은 AC와 CAPC를 비교한 것으로 LCS는 AC이고 길이는 2이다.
   • 전 행은 A와 CAPCA를 비교한 것으로 LCS는 A 이고 길이는 1이다.
   • AC와 CAPCA의 LCS는 AC로 유지되고 길이는 2이다.
6. 7열: AC와 CAPCAK를 비교한다.
   • C와 A는 같지 않다.
   • 전 열은 AC와 CAPCA를 비교한 것으로 LCS는 AC이고 길이는 2이다.
   • 전 행은 A와 CAPCAK를 비교한 것으로 LCS는 A 이고 길이는 1이다.
   • AC와 CAPCAK의 LCS는 AC로 유지되고 길이는 2이다.

참고 답안 2

x, y = input(), input()
LCS = [0] * 1000

for i in range(len(x)):
    max_lcs = 0
    for j in range(len(y)):
        if max_lcs < LCS[j]:
            max_lcs = LCS[j]
        elif x[i] == y[j]:
            LCS[j] = max_lcs + 1

print(max(LCS))

아이디어 & 풀이

두 문자열을 일일이 순회하면서 비교해 해당 문자까지의 LCS 최대 길이를 LCS에 입력한다.

전체적인 흐름 자체는 참고 답안 1과 유사하지만 2차원 리스트가 아닌 1차원 리스트 LCS에 해당 문자까지의 최대 LCS 길이를 저장한다.

• 이전 행을 참조하지 않고 x의 문자를 순회하면서 동일한 리스트에 값을 ‘업데이트’하므로 1차원 리스트만으로도 관리할 수 있다.
• 이전까지의 LCS값을 반영하는 데는 변수 max_lcs를 사용한다.

최대 LCS 길이를 구하는 과정은 다음과 같다.

• 입력한 x의 각 문자에 대해 이전에 입력한 LCS 값을 순회하면서
• 현재 max_lcs가 LCS값보다 작으면 max_lcs를 그 값으로 변경한다.
  • 이전에 입력한 LCS는 이전 문자까지의 LCS 최댓값이고 이는 현재 문자까지의 LCS에 포함되기 때문에 현재 최댓값에 이를 반영해주는 것이다.
• 현재 x의 문자와 y의 문자가 같으면 해당 LCS 값을 max_lcs에 1 더한 값으로 바꾼다.
• 마지막 x 문자에 대해서까지 업데이트를 끝낸 LCS의 최댓값을 출력한다.

예제 입력의 두 문자열 ACAYPK, CAPCAK로 LCS를 업데이트하는 과정은 다음과 같다.

참고 답안 3

x = input()
y = input()

T = [0] * 300
row = 0
X = 0

for i in range(len(x)):
    T[ord(x[i])] += 2 ** i

for i in range(len(x)):
    if x[i] == y[0]:
        row += 2 ** i
        break

for i in range(1, len(y)):
    X = T[ord(y[i])] | row
    row = X & ((X - (row * 2 + 1)) ^ X)

cnt = 0
while row:
    cnt += row % 2
    row //= 2

print(cnt)