[WEEK02] Two-pointer 알고리즘

Two-pointer 알고리즘

 

Two-pointer 알고리즘은 배열이나 리스트와 같은 선형 자료구조에서 두 개의 포인터를 사용하여 문제를 효율적으로 해결하는 기법이다. 일반적으로 정렬된 배열에서 특정 조건을 만족하는 요소를 찾거나, 구간을 조작하는 문제에서 자주 사용된다.

Two-pointer 알고리즘의 유형

(1) 투 포인터 탐색(Two-pointer Search)

• 두 개의 포인터를 배열의 양 끝에 두고 이동하며 조건을 만족하는 요소를 찾는 방식
• 예시: 정렬된 배열에서 두 수의 합이 특정 값이 되는 쌍 찾기 (Two Sum 문제)

(2) 슬라이딩 윈도우(Sliding Window)

• 두 개의 포인터가 일정한 간격을 유지하면서 이동하며 최적의 부분 배열을 찾는 방식
• 예시: 연속된 부분 배열에서 특정 조건을 만족하는 최대/최소 길이 찾기

Two-pointer 알고리즘의 활용 예제

(1) 두 수의 합 (Two Sum, 정렬된 배열)

# 정렬된 배열에서 두 수의 합이 target이 되는 인덱스 찾기

def two_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return left, right  # 두 인덱스 반환
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return None  # 조건을 만족하는 쌍이 없는 경우

(2) 가장 긴 부분 배열 (Sliding Window)

# 주어진 배열에서 합이 target 이하인 가장 긴 부분 배열 찾기

def longest_subarray(nums, target):
    left, current_sum, max_length = 0, 0, 0
    for right in range(len(nums)):
        current_sum += nums[right]
        while current_sum > target:
            current_sum -= nums[left]
            left += 1
        max_length = max(max_length, right - left + 1)
    return max_length

Two-pointer 알고리즘의 장점

• 시간 복잡도 감소: 일반적으로 O(N^2) 복잡도를 갖는 문제를 O(N)으로 최적화할 수 있음
• 메모리 효율성: 추가적인 공간을 사용하지 않고 주어진 배열을 직접 탐색
• 간결한 코드: 반복문과 조건문만으로 간단하게 구현 가능

정리

Two-pointer 알고리즘은 정렬된 배열을 활용하거나 특정 범위를 탐색하는 문제에서 매우 유용하다. 특히 투 포인터 탐색과 슬라이딩 윈도우 기법을 활용하면 다양한 문제를 효과적으로 해결할 수 있다. 실제 코테에서도 자주 등장하는 개념이므로 익숙해질 필요가 있겠다.