파이썬 백준 알고리즘: 최장 공통 부분 수열(LCS) 9251

안녕하세요! 알고리즘 풀이 포스트를 작성할 개발자로 도움을 드릴게요. 이번에는 "최장 공통 부분 수열" 문제를 다루어보려고 합니다. 최장 공통 부분 수열(LCS) 문제는 두 개의 문자열에서 공통으로 나타나는 가장 긴 부분 수열을 찾는 문제입니다.

문제 내용

주어진 두 개의 문자열에서 최장 공통 부분 수열의 길이를 구하는 문제입니다. 최장 공통 부분 수열은 첫 번째 문자열과 두 번째 문자열 모두에 존재하는 부분 수열 중 가장 긴 것을 말합니다.

문제 이해하기

주어진 문제를 풀기 위해 다이나믹 프로그래밍(Dynamic Programming)을 활용합니다. 다이나믹 프로그래밍은 큰 문제를 작은 문제로 나누어 푸는 방법입니다.

주어진 문제에서는 두 개의 문자열에서 최장 공통 부분 수열의 길이를 구해야 합니다. 이를 위해 두 개의 문자열을 비교하면서 공통 부분 수열을 찾습니다.

주어진 코드에서는 get_lcs() 함수를 사용하여 최장 공통 부분 수열의 길이를 계산합니다. 이를 위해 다이나믹 프로그래밍을 적용하여 2차원 배열 **lcs**를 생성합니다.

lcs 배열의 각 원소 **lcs[i][j]**는 첫 번째 문자열의 인덱스 **j**까지와 두 번째 문자열의 인덱스 **i**까지의 부분 수열 중 최장 공통 부분 수열의 길이를 저장합니다.

1. 다이나믹 프로그래밍 점화식:
   • 두 문자가 같은 경우: lcs[i][j] = lcs[i - 1][j - 1] + 1
   • 두 문자가 다른 경우: lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1])

최장 공통 부분 수열의 길이는 lcs 배열의 마지막 원소인 **lcs[-1][-1]**에 저장되어 있습니다.

풀이 코드

pythonCopy code
def get_lcs():
    lcs = [[0] * (len_first + 1) for _ in range(len_second + 1)]
    for i in range(1, len_second + 1):
        for j in range(1, len_first + 1):
            if first[j - 1] == second[i - 1]:
                lcs[i][j] = lcs[i - 1][j - 1] + 1
            else:
                lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1])
    return lcs[-1][-1]
 
if __name__ == '__main__':
    first, second = input(), input()
    len_first, len_second = len(first), len(second)
    print(get_lcs())
 

풀이 방법

1. get_lcs() 함수를 정의하여 최장 공통 부분 수열의 길이를 반환하는 함수를 구현합니다.
2. **lcs**라는 2차원 배열을 생성합니다. lcs 배열의 크기는 **(len_second + 1) × (len_first + 1)**이며, 모든 원소는 0으로 초기화됩니다.
3. 이중 반복문을 통해 lcs 배열을 채웁니다. **i**는 두 번째 문자열의 인덱스, **j**는 첫 번째 문자열의 인덱스를 나타냅니다.
4. 문자열의 각 위치를 비교하여 같은 문자인 경우 이전 부분 수열의 길이에 1을 더해 저장합니다.
5. 문자열의 각 위치를 비교하여 다른 문자인 경우 이전 위치에서의 최장 공통 부분 수열의 길이 중 최댓값을 선택하여 저장합니다.
6. **lcs[-1][-1]**에는 최장 공통 부분 수열의 길이가 저장되어 있으므로, 이를 반환합니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(n × m)입니다. 이는 첫 번째 문자열의 길이를 n, 두 번째 문자열의 길이를 m이라고 할 때, lcs 배열을 채우기 위해 이중 반복문을 수행하기 때문입니다. 따라서 전체적인 시간 복잡도는 O(n × m)입니다.

 

 

혹시 문제가 잘 안풀리고 답답하신가요? 아래를 눌러 백준 알고리즘 트랜드와 기출문제를 알아보세요! 이것만 알아도 네카라뿌십니다~

 

👉 백준 알고리즘 모음