백트래커의 도전장: 탐욕·게으름·소유

아침에 사무소 문틈에 검은 봉투가 끼어 있습니다. 안에는 카드 한 장. 소장이 카드를 불빛에 비춰 보고는 책상 위에 내려놓습니다. "드디어 인사를 하는군. 얼굴 대신 서명으로."

^(a|aa)+$

이 패턴은 정답을 맞힌다. 그런데 왜 이렇게 느린가?
답은 패턴으로 보내라.
                                        (a+)+$

"정규식 엔진이 어떻게 생각하는지 알아야 풀 수 있는 문제야." 소장이 말합니다. "오늘은 엔진의 머릿속을 들여다보자."

8-1. 엔진은 앞에서부터 시도하고, 막히면 되돌아간다 (10분)

정규식 엔진은 패턴을 왼쪽부터 한 조각씩 문자열에 맞춰 봅니다. 맞지 않으면 바로 포기하지 않고, 방금 내린 선택을 하나 되돌려 다른 길을 시도합니다. 이것을 역추적(backtracking)이라고 합니다.

3교시에 수량자는 기본적으로 "가능한 한 많이 먹는다(탐욕적)"고 했습니다. HTML에서 태그를 뽑는 예로 그 결과를 봅시다.

html = "<b>bold</b> and <i>it</i>"
re.findall(r"<.+>", html)   # ['<b>bold</b> and <i>it</i>']

태그 네 개가 아니라 줄 전체가 하나로 잡혔습니다. 엔진이 한 일을 따라가 보면 이렇습니다.

1. <가 맨 앞의 <에 맞습니다.
2. .+가 탐욕적이라 줄 끝까지 전부 먹습니다.
3. 이제 패턴의 >를 맞춰야 하는데 남은 글자가 없습니다. 실패.
4. .+가 먹은 글자를 하나씩 돌려주며 다시 시도합니다. 맨 마지막 >를 돌려받는 순간 성공합니다.

결과는 "가장 바깥 <부터 가장 마지막 >까지"입니다. 틀린 건 엔진이 아니라 패턴입니다.

8-2. 게으른 수량자: *? +? ?? {m,n}? (8분)

수량자 뒤에 ?를 붙이면 가능한 한 적게 먹는 게으른(lazy) 수량자가 됩니다. 일단 최소한만 먹고, 뒤가 맞지 않을 때만 한 글자씩 더 먹습니다.

re.findall(r"<.+?>", html)          # ['<b>', '</b>', '<i>', '</i>']
re.findall(r"a+?", "aaa")           # ['a', 'a', 'a']
re.findall(r"a??", "a")             # ['', 'a', '']
re.search(r"\d{2,4}?", "12345").group()   # '12'

게으른 수량자는 "어디서 멈출지"를 바꿉니다. 그래서 태그처럼 끝 표시가 분명한 것을 짧게 잡을 때 편합니다.

8-3. 같은 문제, 세 가지 답 (4분)

태그를 뽑는 방법을 나란히 놓아 봅니다.

<[^>]+>는 2교시의 부정 클래스로 ">가 아닌 글자들"만 먹습니다. 되돌아갈 일이 거의 없어서 가장 빠르고 뜻도 분명합니다. 소장은 이렇게 말합니다. "게으름보다 정확함이 낫다."

8-4. 도전장의 답: 되돌아갈 길이 너무 많다 (8분)

이제 카드의 패턴 ^(a|aa)+$를 봅니다. 이 패턴은 "a가 하나 이상 이어진 문자열 전체"를 찾습니다. 뜻은 ^a+$와 같습니다.

bool(re.fullmatch(r"^(a|aa)+$", "aaaa"))   # True
bool(re.fullmatch(r"^a+$", "aaaa"))        # True

문제는 맞지 않는 문자열을 만났을 때입니다. aaaa…ab처럼 끝에 b가 붙으면, 엔진은 a들을 a와 aa로 나누는 모든 방법을 하나씩 시도한 뒤에야 실패를 인정합니다. 나누는 방법의 수는 a의 개수가 늘수록 폭발적으로 늘어납니다.

