[백준] 18438 LCS 5 C++

두 문자열 사이의 최장 공통 부분 수열(LCS)을 구하는 문제는 두 문자열의 부분 문자열 간 순서를 유지하는 최대 길이의 공통 부분 문자열을 찾는 문제로, 전통적인 동적 계획법은 O(nm)의 시간과 O(nm)의 메모리를 필요로 한다. 본 글은 이를 분할 정복 기법으로 복원하는 방법을 소개하며, 메모리 사용량을 크게 줄이고 큰 입력에서도 효과적으로 동작하는 알고리즘을 제시한다. 예를 들면 a = "ACDBE"와 b = "ABCDE"일 때 LCS는 "ACDE"가 된다.

주요 흐름은 이분으로 나누어 전방과 후방의 LCS를 각각 계산한 뒤 최적의 분할 지점을 찾아 재귀적으로 해결하는 방식이다. 먼저 문자열 a를 가운데에서 두 구간으로 나눈 뒤, 앞부분 a[al..ah]와 나머지 부분 a[ah+1..ar]에 대해 각각 LCS를 계산한다. 전방 LCS는 좌에서 우로, 후방 LCS는 우에서 좌로 계산하여 각 지점까지의 LCS 길이를 배열에 저장한다. 두 배열의 값을 합쳐 최적의 분할 인덱스를 찾고, 그 지점을 기준으로 두 부분 문제로 재귀적으로 LCS를 복원한다. 가장 작은 구간의 기저 사레는 a 구간 길이가 1인 경우로, 해당 문자와 b 구간 어디에 매칭되는지 확인하여 결과에 추가한다.

구현은 최적화된 전방 LCS와 후방 LCS 계산을 반복적으로 수행한다. 전방 LCS는 이차원 DP를 한 행씩 갱신하는 형식으로 진행되며, 각 i에 대해 tmp를 사용해 이전 행의 값을 보존하고 현재 행의 값을 새로 계산한다. 후방 LCS 역시 역방향으로 진행하며 tmp를 사용해 다음 행의 값을 참조한다. 그런 다음 LCS1[j] 와 LCS2[j+1]의 합이 최대가 되도록 분할 지점을 선정하고, 재귀 호출로 두 부분을 각각 처리한다. 최종적으로 얻은 LCS의 길이와 문자열은 출력된다.

시간 복잡도는 전체적으로 O(nm)으로 유지되지만, 메모리 사용량은 O(m) 수준으로 대폭 절감된다. 이는 중간 배열과 임시 변수만 필요한 방식으로 구현되기 때문이며, 외부 반복 없이 각 분할에서만 필요한 공간을 사용한다. 전체 코드는 입력된 두 문자열을 바탕으로 lcs 함수를 호출해 LCS를 복원하고, LCS의 길이와 문자열을 출력하도록 구성된다. 끝으로 C++ 코드의 최적화 지시문과 함께 구현된 로직은 분할 정복과 전방·후방 LCS의 조합으로 LCS를 효율적으로 복원하는 과정을 보여 준다.