패턴 인식: 최고 코더들의 비밀 무기
Source: Dev.to
패턴 인식: 최고 수준 코더들의 비밀 무기
빠른 배경 (왜 이 글을 쓰는가)
문제는 이렇다: 나는 LeetCode 중간 난이도 문제에 너무 오래 끼어 있었는데, 솔직히 말하면 인정하고 싶지 않다. 과제는 중복 문자가 없는 가장 긴 부분 문자열을 찾는 것이었다. 나는 가장 직관적인 완전 탐색 방식—중첩 루프, 중복을 확인하기 위한 집합, 그리고 “이 경우엔 이렇게” 같은 수많은 조건문—부터 시작했다. 가장 큰 테스트 케이스에서 내 풀이가 두 시간째 타임아웃되는 걸 보면서, 익숙한 낙심이 찾아왔다: 뭔가 명백한 걸 놓치고 있다.
그때 화면을 바라보며 나는 한 가지를 깨달았다: 중복 문자를 만나면 지금까지 해 온 모든 작업을 버리고 다음 인덱스부터 다시 시작하고 있었다. 마치 못이 휘어질 때마다 집을 처음부터 다시 짓는 듯한 낭비였다. 바로 그 순간 패턴이 떠올랐다: 나는 부분 문자열을 찾는 것이 아니라, 필요에 따라 양쪽 끝을 조정할 수 있는 윈도우를 다루고 있었다.
이 순간—문제가 실제로는 “유효한 윈도우를 유지하는 것”이라는 걸 깨달은 순간—은 몇 시간의 좌절을 날려버렸고, 복잡했던 상황을 깔끔한 O(n) 해결법으로 바꾸어 놓았다.
통찰
최고 수준 코더들은 단순히 알고리즘을 외우는 것이 아니라, 문제의 근본적인 형태를 눈으로 포착한다. “가장 길고/연속적이고/최대/최소 … 라는 조건을 만족하는 무언가”를 요구하는 문제를 보면, 그 형태는 대개 슬라이딩 윈도우이다.
정신적 프레임워크는 다음과 같다:
- 불변식(invariant) 정의 – 윈도우 안에서 언제나 만족해야 할 조건은 무엇인가? (예: 모든 문자가 서로 다름)
- 두 포인터 지정 – 윈도우의 왼쪽과 오른쪽 경계
- 오른쪽 포인터 확장 – 불변식이 유지되는 한 오른쪽을 가능한 한 멀리 이동
- 불변식이 깨지면 – 왼쪽 포인터를 최소한으로 움직여 불변식을 복구, 불필요하게 작업을 버리지 않도록
- 윈도우가 유효할 때마다 최적 해 기록
이 단계에 문제를 매핑할 수 있다면, 이미 절반은 해결한 셈이다. 나머지는 꼼꼼한 bookkeeping에 불과하다.
구현 (코드와 함께)
먼저 흔히 빠지는 함정을 보여주고, 그 뒤에 슬라이딩 윈도우 방식으로 고치는 과정을 살펴보자.
나이브 시도 (O(n²))
def length_of_longest_substring_brute(s: str) -> int:
n = len(s)
best = 0
for i in range(n):
seen = set()
for j in range(i, n):
if s[j] in seen: # duplicate – window invalid
break
seen.add(s[j])
best = max(best, j - i + 1)
return best문제점
시작 인덱스 i마다 seen 집합을 새로 만든다. 문자열이 "abcdefghijklmnopqrstuvwxyz"를 100번 반복한다면, 약 n²/2 번의 연산을 수행하게 된다. 내부 루프가 매번 같은 작업을 반복하는데, 이를 재활용할 수 있다.
슬라이딩 윈도우 돌파구 (O(n))
def length_of_longest_substring(s: str) -> int:
last_index = {} # char -> most recent position
left = 0 # start of current window
best = 0
for right, ch in enumerate(s):
# If ch was seen inside the current window, jump left past it
if ch in last_index and last_index[ch] >= left:
left = last_index[ch] + 1 # = left` guard. Without it, they might slide `left` backward when the duplicate lies *outside* the current window, incorrectly shrinking the window and missing longer substrings.
간단한 검증
assert length_of_longest_substring("abcabcbb") == 3 # "abc"
assert length_of_longest_substring("bbbbb") == 1
assert length_of_longest_substring("pwwkew") == 3 # "wke"모두 통과하고, 알고리즘은 선형 시간에 O(k) 의 추가 공간을 사용한다. 여기서 k는 문자 집합의 크기이며, ASCII 기준이면 상수이다.
왜 중요한가
슬라이딩 윈도우 형태를 인식하는 능력은 면접용 트릭을 넘어 실제 시스템에서도 빈번히 등장한다.
- Rate‑limiting 윈도우 (지난 1분 동안의 요청 수 카운트)
- 네트워크 버퍼 (오래된 패킷을 버리고 최신 패킷을 유지)
- 금융 롤링 평균 (이동 평균, 변동성)
불변식 + 두 포인터 패턴을 눈에 익히면, 매번 새로운 변형을 위해 휠을 다시 만들 필요가 없어진다. 코드량은 줄고, 버그는 감소하며, 실제 비즈니스 로직을 해결하는 데 더 많은 시간을 할애할 수 있다.
가장 좋은 점은 패턴이 이식 가능하다는 것이다. “불변식 정의 → 확장 → 위반 시 수축 → 답 기록”이라는 흐름을 내면화하면, “합이 ≥ target인 최소 크기 부분 배열”이나 “서로 다른 값이 ≤ K개인 가장 긴 부분 배열” 같은 전혀 다른 문제에도 적용할 수 있다.
다음에 “가장 길고/연속적인 … 가 X를 만족한다”는 문장을 마주하면, 잠시 멈추고 스스로에게 물어보라: “구간 안에서 무엇이 항상 참이어야 하는가?” 라는 질문에 답할 수 있다면, 이미 프레임워크를 잡은 셈이다.
당신 차례
다음 문제에서 슬라이딩 윈도우를 찾아보라:
양의 정수 배열과 목표 합
t가 주어질 때, 합이 최소t이상인 연속 부분 배열의 최소 길이를 구하라. 그런 부분 배열이 없으면0을 반환한다.
시도해 보고, 친구와 답을 비교하거나 댓글에 풀이를 남겨라. 어떤 불변식을 정의했는가? 왼쪽 포인터는 어떻게 움직였는가? 즐거운 윈도우 슬라이딩!