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)보다 훨씬 빠르다.

문제 패턴

예시 문제 기반 설명

Java

Python

JavaScript

실수 포인트>