정렬된 배열에서 투 포인터

두 포인터 기법은 중첩 반복문 대신 두 인덱스로 배열을 훑습니다. 그 결과 많은 O(n^2) 방식이 깔끔한 한 번의 O(n) 순회로 바뀝니다. 🎯

대표적인 방식에서는 정렬된 배열이 필요합니다. 순서가 있으면 오른쪽으로 이동할수록 값이 커지고 왼쪽으로 이동할수록 값이 작아진다고 판단할 수 있으므로, 매 단계가 분명한 선택이 됩니다.

한 포인터는 왼쪽 끝에, 다른 포인터는 오른쪽 끝에 둡니다. 두 포인터는 서로 마주 보며 천천히 간격을 좁혀 갑니다.

각 단계에서는 포인터 하나만 정확히 안쪽으로 이동합니다. 배열의 순서를 보고 목표에 가까워지려면 어느 쪽을 움직여야 하는지 결정합니다.

left < right인 동안 반복하십시오. 두 포인터가 만나거나 서로 지나치면 확인해야 할 모든 유효한 쌍을 확인한 것이므로 멈추면 됩니다.

a[left] + a[right]를 현재 후보값으로 보십시오. 이를 목표값과 비교하면 다음에 더 큰 값이 필요한지 더 작은 값이 필요한지 알 수 있습니다.

합이 목표값보다 작으면 더 큰 값이 필요합니다. 배열이 오름차순으로 정렬되어 있으므로 왼쪽 포인터를 큰 값이 있는 오른쪽으로 이동하십시오.

합이 목표값보다 크면 더 작은 값이 필요합니다. 합을 줄이도록 오른쪽 포인터를 더 작은 값이 있는 왼쪽으로 이동하십시오.

포인터를 한 번 이동할 때마다 다시 검사할 필요가 없는 쌍을 한꺼번에 제거합니다. 그래서 이 순회가 이차 시간이 아니라 선형 시간이 됩니다.

일치할 수 없는 쌍만 버리므로 올바른 답을 건너뛰지 않습니다. 이러한 안전성 덕분에 대회에서 두 포인터를 믿고 사용할 수 있습니다.

같은 아이디어는 배열을 제자리에서 뒤집거나, 분할하거나, 병합하는 변형 문제에도 활용됩니다. 포인터가 만나는 방식을 익히면 이 문제들도 익숙하게 느껴질 것입니다.

정렬된 배열을 양끝에서 훑으며 목표 합을 찾고 있습니다.

두 포인터는 정렬된 배열을 양끝에서 훑으며 sorted 배열에서 left < right인 동안 매 단계 하나를 안쪽으로 이동합니다. 선형 시간에 올바르게 동작하며, 다양한 기법의 기반이 됩니다. 🚀