김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 1958 LCS 3 파이썬(Python)

문제 링크

최장 공통 부분수열(Longest Common Subsequence, LCS) 문제.
LCS를 구하는 건 간단하다. 두 문자열(수열)에 대해, DP를 사용해서 순회하면 되기 때문이다.
점화식을 살펴보면 다음과 같다.
우선 lcs[0][j] = lcs[i][0] = 0이다. 하나의 문자열이라도 길이가 0이면 부분문자열의 최대 길이도 0이기 때문이다.
만약 a[i] == b[j]라면 현재 문자가 같은 경우이므로 이전까지의 답에서 길이가 1 증가한 lcs[i][j] = lcs[i-1][j-1] + 1이다.
그렇지 않은 경우라면 둘 중 한 문자열의 길이를 감소시키면 되는데, 그 중 최대값을 취하면 되므로 lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1])이다.
이게 두 문자열에 대한 LCS이고, 세 문자열도 거의 똑같다.
우선 lcs[0][j][k] = lcs[i][0][k] = lcs[i][j][0] = 0이다. 하나의 문자열이라도 길이가 0이면 부분문자열의 최대 길이도 0이기 때문이다.
만약 a[i] == b[j] == c[k]라면 현재 문자가 같은 경우이므로 이전까지의 답에서 길이가 1 증가한 lcs[i][j][k] = lcs[i-1][j-1][k-1] + 1이다.
그렇지 않은 경우라면 셋 중 한 문자열의 길이를 감소시키면 되는데, 그 중 최대값을 취하면 되므로 lcs[i][j] = max(lcs[i-1][j][k], lcs[i][j-1][k], lcs[i][j][k-1])이다.
문자열이 두 개일 때의 LCS를 잘 이해하고 있다면 매우 쉽게 풀 수 있다.
DP 구현은 간단하게 funtools.cache를 통해 해도 충분해서 그렇게 했지만, 사실 반복문을 사용하는 게 훨씬 빠르므로 그렇게 하는 게 더 좋다.

#!python

from functools import cache

a, b, c = (input() for _ in range(3))

# 메모이제이션
@cache
# a[:s1], b[:s2], c[:s3]의 LCS 길이
def lcs(s1, s2, s3):
    # 하나라도 빈 문자열이면 0
    if 0 in (s1, s2, s3):
        return 0
    
    # 세 문자열의 마지막 문자가 모두 같다면(즉, LCS에 들어감)
    # 이전까지의 LCS에서 길이가 1 증가
    if a[s1-1] == b[s2-1] == c[s3-1]:
        return lcs(s1 - 1, s2 - 1, s3 - 1) + 1
    
    # 그렇지 않다면 셋 다 각각 1씩 줄인 후 그 중 최대값을 찾는다
    return max(lcs(s1 - 1, s2, s3), lcs(s1, s2 - 1, s3), lcs(s1, s2, s3 - 1))

print(lcs(*map(len, (a, b, c))))

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