30 핵심 알고리즘 Ep:04 - 투 포인터 기법
Source: Dev.to
왜 두 포인터 기법은 실제로 조정에 관한 것인가
두 포인터 기법은 종종 트릭으로 가르쳐진다.
- 왼쪽에서 하나의 포인터를 이동시킨다.
- 오른쪽에서 또 다른 포인터를 이동시킨다.
- 중간 어딘가에서 만나게 된다.
그것이 작동하기 때문에, 기억해야 할 패턴으로 여기기 쉽다.
그런 관점은 이 기법이 실제로 하는 일을 놓친다.
두 포인터는 배열을 더 빠르게 스캔하는 것이 아니다.
그것은 공유된 제약 하에서 움직임을 조정하는 것이다.
혼자 이동하는 비용
큰 정렬된 구조에서 어떤 조건을 찾는다고 상상해 보세요.
한 가지 방법은 한쪽 끝에서부터 한 단계씩 움직이며 모든 것을 확인하는 것입니다. 이는 직관적이고 신뢰할 수 있지만, 중요한 점을 간과합니다: 구조 자체가 이미 어디를 보지 말아야 할지 알려주고 있기 때문입니다.
단일 포인터로 이동하면 그 정보를 낭비하게 됩니다. 각 단계는 다른 곳에서 일어나는 상황과 연결되지 않은 지역적인 결정만을 반영합니다. 진행은 이루어지지만, 느리게 진행됩니다.
두 포인터: 정렬을 통한 진행
두 번째 포인터를 도입하는 순간, 문제는 달라집니다.
이제 모든 움직임이 상대적입니다. 한 포인터는 다른 포인터가 보는 것에 따라 전진합니다. 결정은 고립된 것이 아니라 쌍으로 이루어집니다.
다음과 같이 묻는 대신:
“다음에 무엇을 해야 할까?”
시스템은 이렇게 묻습니다:
“이 두 위치를 어떻게 함께 움직여야 할까?”
그러한 조정은 추가 메모리나 복잡한 로직 없이도 가능성을 빠르게 축소합니다.
왜 순서가 그렇게 중요한가
Two Pointers는 움직임에 의미가 있을 때만 작동한다:
- 정렬된 배열
- 단조 시퀀스
- 구조화된 경계
순서가 없으면 포인터 이동은 추측에 불과하다. 순서가 있으면 각 단계가 전체 상태 클래스를 제거한다. 그래서 이 기법은 올바른 상황에서는 거의 마법처럼 느껴지고, 잘못된 상황에서는 완전히 쓸모가 없다. 힘은 포인터에서 오는 것이 아니라 데이터가 제공하는 보장에 있다.
제약 조건 해결사로서의 두 포인터
많은 두 포인터 문제는 실제로 탐색에 관한 것이 아니다. 불변 조건을 유지하는 것이다:
- 범위 내에 있어야 하는 합
- 조건을 만족해야 하는 윈도우
- 제한을 초과해서는 안 되는 거리
포인터는 탐색하기 위해 움직이는 것이 아니라 재조정하기 위해 움직인다. 한 쪽이 제약을 위반하면 다른 쪽이 보상한다. 알고리즘은 시스템을 지속적으로 유효성 쪽으로 미묘하게 조정한다. 그 피드백 루프가 진정한 메커니즘이다.
슬라이딩 윈도우는 대화이다
슬라이딩 윈도우 기법은 이유가 있어 종종 두 포인터와 함께 묶여 설명됩니다.
- 왼쪽 포인터는 제약을 강화합니다.
- 오른쪽 포인터는 제약을 완화합니다.
두 움직임 중 어느 하나만으로는 의미가 없습니다. 함께 할 때, 조건을 중심으로 확장하고, 수축하고, 안정화하는 대화를 형성합니다. 이것이 순수한 형태의 협조입니다.
두 포인터가 무너지기 쉬운 경우
Two Pointers는 협력을 전제로 합니다. 포인터가 움직일 때 데이터가 예측 가능하게 반응해야 합니다. 구조가 단조롭게 변하지 않으면 조정이 실패합니다. 그래서 이 기법은 다음과 같은 경우에 어려움을 겪습니다:
- Unsorted data
- Non‑monotonic conditions
- Problems requiring global context
지역적인 움직임이 조건을 일관되게 개선하거나 악화시키지 못할 때, 포인터 이동은 신호를 잃게 됩니다. 이 기법은 취약한 것이 아니라, 그 한계에 대해 솔직합니다.
명시적인 트레이드오프
Two Pointers는 일반성을 희생하여 공간과 시간을 최적화합니다. 모든 경우를 탐색하거나, 되돌아가거나, 잘못된 가정으로부터 회복하지 않습니다. 그러나 제약 조건이 만족될 때 최소한의 노력과 거의 오버헤드 없이 답을 도출합니다. 이것이 의도된 트레이드오프입니다.
Takeaway
Two Pointers 기법은 지름길이 아니다. 움직임이 독립적이지 않도록 보장함으로써 진행을 이루는 방법이다. 모든 단계가 다른 단계에 의해 안내되고, 모든 결정은 제약 조건과 균형을 이룬다.
이 개념은 배열을 넘어선 곳에서도 나타난다 — 시스템이 동시에 움직이며 범위 내에 머무르는 모든 곳에서. 그래서 Two Pointers는 교묘한 트릭이 아니라 핵심 기법으로 남아 있다.