투 포인터(Two Pointers)와 슬라이딩 윈도우(Sliding Window) 차이점
코딩 테스트에서 배열이나 문자열을 다루는 문제를 풀 때, 이중 반복문(for문 2개)을 사용하여 전체 경우의 수를 샅샅이 뒤지는 O(N^2) 방식은 가장 직관적이지만 필연적으로 '시간 초과(Time Limit Exceeded)'의 늪에 빠지게 만듭니다. 데이터가 10만 개만 되어도 100억 번의 연산이 필요하기 때문입니다. 이때 O(N^2)의 끔찍한 시간 복잡도를 마법처럼 단 O(N)의 선형 시간으로 줄여주는 구세주 같은 두 가지 알고리즘 기법이 있습니다. 바로 '투 포인터(Two Pointers)'와 '슬라이딩 윈도우(Sliding Window)'입니다. 두 기법 모두 1차원 배열을 단 한 번만 스캔하여 정답을 도출한다는 공통점이 있지만, 포인터(화살표)가 움직이는 방식과 적용해야 하는 문제의 조건이 완전히 다릅니다. 비슷한 듯 전혀 다른 두 기법의 메커니즘을 완벽하게 해부해 보겠습니다.
1. 투 포인터(Two Pointers): 두 화살표의 유연한 합주
투 포인터는 1차원 배열에서 두 개의 포인터(인덱스를 가리키는 변수)를 조작하여 원하는 결과를 얻는 강력한 탐색 알고리즘입니다. 보통 left와 right, 또는 start와 end라는 두 개의 화살표를 배치하고, 특정한 논리적 조건에 따라 이 화살표들을 각각 독립적이고 유연하게 이동시킵니다.
1-1. 대표적인 활용 시나리오: 정렬된 배열에서 두 수의 합 찾기
가장 고전적이고 대표적인 문제는 "오름차순으로 정렬된 배열에서 두 숫자를 더해 타겟 값(K)을 만드는 쌍을 찾으시오"입니다.
- 초기화:
left포인터는 배열의 맨 앞(가장 작은 값)에,right포인터는 배열의 맨 뒤(가장 큰 값)에 배치합니다. - 이동 조건 1: 두 포인터가 가리키는 값의 합이 타겟 K보다 작다면? 합을 더 키워야 하므로, 작은 값을 가리키는
left포인터를 오른쪽으로 한 칸 이동시킵니다. - 이동 조건 2: 두 포인터가 가리키는 값의 합이 타겟 K보다 크다면? 합을 깎아내려야 하므로, 큰 값을 가리키는
right포인터를 왼쪽으로 한 칸 당겨 이동시킵니다. - 종료 조건: 두 값이 정확히 K와 일치하면 정답을 반환하고,
left와right가 서로 엇갈려 교차하는 순간 탐색을 완전히 종료합니다.
이처럼 투 포인터는 두 화살표 사이의 간격(탐색 길이)이 탐색 과정 내내 자유자재로 고무줄처럼 늘어났다 줄어들며 변한다는 것이 핵심적인 특징입니다.
2. 슬라이딩 윈도우(Sliding Window): 창문을 밀며 전진하라
슬라이딩 윈도우 역시 두 개의 포인터를 사용하지만, 두 포인터 사이의 간격(Window 크기)이 처음부터 끝까지 딱딱하게 고정된 채로 움직인다는 결정적인 차이가 있습니다. 마치 투명한 창문을 긴 배열 위에 올려놓고, 오른쪽으로 한 칸씩 스르륵 밀면서(Sliding) 창문 너머로 보이는 데이터만 확인하고 연산하는 것과 같습니다.
2-1. 대표적인 활용 시나리오: 길이가 K인 연속 부분 배열의 최대 합
배열 안에서 "연속된 K일 동안의 매출액 합계 중 최댓값"을 구하는 상황을 상상해 보십시오.
- 초기화: 먼저 0번 인덱스부터 K-1번 인덱스까지의 합(첫 번째 창문의 합)을 정직하게 모두 더하여 구합니다.
- 이동의 마법: 창문을 오른쪽으로 한 칸 슬쩍 밀면, 윈도우에서 가장 왼쪽에 있던 과거의 데이터 하나가 시야에서 빠져나가고, 가장 오른쪽에 새로운 데이터 하나가 새롭게 들어오게 됩니다.
- 연산의 극대화 (O(1) 갱신): 매번 창문을 밀 때마다 창문 안의 K개 숫자를 다시 처음부터 끝까지 더할 필요가 전혀 없습니다! 기존 창문의 총합에서 '시야를 빠져나간 맨 앞의 숫자'를 빼고, '새롭게 시야에 들어온 맨 뒤의 숫자'만 더해주면 O(1)의 덧셈/뺄셈 연산 단 두 번만으로 새로운 창문의 합을 즉시 구해낼 수 있습니다. 이 과정이 슬라이딩 윈도우 최적화의 꽃입니다.
3. 어떤 문제에 무엇을 써야 할까? (결정적 차이와 선택 기준)
실전 코딩 테스트에서 두 기법을 헷갈리지 않고 정확히 짚어내어 선택하는 기준은 바로 '구간의 길이가 고정되어 있는가?'에 있습니다.
- 부분 배열의 길이가 고정되어 있다면(예: 무조건 연속된 3일간의 합, 크기가 5인 서브스트링) 망설이지 말고 슬라이딩 윈도우를 사용해야 합니다. 창문의 크기를 일정하게 유지한 채 O(1)로 값을 갱신하며 밀고 나가기만 하면 됩니다.
- 부분 배열의 길이가 정해져 있지 않고, 특정 조건(예: 합이 정확히 100이 되는 연속 구간, 조건을 만족하는 가장 짧은 구간)을 만족하는 구간을 직접 찾아내야 한다면 투 포인터를 사용해야 합니다. 조건을 맞추기 위해 앞 포인터를 당기거나 뒤 포인터를 밀면서 길이를 능동적으로 조절해야 하기 때문입니다.
1. 투 포인터와 슬라이딩 윈도우는 모두 1차원 배열을 단 1회 스캔하여 O(N)의 선형 시간 복잡도로 O(N^2)의 한계를 극복하는 강력한 탐색 기법입니다.
2. 투 포인터는 두 화살표가 독립적으로 움직여 탐색 구간의 길이가 유동적으로 변하며, 주로 정렬된 배열의 값 비교나 가변 길이 구간 탐색에 쓰입니다.
3. 슬라이딩 윈도우는 두 화살표 사이의 간격이 고정된 상태로 배열 위를 미끄러지듯 이동하며, 고정 길이 구간의 합이나 최댓값 계산에서 불필요한 중복 연산을 완벽하게 제거합니다.