사무소 컴퓨터(Python 3.14)에서 직접 잰 시간입니다.

a가 4개 늘 때마다 약 7배씩 느려집니다. 같은 비율이면 40개일 때는 10초를 훌쩍 넘습니다. 이렇게 겹치는 선택지를 가진 반복이 역추적을 폭발시키는 전형적인 모양입니다. (a+)+처럼 반복 안에 반복이 있는 것도 같은 종류입니다.

8-5. 돌려주지 않는 수량자: *+ ++ ?+ {m,n}+ (6분)

Python 3.11부터 수량자 뒤에 +를 붙이면 소유(possessive) 수량자가 됩니다. 한 번 먹은 글자는 뒤가 실패해도 돌려주지 않습니다. 되돌아갈 길 자체를 없애는 것입니다.

re.fullmatch(r"a*a", "aaa")    # <re.Match object; span=(0, 3), match='aaa'>
re.fullmatch(r"a*+a", "aaa")   # None

a*+a는 어떤 문자열에도 매치하지 않습니다. a*+가 a를 전부 가져가 돌려주지 않으니, 뒤의 a가 맞출 글자가 남지 않기 때문입니다. 반대로 이 성질 덕분에 카드의 패턴도 고칠 수 있습니다.

re.search(r"^(?:a|aa)++$", "a" * 28 + "b")   # None (곧바로 끝난다)

++가 그룹의 반복을 소유로 만들어, 실패하면 다른 나누기를 시도하지 않고 바로 포기합니다.

8-6. 통째로 돌려주지 않는 그룹: (?>...) (4분)

원자 그룹(atomic group) (?>...)도 3.11부터 쓸 수 있습니다. 그룹 안이 한 번 매치되면, 그 결과를 통째로 확정하고 안으로 되돌아가지 않습니다. 소유 수량자는 사실 원자 그룹의 줄임말입니다. a++는 (?>a+)와 같습니다.

re.fullmatch(r"(?>a+)b", "aab")   # <re.Match object; span=(0, 3), match='aab'>
re.fullmatch(r"(?>a+)a", "aaa")   # None

사건 해결 (10분)

소장과 함께 답장을 정리합니다. 느린 패턴을 고치는 방법은 세 가지입니다.

1. 겹치지 않게 다시 쓴다. 같은 글자를 여러 방법으로 나눌 수 없게 만든다. ^(a|aa)+$ 대신 ^a+$.
2. 되돌아갈 길을 없앤다. 소유 수량자 ^(?:a|aa)++$나 원자 그룹 ^(?>(?:a|aa)+)$.
3. 바깥에서 막는다. 입력 길이를 제한하고, 남이 보낸 패턴은 시간 제한이 있는 곳에서만 실행한다. 이 분석실이 패턴을 별도 프로세스에서 돌리고 0.3초가 넘으면 멈추는 것이 그런 장치다. (서드파티 패키지 regex에는 timeout 인자가 있다.)

import time
text = "a" * 40 + "b"
start = time.perf_counter()
print(re.search(r"^a+$", text))             # None
print(time.perf_counter() - start < 0.01)   # True

신입 탐정은 카드 뒷면에 ^a+$라고 적어 봉투에 넣습니다. 소장이 고개를 끄덕입니다. "짧고, 읽히고, 빠르다. 좋은 답장이야."

실습 과제

1. re.findall(r'".+"', 'say "hi" and "yo"')의 결과를 예상하고, 따옴표 하나씩 잡도록 두 가지 방법(게으른 수량자, 부정 클래스)으로 고쳐 보세요.
2. (\d+)+$가 왜 위험한 모양인지 설명하고, 같은 뜻의 안전한 패턴을 써 보세요.
3. a{2,4}?와 a{2,4}+를 "aaaaa"에 findall로 돌리면 각각 무엇이 나올까요? 분석실에서 확인해 보세요.