30초 답변

Two Pointer는 배열이나 문자열에서 두 개의 인덱스를 조건에 따라 이동시켜 O(n²) 탐색을 O(n)으로 줄이는 기법입니다. 두 포인터를 양 끝에 두고 좁히는 방식과, 같은 방향으로 이동하는 sliding window 방식이 있습니다.

꼬리질문

조금 더 깊게 물어본다면

답변 뒤에 이어질 수 있는 질문들을 하나씩 열어볼 수 있어요.

1

2

3

4

Two Pointer와 Sliding Window의 차이는?

두 방법 모두 포인터 두 개를 씁니다. Two pointer는 보통 정렬된 배열에서 양 끝을 좁히고, sliding window는 같은 방향으로 이동하며 구간을 유동적으로 확장하고 축소합니다.

이전 질문다음 꼬리질문

부가 설명

배열에서 합이 특정 값인 두 수를 찾는다고 할 때, 모든 쌍을 확인하면 O(n²)입니다. 배열이 정렬되어 있다면 양 끝에 포인터를 놓고, 합이 크면 오른쪽 포인터를 줄이고 작으면 왼쪽 포인터를 늘리면 O(n)에 풀 수 있습니다. "합이 크면 오른쪽 값을 줄여야 한다"는 판단이 가능한 이유가 정렬입니다.

Sliding window는 같은 방향으로 이동하는 two pointer의 변형입니다. 창 안의 조건이 만족되면 오른쪽 포인터를 늘려 창을 키우고, 조건이 깨지면 왼쪽 포인터를 밀어 창을 줄입니다. 중복 없는 가장 긴 부분 문자열처럼 연속 구간을 탐색하는 문제가 대표적입니다.

한 줄 정리

Two Pointer는 단조성을 근거로 두 인덱스의 이동 방향을 고정해 O(n²)을 O(n)으로 줄이는 기법입니다.