[SW 정글 25일차] LCS는 왜 그렇게 될까?

오늘은 다이나믹 프로그래밍, 그리디 알고리즘을 공부하는 주차로 다이나믹 프로그래밍 문제 중에 LCS(Longest Common Subsequence, 최장 공통 부분 수열)라는 문제가 있었다.

https://www.acmicpc.net/problem/9251

9251번: LCS

이전에 푼 경험이 있어 접근법을 알고 있어 나는 풀기는 했지만 다른 동료가 와서 왜 이렇게 되는지에 대한 질문을 던졌고 나는 명확한 답변을 해주지 못했다.

질문은 이렇다.

문자열 1과 문자열 2에 가장 최근에 추가된 글자가 서로 같을 때 왜 'matrix[i][j] = matrix[i - 1][j - 1] + 1' 이렇게 되는 것인가이다.

 

대부분의 블로그에서는 이 부분에 대해 명확한 설명이 없고 그냥 저렇게만 쓰여있었다.

그래서 Introduction to algorithms이라는 책과 유튜브 강의를 통해 왜 그렇게 되는지를 이해했다.

 

 

1. 코드부터 보자.

import sys

string1 = ' ' + sys.stdin.readline().rstrip()
string2 = ' ' + sys.stdin.readline().rstrip()
LCS = [[0 for _ in range(len(string2))] for _ in range(len(string1))]

for i in range(1, len(string1)):
    for j in range(1, len(string2)):
        if string1[i] == string2[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])

아마 코드를 기반으로 접근하는 설명들은 처음 이 문제를 처음 접하는 사람에게 이해가 되도록 도움을 주지는 못한다.

왜 그럴까?라고 생각해봤을 때 코드만 보았을 때 접근방식이 작은 것부터 시작해 점점 커지는 구조이다.

그러면 Bottom up 방식으로 접근하는 것으로 보이고 전체적인 그림을 모르면 당연히 문자가 같았을 때 왜 이전의 값이 대각선의 값일까하는 의문이 들 수 밖에 없다.

 

 

 

2. 그러면 어떻게 접근하는 걸까?

LCS는 하나의 큰 문제를 부분 문제(Sub problem)로 쪼개어 생각해서 그 쪼개어진 결과를 통해 최종 값을 얻는 것이다.

그러면 어떻게 부분 문제로 쪼개어지는지 확인해보자.

간단한 예시로 s1을 "abcd" s2를 "bcdd"라고 생각하고 LCS를 구해보자.

먼저, 두 문자열의 맨 뒤의 값이 같은지와 다른지를 확인한다.

위 예시에서는 같으므로 LCS에 +1이 될 것이고 두 값이 없는 "abc"와 "bcd"의 LCS를 구하는 sub problem이 된다.

다시 sub problem을 보면 두 문자열의 맨 뒤의 값이 다른 것을 볼 수 있다.

이러한 경우에는 한 문자열에서만 맨 뒤의 값을 빼준경우의 LCS들을 구해서 그 중 큰 값을 얻으면 된다.

이렇게 계속해서 두 문자열의 마지막 값을 비교하면서 같을 떄와 다를 때 sub problem이 달라지게 된다.

마지막에는 어떻게 나뉘는지 결과는 아래의 그림과 같다.

이렇게 여러 개의 sub problem으로 나뉘어지게 되고 해당 sub problem을 해결하면서 다시 올라가면 전체 문제를 풀 수있는 구조이다.

그래서 코드가 sub problem부터 해결하면서 전체 문제의 값을 구하기 위해 이중 for문을 쓰는 구조로 되어 있는 것인데 그냥 단순히 설명만 한 줄쓰고 코드를 보여주면 당연히 오해를 불러일으키고 이해도 전혀되지 않는 것이다.

---

 

[오늘의 나는 어땠을까?]

오늘은 3주차를 끝내면서 오전에 모의고사를 보고 4주차가 시작되었다.

모의고사 결과는 1.5솔이다. (0.5솔이라고 하는 이유는 한 문제를 50%정도 통과해서 그냥 0.5솔로..)

오늘 모의고사를 통해 성장했다고 느꼈다.

마지막 문제는 접근법을 떠올리지 못했지만 2문제의 접근법을 빠르게 떠올렸고 그 접근법이 정답으로 가는 길이였다.

이전에는 이 정도로 빠르게 생각해냈지 못했는데 내가 노력한 결과라고 생각하고 성장 중이라고 생각한다.

 

오늘도 매 주 진행되는 소규모 면담에 참여했다.

3가지의 질문을 했는데 그 중 내가 좋아하는 영역에서 깊이있게 알아보는 것은 어떠한 것을 의미하는 것인지였다.

운영진님들께서 좋은 사례를 들며 앞으로의 나에게 도움이될 수 있는 대답을 해주셨다.

그리고 면담이 끝나고 나가기 전, 장병규 의장님께서 좋은 질문들을 가져온다고 말해주셨다.

마음 속으로 굉장히 기분이 좋았고 내가 성장하기 위해서 가지는 궁금증이 좋은 생각이라고도 해석이 되기도 했다.

나중에는 장병규 의장님 뿐만 아니라 많은 사람들에게 좋은 개발자(좋은 개발자라는 말은 사람들에 따라 다르지만..)라는 말을 듣고 싶다.

 

---

<참고 자료>

Introduction To Algorithms, Third Edition

https://www.youtube.com/watch?v=ASoaQq66foQ&t=1141s