[백준] 18439 LCS 6 C++

두 문자열 사이의 최장 공통 부분 수열 LCS는 자주 등장하는 문제로, 일반적인 동적 계획법 DP를 이용하면 시간 복잡도가 O(n*m)이고, 문자열 길이가 커질수록 메모리와 실행 시간이 크게 증가하는 단점이 있다. 본 글은 비트셋 기반의 LCS 알고리즘으로 이를 개선하는 원리와 구현 방법을 설명한다. 핵심 아이디어는 각 문자를 비트로 매핑하는 비트셋의 활용이다. 문자열 b의 각 위치를 비트로 표현하는 비트셋을 구성하고, 2차원 DP의 행렬 계산을 대체하는 방식으로 상태를 갱신한다. 비트 연산의 효율성을 활용하여 비교적 빠르게 LCS를 구하며, 반복문은 CPU에 최적화된 방식으로 수행된다.

비트셋 기반 구현에서 bset은 비트셋을 다루는 커스텀 자료구조로 사용된다. 50,000비트 이상도 다룰 수 있도록 멀티워드를 지원하며, 64비트 단위의 배열로 비트를 관리한다. 기본 생성자는 모든 비트를 0으로 초기화하고, 특정 위치의 비트를 1로 설정하는 기능을 제공한다. 문자열 b의 각 문자를 기준으로 비트셋을 초기화하는데, A 배열은 알파벳 A~Z 각각에 대한 비트셋을 저장한다. 예를 들어 b의 각 위치에 해당하는 문자가 등장하는 위치에 해당 비트가 1로 설정된다.

비트셋을 이용한 LCS 계산은 먼저 B를 DP 상태로 삼아 초기화하고, 문자열 a의 각 문자를 순회하며 상태를 갱신한다. 갱신식은 X = B | A[a[i] - 'A'] 이고, Y = (B << 1) | 1 이다. 그 뒤 B = X & ~(X - Y)를 통해 새로운 상태를 얻는다. 이 과정을 반복하면 최종적으로 B에 남아 있는 비트의 1의 개수가 LCS의 길이가 된다. 최종 길이는 B의 각 워드를 대상으로 __builtin_popcountll()를 적용해 합산한다.

시간 복잡도는 비트 연산의 특성상 문자열 길이에 따라 대략 O(n*m/64)로 처리되어, 일반적인 DP 방식보다 매우 빠르며, 공간 복도는 최대 길이에 의해 O(m/64)로 크게 줄어든다. 코드 전체는 비트셋 구조체와 26개의 알파벳 비트셋 배열, 그리고 LCS 계산 로직으로 구성된다. 입력으로 두 문자열을 받고, 길이가 짧은 쪽을 기준으로 처리하여 A 배열의 비트셋을 구성하고, B를 순차적으로 업데이트한 뒤 최종적으로 LCS의 길이를 출력한다.