[알고리즘 코어 파헤치기] 투 포인터 & 슬라이딩 윈도우 - O(N^2)을 O(N)으로 압축하는 손가락 마법

학습 철학 회고
10만 개의 데이터가 주어졌을 때, 부분 연속 수열의 합을 구하려고 이중 for문($O(N^2)$)을 돌리면 100억 번의 연산이 발생하여 무조건 시간 초과가 납니다. 이때, 두 개의 포인터(손가락)를 사용하여 배열을 단 한 번만 스캔($O(N)$)하고 지나가는 우아한 최적화 기법의 뼈대를 세웁니다.

📌 개념 요약: 투 포인터란 무엇인가?

1차원 배열에서 두 개의 포인터(인덱스를 가리키는 변수)를 조작하여 원하는 결과를 얻는 알고리즘입니다. 동작 방식에 따라 크게 두 가지 철학으로 나뉩니다.

1. 같은 방향으로 이동 (애벌레 꿈틀대기): start와 end 포인터가 모두 인덱스 0에서 출발하여 오른쪽으로 이동합니다. 주로 '연속된 부분 배열의 합'을 구할 때 사용합니다.
2. 양끝에서 출발하여 교차 (가운데로 모이기): left는 0에서, right는 끝에서 출발하여 서로를 향해 다가옵니다. 주로 '정렬된 배열'에서 두 수의 합을 찾을 때 사용합니다.

📌 개념 요약: 슬라이딩 윈도우 (투 포인터의 특수 형태)

투 포인터처럼 두 개의 포인터를 쓰지만, 두 포인터 사이의 간격(창문 크기)이 항상 고정되어 있다는 점이 다릅니다. 마치 고정된 크기의 창문을 배열 위로 스르륵 밀고(Slide) 지나가는 것과 같습니다.

💡 동작 원리: 상태의 갱신과 포인터의 이동 (같은 방향 기준)

애벌레가 앞으로 나아가는 모습을 상상하면 쉽습니다.

• 머리(end) 전진: 현재 합이 목표값보다 작다면, end 포인터를 한 칸 앞으로 밀고 새로운 값을 합에 더합니다. (길이가 늘어남)
• 꼬리(start) 전진: 현재 합이 목표값보다 크거나 같다면, 현재 start 포인터가 가리키는 값을 합에서 빼고 start를 한 칸 앞으로 밉니다. (길이가 줄어듦)

💻 추상화된 템플릿 코드

가장 헷갈리기 쉬운 "같은 방향으로 이동하는 투 포인터 (연속 부분 배열의 합)"의 순수 뼈대입니다. 이 템플릿의 핵심은 IndexError를 완벽하게 통제하는 while문의 조건 설계에 있습니다.

def two_pointers_template(arr, target_sum):
    """
    :param arr: 1차원 배열 (자연수로만 이루어져 있어야 성립함)
    :param target_sum: 우리가 찾고자 하는 연속 부분 배열의 합
    """
    n = len(arr)
    count = 0        # 조건을 만족하는 경우의 수
    current_sum = 0  # 현재 포인터 구간의 합
    end = 0          # 꼬리(start)와 머리(end) 모두 0에서 시작
    
    # 1. 꼬리(start)를 0부터 끝까지 차례대로 이동시키며 탐색
    for start in range(n):
        
        # 2. [핵심 로직] 합이 타겟보다 작고, 머리(end)가 배열 범위를 벗어나지 않을 때까지 머리 전진
        while current_sum < target_sum and end < n:
            current_sum += arr[end]
            end += 1
            
        # 3. while문이 끝났다는 것은 합이 타겟 이상이 되었거나, end가 끝에 도달했다는 뜻
        if current_sum == target_sum:
            count += 1
            # 정답을 찾은 상태에서 다른 로직(예: 최소 길이 갱신 등)을 추가할 수 있음
            
        # 4. 다음 start로 넘어가기 전, 현재 start가 가리키는 값을 합에서 빼줌 (꼬리 당기기)
        current_sum -= arr[start]
        
    return count

