[BOJ/9251/Golang] 백준 9251 - LCS

접근 방식

이 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것의 길이를 찾는 문제입니다.. 문제에서 예로 든 것은 ACAYKP와 CAPCAK의 LSC인데요. 이 둘의 LCS는 ACAK가 됩니다.

여담으로, LCS는 Longest Common Subsequence의 약자입니다. Substring과의 다른 점은, Substring은 연속으로 붙어 있어야 한다는 제약이 있는 반면에, Subsequence는 그러한 제약이 없다는 점입니다.

백준 강의를 들어보니, 두 문자열의 LCS는 다음과 같다고 설명하고 있습니다.

두 문자열의 LCS는 다음과 같이 같은 문자가 일치하게 공백을 삽입하는 것과 같다고 볼 수 있다.

A = "ACAYKP"
B = "CAPCA_K_"

그러나 제가 참고한 블로그의 포스트에서는 조금 다른 방식으로 설명을 했는데요, 후자의 설명이 이해하는 데에 더 편해서 해당 내용을 소개하도록 하겠습니다.

최장 공통 문자열(Longest Common Substring)

최장 공통 문자열은 본 문제에서 소개할 최장 공통 부분 수열(Longest Common Subsequence) 보다 이해하기 쉽고, 후자를 구하는데 사용되기 때문에 먼저 보도록 합니다.

점화식

// 문자열의 시작이 인덱스 1부터라고 가정합니다.
// 즉, 문자열 0번 인덱스에는 공백이 들어있습니다.

if A[i] == B[j] {
    D[i][j] = D[i-1][j-1] + 1
} else {
    D[i][j] = 0
}

최장 공통 문자열의 점화식은 매우 단순합니다. 최장 공통 문자열은 최장 공통 부분 수열처럼 끊어지거나 해서는 안됩니다. 즉, 한 번이라도 다른 값이 나온다면, 해당 위치에의 최장 공통 문자열의 길이는 0이 됩니다. 이전의 최장 공통 문자열과 연결될 수 없기 때문입니다. 마찬가지로, 같은 값이 나온다면, 해당 위치에서의 최장 공통 문자열의 길이는 이전의 최장 공통 문자열과 연결되기 때문에, 이전의 최장 공통 문자열의 길이 + 1이 됩니다. 만약 이전의 최장 공통 문자열의 길이 가 0이었다면, 이번에 새로 연속된 문자열이 시작되는 것이므로, 1이 되는데, 이러한 케이스도 모두 포함하고 있습니다.

최장 공통 부분 수열(Longest Common Subsequence)

최장 공통 부분 수열은 최장 공통 문자열과 유사하지만, 한 가지 조건이 더 추가 됩니다. 우선 점화식을 보겠습니다.

점화식

// 문자열의 시작이 인덱스 1부터라고 가정합니다.
// 즉, 문자열 0번 인덱스에는 공백이 들어있습니다.

if A[i] == B[j] {
    D[i][j] = D[i-1][j-1] + 1 // 최장 공통 문자열과 일치합니다.
} else {
    D[i][j] = max(D[i-1][j], D[i][j-1]) // max 함수는 직접 구현해야 합니다.
}

최장 공통 부분 수열의 점화식은 최장 공통 문자열의 점화식과 유사하나, A[i] != B[j]가 되는 경우에 연산이 추가됩니다. 즉, 비교하는 문자가 서로 다를 때 최장 공통 문자열과 달라집니다.

D[i-1][j] & D[i][j-1]

최장 공통 부분 수열이 최장 공통 문자열과 가장 크게 다른 점은, 연속하지 않아도 된다는 점입니다. 즉, (i, j)를 현재 상태라고 할 때, 현재 상태 직전의 최장 공통 부분 수열의 값을 그대로 유지해서 가져갈 수 있다는 것입니다. 여기에서 "현재 상태 직전의 최장 공통 부분 수열의 값" 을 구하는 과정이 D[i-1][j]과 D[i][j-1] 입니다. 그 중에서 최장의 값을 선택해야 하므로, 두 값 중, 더 큰 값을 선택하기 위해, max 함수를 사용하게 됩니다.

코드

package main

import (
    "bufio"
    "fmt"
    "os"
)

var (
    w  = bufio.NewWriter(os.Stdout)
    sc = bufio.NewScanner(os.Stdin)
)

var (
    D [][]int
)

func main() {
    defer w.Flush()
    A, B := " "+scan(), " "+scan()
    n, m := len(A)-1, len(B)-1
    D = make([][]int, n+1)
    for i := range D {
        D[i] = make([]int, m+1)
    }
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            if A[i] == B[j] {
                D[i][j] = D[i-1][j-1] + 1
            } else {
                D[i][j] = max(D[i-1][j], D[i][j-1])
            }
        }
    }
    fmt.Fprintln(w, D[n][m])
}

func scan() string {
    sc.Scan()
    return sc.Text()
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

마무리

여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.

혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글💬을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다 😊

참고

• https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence