(Python) 백준 9251

Lee Yechan·2024년 1월 8일
algorithmbojpspython백준
0

알고리즘 문제 풀이

목록 보기
34/60
post-thumbnail

백준 9251

시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.1 초 (https://www.acmicpc.net/problem/9251#)256 MB80934332542440540.559%

문제

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

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

입력

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

출력

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

답안

import sys

string1 = sys.stdin.readline().strip()
string2 = sys.stdin.readline().strip()
memo = [[0 for _ in range(len(string2)+1)] for _ in range(len(string1)+1)]

for i in range(len(string1)):
    for j in range(len(string2)):
        memo[i][j] = memo[i-1][j-1] + 1 if string1[i] == string2[j] \
            else max(memo[i-1][j], memo[i][j-1])

print(max(map(max, memo)))

풀이

이 문제는 어떻게 풀어야 할지 감이 잘 잡히지 않았다.

고민을 이어가다가 이 블로그 글을 보게 되었는데,

https://velog.io/@emplam27/알고리즘-그림으로-알아보는-LCS-알고리즘-Longest-Common-Substring와-Longest-Common-Subsequence

많은 도움이 되어 문제를 해결할 수 있게 되었다.

위 블로그에서는 점화식을 제시한 뒤, 그 점화식을 이용해 어떻게 문제를 풀 수 있는지 알고리즘 실행 단계를 하나씩 밟으며 보여준다.

그 설명을 읽으니 어떻게 문제가 풀어지는지는 이해할 수 있었지만, 처음에 점화식을 어떻게 유도해낼 수 있었는지에 대한 설명은 없었다.

DP의 경우 점화식을 도출해내는 것이 굉장히 중요한데 그것이 빠져 있는 것이다.

이해하는 데에는 도움이 될지언정, 다음에 비슷한 문제를 접했을 때 어떻게 풀지 다시한번 막막해지는 것이 반복될 것이다.

그래서 나는 위 블로그 글에 덧붙여, 내가 실제로 이 문제를 받았을 때 점화식을 어떻게 도출해낼 수 있을지 그 과정을 시뮬레이션해보기로 했다.

이렇게 점화식을 도출하는 논리적 흐름을 명확하게 함으로써 다른 DP 문제들을 풀 때에도 도움이 되기를 바란다.

첫 번째로, 이 문제를 왜 DP 문제라고 생각했는가?

문제의 시간 요구사항을 보면 굉장히 짧다. (0.1초) 문자열의 길이가 1000으로 짧다고 하더라도, 이는 아주 효율적인 알고리즘을 요구한다는 것이다. O(n)이나 O(nlogn), 아주 최악의 경우에라도 O(n^2)은 넘지 않아야 했다.

그럼에도 불구하고, 살펴보아야 하는 경우의 수가 아주 많았다. 그 경우의 수 중에서 어떤 것이 최적인지 알기도 어려웠다.

최적해를 구해야 한다, 이전 결과(부분해)를 활용하여 시간을 단축해야 한다, 와 같은 요구조건들로부터 DP를 쓰면 효율적일 수 있겠다는 생각을 한 것이다.

그렇다면 어떻게 문제를 풀 것인가?

먼저, 문제의 조건을 통해 명시적/암시적으로 제한되는 것이 무엇인지 살펴보자.

첫 번째로, 두 문자열의 길이가 모두 1000 이하로 제한된다.

두 번째로, 문자열에 사용되는 문자는 A-Z까지 26개의 대문자만이 사용된다.

세 번째로, 최장 공통 부분 수열 그 자체를 구하는 것이 아니라, 그 수열의 길이에만 관심이 있다.

네 번째로, 문자열의 순서는 왼쪽에서부터 오른쪽이다. 그밖의 경우는 고려할 필요 없다.

다음으로, 메모이제이션할 공간에 대한 설계를 해보자.

먼저 생각해봤던 것은 다음과 같은 2차원 공간이다.

ABC…YZ
A
B
C
…
Y
Z

알파벳 대문자가 26개만으로 이뤄져 있으므로, 한정된 크기의 공간이다.

다만 이런 공간의 문제점은, 문자열의 순서가 이곳에 드러나있지 않아 나중에 차원을 하나 더 추가할 수밖에 없다는 것이다.

그렇다면 다음 후보를 사용해보자.

테이블 안의 데이터는 문제에서 예시로 주어진 ACAYKP와 CAPCAK을 사용했다.

ACAYKP
C
A
P
C
A
K

문자열의 순서도 잘 표현되어 있고, 최장 공통 부분 수열도 이 모델을 통해 나타낼 수 있을 것 같다. (왼쪽 위로부터 오른쪽 아래까지 이어지는 꺾은선 그래프)

문제에서 최장 공통 부분 수열 그 자체를 구하는 것이 아니라, 그 수열의 길이에만 관심이 있으므로, 이 공간의 각각의 칸에는 수열의 길이를 기록하는 것으로 시작해보자.

ACAYKP

CAPCAK

위 두 문자열에서 “A” 혹은 “C”라는 공통 문자가 나오기 전까지는 최장 공통 부분 수열의 길이가 0이다. 초기 상태를 0으로 설정해보자.

-ACAYKP
-0000000
C0
A0
P0
C0
A0
K0
ACAYKP
^

CAPCAK
 ^

와 같이 A로 시작하는 최장 공통 부분 수열과,

ACAYKP
 ^

CAPCAK
^

와 같이 C로 시작하는 최장 공통 부분 수열을 생각해볼 수 있다. 이것을 위 공간에 표시해보자.

-ACAYKP
-0000000
C01
A01
P0
C0
A0
K0

그런데 이런 생각을 해볼 수 있다. A로 시작하는 최장 공통 부분 수열이 있다면, 첫번째 문자열에서의 포인터가 1번째를 넘어가고, 두 번째 문자열에서의 포인터가 2번째를 넘어가는 모든 경우에서 최장 공통 부분 수열의 길이는 최소한 1 이상이 보장된다는 것이다. 즉

ACAYKP
^
CAPCAK
 ^

위와 같은 경우에서 첫번째 문자열에서는 C, A, Y, K, P로 점프할 수 있고, 두번째 문자열에서는 P, C, A, K로 점프할 수 있는데, 이렇게 두 포인터가 점프하는 모든 경우의 수에서 최장 공통 부분 수열의 길이는 최소 1이라는 것이다. 이것을 표로 표현하면 다음과 같다.

-ACAYKP
-0000000
C01
A01
P011111
C011111
A011111
K011111

이렇게 발견한 사실을 일반화하면, x행 y열의 값이 n일 때, x+1행 이하이면서 y+1열 이하인 곳의 값은 n 이상이라는 것이다. C로 시작하는 최장 공통 부분 수열의 경우도 표시해주자.

-ACAYKP
-0000000
C01
A011111
P011111
C011111
A011111
K011111

이러한 현상은 행의 값과 열의 값이 같을 때 일어났다. 그렇다면 아래 경우를 표기하면 어떻게 될까?

ACAYKP
  ^
CAPCAK
 ^

이 경우에는 CA와 같이 최장 공통 부분 수열의 길이가 2이다. 표를 통해 나타내면

-ACAYKP
-0000000
C01
A012111
P011111
C011111
A011111
K011111

이고, 이는 앞서 발견한 규칙으로 인해 아래와 같이 값이 변경된다.

-ACAYKP
-0000000
C01
A012111
P011222
C011222
A011222
K011222

이 과정을 반복하면 다음과 같이 값이 모두 변경된다.

-ACAYKP
-0000000
C0010000
A0102111
P0011223
C0021222
A0113222
K0012343

이렇게 하면 이 표에서의 최댓값인 4를 통해 원하는 값을 얻어낼 수 있다.

이제 구현을 쉽게 하기 위해, 표의 값이 변경되는 구간인 열과 행의 값이 같은 경우를 하이라이팅해보자.

-ACAYKP
-0000000
C0010000
A0102111
P0011223
C0021222
A0113222
K0012343

구현에 약간의 애로사항이 있는데, 예를 들어 

ACAYKP
 ^
CAPCAK
   ^

와 같은 경우 이전 값으로부터 최장 공통 부분 수열의 길이가 1이었다는 사실을 알기 위해서는 그 칸에 저장되어 있던 숫자를 읽어야 한다.

그런데 이 숫자를 업데이트하는 과정에서 문제가 발생하는데, 최악의 경우, n개의 길이를 갖는 같은 문자열 두 개가 주어졌다고 하면 n*n번 동안 n*n의 공간을 업데이트해줘야 한다.

우리가 관심을 갖는 것은 안쪽(위 예시에서, A, Y, K, P와 A, K로 이뤄진 공간)이고 우리가 구해야 하는 것은 공통 부분 수열의 최대 길이이므로, 바깥쪽 공간의 숫자가 0이 아닌 모두 1로 칠해지더라도 문제 없을 것이다.

-ACAYKP
-1111111
C1111111
A1112222
P1112223
C1122222
A1123333
K1123344

이렇게 해보았더니 마치 양파같은 공간(오른쪽 아래로 갈수록 숫자가 커지는 영역이 만들어짐)으로 만들어진다. 이경우, 아까와 같이 

ACAYKP
 ^
CAPCAK
   ^

와 같은 경우에서 그 왼쪽 위 대각선 칸의 값에 +1을 한 값을 저장한다면 칸을 매번 업데이트해야 하는 일 없이 다음 값을 구할 수 있다.

이때 그 왼쪽 위 대각선 방향의 칸이어야 하는 이유는,

ACAYKP
 ^
CAPCAK
^
ACAYKP
 ^
CAPCAK
   ^

위와 같이 한쪽 포인터를 움직이지 않은 채로 다른 쪽 포인터만 이동시키는 것은 공통 부분 수열의 길이를 늘리는 데에 일조하지 않기 때문이다.

따라서 내 쪽과 다른 쪽의 포인터가 모두 움직인 영역, 즉 a행 b열이라고 할 때 a-1행이면서 b-1열인 부분에서의 값을 가져와야 하는 것이다.

-ACAYKP
-1111111
C1111111
A1112222
P1112223
C1122222
A1123333
K1123344

왼쪽 위 대각선 칸의 값에 +1을 한 값을 가져온다면, 예외가 생기는데 

ACAYKP
^
CAPCAK
 ^

또는 

ACAYKP
 ^
CAPCAK
^

와 같은 구간인 것이다.

그러므로, a행 b열에서 두 문자열의 두 포인터가 같은 문자를 가리킨다고 해도, 바깥쪽 영역을 모두 1로 색칠하지 않고, a행을 포함한 a행 이하와 b열을 포함한 b행 이하를 색칠하는 것으로 규칙을 변경하자.

이런 식으로 변경한다고 하더라도, 문제될 이유가 없는 이유는, 우리가 양파 안쪽 껍질에만 관심을 가지기 때문이다.

-ACAYKP
-0000000
C0011111
A0112222
P0112223
C0122222
A0123333
K0123344

따라서 이와 같이 모델을 나타낼 수 있다.

이를 통해 점화식을 도출해낼 수 있는데,

  • 만약 행과 열의 문자가 같을 경우: 왼쪽 위 칸에 저장된 값에 1을 더해 자기 자신 칸에 저장한다. (최장 공통 부분 수열의 길이가 길어짐을 표현하기 위함)
  • 그 밖의 경우: 자신 바로 위 칸이나 바로 왼쪽 칸에 저장된 값 중 더 큰 값을 자기 자신 칸에 저장한다. (양파 껍질의 형성을 위함)

그렇게 정리가 된다면 아래와 같이 코드를 짤 수 있다.

코드를 짜는 과정은 쉬우니 설명을 생략하겠다.

import sys

string1 = sys.stdin.readline().strip()
string2 = sys.stdin.readline().strip()
memo = [[0 for _ in range(len(string2)+1)] for _ in range(len(string1)+1)]

for i in range(len(string1)):
    for j in range(len(string2)):
        memo[i][j] = memo[i-1][j-1] + 1 if string1[i] == string2[j] \
            else max(memo[i-1][j], memo[i][j-1])

print(max(map(max, memo)))

이렇게 하면 모든 경우의 수를 고려하게 되면서도, 계산량을 줄일 수 있다.

profile
Lee Yechan
이예찬
이전 포스트

(Python) 백준 1107

다음 포스트

(Python) 백준 13549

0개의 댓글