Greedy 매칭 — 기본 동작

~10 min · greedy, engine

Level 0패턴 호기심

0 XP0/90 lessons0/15 achievements

0/100 XP to next level100 XP to go0% complete

Quantifier 는 기본적으로 가능한 만큼 잡음

기본적으로 모든 quantifier 는 greedy. 가능한 만큼 글자 소비, 패턴 나머지가 매칭 실패할 때만 backtrack.

고전 예시: 패턴 a.*b 입력 a123b456b. 순진한 기대: a123b 매칭 (a 뒤 첫 b). 현실: a123b456b 매칭 (첫 a 부터 마지막 b 까지 전부).

왜 기본이 greedy

Backtracking. 엔진이 .* 를 문자열 나머지 전체에 매칭 시도, b 가 안 따라옴 (문자열 끝이니까), 그 다음 한 글자씩 backtrack 후 다시 시도. 리터럴 b 가 매칭하는 위치 찾을 때까지 backtrack 계속 — 그게 마지막 b 에서 일어남, 첫 게 아니라.

"greedy 는 가능한 가장 길게" 가 박이면 정규식의 놀람 절반이 놀람 안 됨.

Greedy 함정

입문 정규식 가장 흔한 실수: .* (greedy) 로 두 마커 사이 부분 문자열 추출 시도. 의도한 끝점 지나서 닫는 마커의 마지막 등장까지 먹어.

Code

Greedy 슬로우모션·python

import re

# Greedy: 가능한 가장 긴 부분 문자열 매칭
re.findall(r'a.*b', 'a123b456b')
# ['a123b456b']  — 'a123b' 만이 아님

# HTML 도 — 재앙
html = '<p>first</p> <p>second</p>'
re.findall(r'<p>.*</p>', html)
# ['<p>first</p> <p>second</p>']  — 두 paragraph 한 매칭으로 먹음

# Greedy + backtracking 시각화
# 패턴: a\d+b 입력 'a12345b6789b' 에 대해
# 1. \d+ 가 '12345b6789' 잡음  → 다음 글자 'b' 여야 함, 위치는 끝 너머
# 2. 한 글자 backtrack: \d+ 가 '12345b678' 됨  → 여전히 'b' 안 옴, 잠깐
# 3. 사실 \d+ 가 'b' 잡을 수 없음 (숫자 아님), 그래서 '12345' 만 잡음
# 4. 그 다음 'b' 가 위치 6 에서 매칭
re.findall(r'a\d+b', 'a12345b6789b')
# ['a12345b']  — \d+ 가 처음부터 b 포함 못 해

External links

Greedy and Lazy quantifiers — regular-expressions.info

Exercise

re.findall(r'".*"', '"a" "b" "c"') 결과 예측. 돌려. 결과가 입문자가 따옴표 문자열 파싱에 .* 싫어하는 이유 설명해야 해.

Progress

Progress is local-only — sign in to sync across devices.

← Previous범위: {n,} 와 {n,m}Next →Lazy (Non-Greedy) 매칭 — *? +? ??

이 페이지에서 버그를 발견하셨거나 피드백이 있으세요?문제 신고

🔔 답글 알림 (로그인 필요)

로그인 — 댓글을 남기려면 로그인해 주세요.

아직 댓글이 없어요. 첫 댓글을 남겨보세요.