투 포인터(Two Pointers) 알고리즘

투 포인터는 배열이나 문자열처럼 선형 구조에서 2개의 인덱스(pointer)를 사용해 원하는 조건을 만족하는 해를 찾는 기법입니다. 주로 정렬된 배열에서 사용하며, 시간 복잡도 O(n)으로 문제를 풀 수 있는 장점이 있습니다.

첫째, 왼쪽 포인터 l(left)를 배열의 시작(또는 특정 기준점)으로, 오른쪽 포인터 r(right)를 배열의 끝으로 설정합니다.

둘째, l과 r이 교차하기 전까지 다음을 반복합니다.

• 두 포인터가 가리키는 원소들이 조건을 만족하는지 검사합니다.
• 조건에 따라 l을 오른쪽으로 한 칸 이동시키거나, r을 왼쪽으로 한 칸씩 이동시켜 탐색 범위를 좁혀 나갑니다.
• 조건을 만족하면 결과를 저장 혹은 반환하여 종료합니다.

이렇게 포인터를 양끝에서 한칸씩 좁혀 나가기 때문에 중첩 반복문 없이 한 번의 선형 탐색으로 해결할 수 있어서 시간 복잡도 O(n)으로 문제를 풀 수 있습니다.

문제

오름차순으로 정렬된 정수 배열 nums와 목표값 target이 주어질 때, 두 수의 합이 target인 모든 인덱스 쌍을 반환하시오.

풀이

쉽고 단순하게 생각하면 이중 for문을 사용하여 모든 경우의 수를 구하면 되지만, 시간복잡도가 O(n^2)이므로 비효율적입니다. 이때 투 포인터(Two Pointer)를 활용하면 좋습니다.

1. l과 r을 양 끝으로 초기화
2. 반복문을 수행하면 아래 과정을 수행
   • current = nums[l] + nums[r]
   • current와 target이 동일한지 비교
   • current < target 이면 l += 1 (합을 늘리기 위해)
   • current > target 이면 r -= 1 (합을 줄이기 위해)

def solution(nums, target):
    l, r = 0, len(nums) - 1
    result = []
 
    while l < r:
        current = nums[l] + nums[r]
        if current == target:
            result.append((l, r))
            l += 1
            r -= 1
        elif current < target:
            l += 1
        else:
            r -= 1
 
    return result
 
# 사용 예시
nums = [1, 2, 3, 4, 6, 7, 11]
target = 9
print(solution(nums, target))  # [(1, 5), (2, 4)]

nums[1] + nums[5] = 2 + 7, nums[2] + nums[4] = 3 + 6 이므로, 정답은 [(1, 5), (2, 4)] 입니다.

문제

풀이

def solution(people, limit):
    answer = 0
 
    l = 0
    r = len(people) - 1
    pp = sorted(people)  # 투 포인터를 사용하기 위해 우선 정렬
 
    while l <= r:
        # 함께 탈 수 있으면 둘 다 태우고,
        if pp[l] + pp[r] <= limit:
            l += 1
        r -= 1  # 아니면 무거운 사람만 태운다
        answer += 1
 
    return answer

• 정렬된 배열에서 합, 차, 약수 관계 등을 탐색할 때 사용
• 문자열에서 팰린드롬 검사나 점진적으로 양끝에서 조건을 확인할 때
• 슬라이딩 윈도우로 확장하여, 배열 내 특정 구간(sub array)의 합을 찾을 때

슬라이딩 윈도우에 대해 더 자세한 내용이 궁금하면 슬라이딩 윈도우(Sliding Window) 알고리즘를 참고해주세요.