정규표현식의 findall은 사실 O(n²)이었다 — 아무도 고치지 않은 이차 시간 복잡도 문제

우리가 당연하게 쓰던 findall의 숨겨진 비용

프로그래밍에서 정규표현식(regex)은 텍스트 처리의 만능 도구처럼 쓰입니다. 로그 파싱, 입력 검증, 데이터 추출 등 거의 모든 곳에서 활용되죠. 그런데 정규표현식으로 문자열에서 "모든 매치를 찾는" 연산, 즉 Python의 re.findall(), JavaScript의 String.matchAll(), 또는 대부분의 언어에서 제공하는 유사한 함수들이 사실 O(n²)의 시간 복잡도를 가지고 있었다는 분석이 공개되었습니다.

O(n²)이라는 것이 왜 문제인지 간단히 짚어보겠습니다. 입력 문자열의 길이가 n일 때, 선형 시간 O(n)은 입력이 10배 커지면 처리 시간도 약 10배 늘어납니다. 하지만 O(n²)에서는 입력이 10배 커지면 처리 시간이 100배 늘어납니다. 1MB 텍스트에서 0.01초 걸리던 작업이 10MB에서는 1초, 100MB에서는 100초가 걸릴 수 있다는 뜻입니다. 대용량 로그 파일이나 데이터 스트림을 처리할 때 이 차이는 치명적이 됩니다.

왜 O(n²)이 되는가: 기술적 원인

정규표현식 엔진이 단일 매치를 찾는 것은 일반적으로 O(n)에 수행됩니다(역추적(backtracking)이 없는 경우). 문제는 "모든 매치"를 찾을 때 발생합니다.

대부분의 regex 엔진은 findall을 구현할 때 다음과 같은 방식을 사용합니다: 첫 번째 매치를 찾고, 그 매치가 끝난 위치에서 다시 매치를 시작합니다. 매치가 발견되지 않으면 한 글자 전진하고 다시 시도합니다. 이 과정 자체는 직관적이고 올바르지만, 문제는 각 시도에서 regex 엔진이 매번 문자열의 상당 부분을 스캔할 수 있다는 것입니다.

특히 빈 문자열에 매치되는 패턴이나, 매치가 매우 자주 발생하는 패턴에서 이 문제가 두드러집니다. 예를 들어 정규표현식 .*는 각 위치에서 문자열 끝까지 매치를 시도하므로, n개의 위치 × 각 위치에서 최대 n글자 스캔 = O(n²)이 됩니다.

더 근본적인 원인은 regex 엔진의 내부 상태 관리에 있습니다. NFA(비결정적 유한 오토마타) 기반 엔진은 이론적으로 O(n) 매칭이 가능하지만, 실제 구현에서는 매치 위치 간의 상태를 효율적으로 전달하지 못합니다. 첫 번째 매치를 찾은 후 다음 매치를 시작할 때, 이전 매칭 과정에서 이미 수집한 정보를 버리고 처음부터 다시 시작하기 때문입니다.

왜 아무도 고치지 않았나

이 문제가 새로 발견된 것은 아닙니다. 컴퓨터 과학 학계에서는 오래전부터 알려져 있었지만, 실제 프로그래밍 언어의 regex 엔진에서는 수정되지 않았습니다. 이유는 몇 가지가 있습니다.

첫째, 실무에서 잘 드러나지 않습니다. 대부분의 regex 사용은 짧은 문자열이나 한 줄 단위로 이루어지기 때문에, n이 충분히 작아서 O(n²)도 사실상 즉시 완료됩니다. 문제는 대용량 텍스트를 한 번에 처리할 때만 나타납니다.

둘째, 수정이 어렵습니다. findall의 O(n) 구현을 위해서는 regex 엔진의 내부 구조를 상당히 변경해야 합니다. 매칭 과정에서 발생하는 모든 매치 후보를 동시에 추적해야 하고, 이는 엔진의 복잡도를 크게 높입니다.

셋째, 하위 호환성 문제입니다. regex의 동작은 많은 코드에서 암묵적으로 의존하는 부분이기 때문에, 내부 구현을 변경하면 미묘한 동작 차이가 발생할 수 있습니다.

비교: Rust의 regex 크레이트는 다르다

Rust의 regex 크레이트는 이 문제에 대해 비교적 나은 접근을 취하고 있습니다. Andrew Gallant(burntsushi)가 만든 이 라이브러리는 처음부터 선형 시간 보장을 설계 목표로 삼았습니다. 역추적을 사용하지 않는 NFA/DFA 기반 엔진을 사용하며, 일부 findall 시나리오에서도 선형에 가까운 성능을 제공합니다.

Google의 RE2도 비슷한 접근을 취합니다. RE2는 역추적 없이 동작하는 regex 엔진으로, 최악의 경우에도 입력 크기에 선형적인 시간을 보장합니다. 대신 PCRE(Perl Compatible Regular Expressions)의 일부 고급 기능(역참조 등)을 지원하지 않는 트레이드오프가 있습니다.

반면 Python의 re 모듈, JavaScript의 내장 regex, Java의 java.util.regex 등 대부분의 주류 언어들은 역추적 기반 엔진을 사용하고 있어 이 문제에 취약합니다.

한국 개발자에게 주는 시사점

실무에서 이 문제가 영향을 미칠 수 있는 상황은 명확합니다. 대용량 로그 파일 분석, 웹 크롤링 결과 파싱, 대규모 텍스트 데이터 전처리 등에서 regex findall을 사용하고 있다면 성능을 점검해볼 필요가 있습니다.

만약 성능 문제가 확인된다면, 몇 가지 대안이 있습니다. 입력을 줄 단위로 나눠서 처리하면 각 줄의 n이 작아져 O(n²)의 영향이 줄어듭니다. 또는 regex 대신 문자열의 split(), find() 등 단순한 문자열 함수로 대체할 수 있는지 검토해볼 수 있습니다. 성능이 정말 중요한 경우 Rust의 regex 크레이트를 Python에서 바인딩해 사용하는 방법도 있습니다.

마무리

"모든 매치 찾기"라는 평범해 보이는 연산에 O(n²)이 숨어 있었다는 사실은, 우리가 표준 라이브러리를 얼마나 맹목적으로 신뢰하는지를 상기시켜줍니다. 여러분의 코드에서 regex findall이 대용량 데이터를 처리하고 있는 곳이 있다면, 한번 프로파일링해보시는 건 어떨까요?