5주차

Two Pointers / Sliding Window

요약

🖱️ Two Pointers (투 포인터)

1차원 배열이나 리스트를 다룰 때 두 개의 포인터(인덱스)를 조작하며 원하는 조건을 만족하는 결과를 찾는 알고리즘이다.

특징

• 두 개의 포인터(인덱스)를 조작하여 원하는 조건을 만족하는 결과를 탐색한다.
• 완전 탐색(이중 for문)으로 O(N^2)의 시간이 걸리는 작업을 O(N)으로 단축시킬 수 있다는 것이 가장 큰 핵심이다.
• 정렬된 배열에서의 탐색, 연속된 부분 배열(수열)의 처리와 깊게 연결되어 있다.

개념

🖱️ Two Pointers (투 포인터)

이름 그대로 두 개의 포인터(시작점과 끝점, 혹은 두 개의 이동점)를 사용하여 배열을 탐색하는 방식이다.

특징

• 보통 1차원 배열에서 두 개의 포인터를 조작한다.
• 반복문 내에서 두 포인터가 각자의 조건에 따라 이동 방향과 속도를 결정한다.
• 한 번 이동한 포인터는 뒤로 돌아가지 않으므로(역방향 이동 불가), 전체 배열을 한 번만 순회하게 되어 시간 복잡도 O(N)을 보장한다.
• 슬라이딩 윈도우와 자주 비교되며, 문제에 따라 혼용되어 쓰이기도 한다.

동작 방식의 종류

1. 양방향 포인터

• 하나의 포인터는 배열의 처음(Left), 다른 하나는 배열의 끝(Right)에서 시작한다.
• 주로 정렬된 배열에서 두 수의 합이나 차를 구할 때 사용된다.
• 조건에 따라 Left를 증가시키거나, Right를 감소시키며 서로 만날 때까지 가운데로 좁혀온다.

2. 동방향 포인터

• 두 포인터 모두 배열의 처음(Start, End)에서 같은 방향으로 출발한다.
• 주로 연속된 부분 수열의 합이나 길이를 구할 때 사용된다.
• 조건에 따라 End를 전진시켜 구간을 넓히거나, Start를 전진시켜 구간을 좁히며 탐색한다.

Two Pointers vs 완전 탐색 비교

어떤 상황에서 투 포인터를 떠올려야 할까?

1. 배열 안에서 두 요소의 합 또는 차를 구해야 하는데 입력 크기(N)가 100,000 이상이라서 O(N) 또는 O(N log N)으로 풀어야 한다면? ➡ 투 포인터 (양방향)
2. 연속된 부분 배열이나 수열의 합이 특정 값이 되는 구간을 찾아야 한다면? ➡ 투 포인터 (동방향)

참고: 양방향 투 포인터를 사용할 때, 배열이 정렬되어 있지 않다면 먼저 정렬O(N log N)을 수행해야 한다. 정렬 시간을 포함하더라도 O(N^2)보다 훨씬 빠르다.

문제 패턴

투 포인터 문제는 대부분 포인터의 이동 조건을 묻는 경우가 많으며, 다음과 같은 패턴이 등장하면 투 포인터 문제일 가능성이 높다.

📚 패턴 1: 양끝에서 좁혀오기 (정렬된 배열)

1. 문제에서 자주 나오는 형태

1. 정렬된 배열에서 두 수의 합이 Target이 되는 쌍 찾기
2. 세 수의 합이 0이 되는 조합 찾기
3. 가장 두 물의 양이 많은 용기 찾기 (수조 문제)

2. 접근 방법

1. 배열을 오름차순으로 정렬한다.
2. Left = 0, Right = 배열의 길이 - 1로 초기화한다.
3. 두 값의 합이 Target보다 크면 Right를 왼쪽으로 이동(값을 줄임).
4. 두 값의 합이 Target보다 작으면 Left를 오른쪽으로 이동(값을 키움).

📚 패턴 2: 같은 방향에서 전진하기 (연속 부분 수열)

1. 문제에서 자주 나오는 형태

1. 연속된 부분 수열의 합이 Target이 되는 경우의 수 찾기
2. 합이 Target 이상이 되는 가장 짧은 연속 구간 길이 구하기

2. 접근 방법

1. Start = 0, End = 0으로 초기화한다.
2. 현재 구간의 합이 Target보다 작거나 같으면 End를 오른쪽으로 이동하여 합을 증가시킨다.
3. 현재 구간의 합이 Target보다 크거나 같으면 (또는 조건 만족 시) Start를 오른쪽으로 이동하여 구간을 좁히고 합을 감소시킨다.

예시 문제 기반 설명

Java

Python

JavaScript

실수 포인트>