🚨 설계 및 회고

• 자연수 전제 조건: 이 애벌레 방식은 배열에 '음수'가 섞여 있으면 사용할 수 없습니다. end를 전진시키면 무조건 합이 커지고, start를 전진시키면 무조건 합이 작아진다는 단조성(Monotonicity)이 보장되어야만 투 포인터의 논리가 성립하기 때문입니다.
• for문과 while문의 결합: 바깥쪽 for문이 start를, 안쪽 while문이 end를 조작합니다. 언뜻 보면 이중 루프라 $O(N^2)$ 같지만, end 변수는 루프가 돌아도 절대 뒤로 후진하지 않고 앞을 향해 $N$번만 이동합니다. 따라서 두 포인터가 각각 최대 $N$번씩만 움직이므로 전체 시간 복잡도는 $O(N)$이 되는 마법 같은 효율을 자랑합니다.

🚨 [핵심 회고] 우리는 왜 current_sum = 0으로 시작해야 하는가?

투 포인터를 구현하면서 가장 납득하기 어려웠던 부분은 초기화 로직이었습니다.
"어차피 첫 번째 원소를 참조할 거라면, 처음부터 current_sum = A[0]으로 꽉 채워서 시작하면 while문의 첫 번째 0 + A[0] 덧셈 연산을 아낄 수 있는 것 아닌가? 왜 쓸데없이 0으로 시작해서 루프를 낭비하게 만들까?"

이 1회의 연산을 아끼기 위한 '수동 언롤링(Manual Loop Unrolling)' 최적화 시도가 왜 오히려 독이 되는지, 컴퓨터의 시각에서 3가지 근거를 찾아냈습니다.

💡 나의 깨달음: 0으로 초기화하는 것은 낭비가 아니라 '영점 조절'이다.

1. 배열 참조 횟수는 사실 똑같다.
밖에서 A[0]을 미리 꺼내든, 안에서 A[0]을 더하든 결국 메모리 접근 횟수는 정확히 1번으로 동일하다. 절대적인 시간 이득이 생각보다 미미하다.

2. 덧셈 1번 아끼려다 '분기문(Branch)' 폭탄을 맞는다.
만약 밖에서 A[0]을 무작정 참조하려면, 배열이 비어있을 때(N = 0) 발생하는 IndexError를 막기 위해 함수 최상단에 if N == 0: return 0이라는 방어 로직을 반드시 넣어야 한다. 현대 CPU 아키텍처에서 단순 덧셈 비용은 거의 0에 수렴하지만, 이 조건 분기문(Branch)은 파이프라인을 깰 수 있어 비용이 훨씬 비싸다. 배보다 배꼽이 더 커진다.

3. 가장 버그가 적은 수학적 구간 설계: [start, end) (start 포함, end 미포함)
투 포인터에서 창문(Window)의 범위를 [start, end)로 설계하는 것이 실전에서 헷갈리지 않고 버그를 최소화하는 핵심 비결이다.
처음 start = 0, end = 0, current_sum = 0으로 시작하면 구간의 길이는 end - start = 0, 즉 아무 원소도 포함하지 않은 텅 빈 창문 상태가 되어 수학적으로 완벽히 들어맞는다. 이때 end 포인터는 "다음에 더해야 할 새로운 원소의 인덱스"라는 아주 명확한 역할을 갖게 된다.
반면 시작부터 A[0]을 미리 더해버리면, end가 '이미 더해진 값'을 가리키게 되어 변수의 역할이 오염된다. 이를 막기 위해 end = 1부터 시작하게 억지로 끼워 맞추다 보면 온갖 엣지 케이스에서 누더기 코드가 탄생한다.

결론적으로 current_sum = 0, start = 0, end = 0으로 시작하는 것은 불필요한 연산 낭비가 아니었다. 어떤 형태의 배열(빈 배열, 길이 1짜리 배열)이 들어와도 에러 없이 수학적 구간 [start, end)를 완벽하게 유지하기 위해 기꺼이 지불하는 가장 값싸고 확실한 보험료였다.