기본 알고리즘 테크닉: 투 포인터

투 포인터(Two Pointer)는 리스트나 배열에서 두 개의 포인터를 사용하여 특정 구간이나 합을 찾는 문제를 빠르게 해결하는 탐색 기법입니다. 투 포인터는 정렬된 배열에서 연속된 부분 구간이나 특정 값의 합을 구하는 문제에 매우 효과적입니다.

두 포인터는 특정 조건에 따라 이동하면서 원하는 값을 탐색합니다. 이 기법은 일반적인 반복문보다 효율적이며, 특정 조건을 만족하는 구간을 찾거나 배열의 끝까지 탐색해야 하는 문제에서 자주 사용됩니다. 특히, 투 포인터는 시간 복잡도를 개선해 줄 수 있는 효율적인 알고리즘으로, 여러 문제 유형에 적용 가능합니다.

투 포인터 기법은 두 개의 포인터를 사용하여 한 방향으로 이동하거나 양쪽에서 중앙으로 좁혀 나가며 탐색하는 방식으로 동작합니다. 이 두 포인터는 각자의 위치에서 조건에 따라 이동하며 특정 값이나 구간을 찾습니다.

주로 사용하는 투 포인터 방식은 다음과 같습니다:

• 정렬된 배열에서 특정 값 찾기: 배열이 오름차순으로 정렬되어 있을 때, 두 수의 합이 특정 값이 되는 경우를 찾는 문제에서 유용합니다.
• 연속 부분 구간: 특정 합을 가지는 연속된 구간을 찾아야 할 때 사용합니다.
• 양쪽에서 중앙으로 좁히는 방식: 양 끝에서 시작해 포인터를 점차 중앙으로 이동시키며 원하는 조건에 맞는 값을 찾습니다.

시간 복잡도

투 포인터 기법은 두 포인터가 리스트를 순회하기 때문에 일반적으로 $$O(N)$$의 시간 복잡도를 가집니다. 두 포인터가 각각 한 번만 배열을 순회하면 되므로, 특정 조건을 만족할 때 반복문을 모두 순회할 필요 없이 종료할 수 있습니다.

다음은 투 포인터를 사용하여 정렬된 배열에서 두 수의 합이 특정 값이 되는 경우를 찾는 예제입니다. 이 문제는 투 포인터를 사용하면 효율적으로 해결할 수 있습니다.

Python 코드 예제:
def two_sum(arr, target):
    # 리스트의 양 끝에서 시작하는 두 포인터를 설정합니다
    left, right = 0, len(arr) - 1

    # 두 포인터가 서로 교차하기 전까지 반복합니다
    while left < right:
        current_sum = arr[left] + arr[right]

        # 찾고자 하는 합이 발견된 경우, 해당 두 값의 인덱스를 반환합니다
        if current_sum == target:
            return left, right

        # 현재 합이 찾고자 하는 값보다 작으면 왼쪽 포인터를 오른쪽으로 이동합니다
        elif current_sum < target:
            left += 1

        # 현재 합이 찾고자 하는 값보다 크면 오른쪽 포인터를 왼쪽으로 이동합니다
        else:
            right -= 1

    return -1, -1  # 값이 없을 경우 -1, -1 반환

# 예제 사용
arr = [1, 2, 3, 5, 7, 11]
target = 10
print(two_sum(arr, target))  # 출력: (2, 4) (arr[2] + arr[4] = 10)
                

설명: two_sum 함수는 정렬된 리스트 arr에서 두 포인터(left와 right)를 사용해 target 값이 되는 두 요소를 찾습니다. 현재 합이 target보다 작으면 left 포인터를 오른쪽으로 이동하고, 크면 right 포인터를 왼쪽으로 이동하여 탐색 범위를 좁힙니다.

투 포인터 기법은 다양한 문제에서 활용할 수 있습니다. 대표적인 예제로는 특정 합을 구하는 문제 외에도 연속된 부분 배열 구간을 찾거나, 정렬된 배열에서 중복 요소 제거 등 다양한 문제가 있습니다.

예제 1: 연속된 부분 배열의 합 찾기

연속된 부분 배열이 특정 합을 갖는 경우를 찾는 문제는 투 포인터를 사용해 쉽게 해결할 수 있습니다. 리스트의 첫 부분과 끝 부분을 가리키는 포인터를 이동하면서 조건을 만족할 때까지 구간을 조정합니다.

Python 코드 예제:
def subarray_sum(arr, target):
    left, current_sum = 0, 0

    for right in range(len(arr)):
        # 구간의 합에 오른쪽 요소 추가
        current_sum += arr[right]

        # 합이 초과하는 경우, 왼쪽 포인터를 오른쪽으로 이동하여 합을 줄입니다
        while current_sum > target and left <= right:
            current_sum -= arr[left]
            left += 1

        # 조건을 만족하는 구간을 찾은 경우
        if current_sum == target:
            return left, right

    return -1, -1  # 값이 없을 경우 -1, -1 반환

# 예제 사용
arr = [1, 3, 2, 5, 7, 2]
target = 10
print(subarray_sum(arr, target))  # 출력: (1, 3) (arr[1:4]의 합 = 10)
                

설명: subarray_sum 함수는 연속된 부분 배열의 합이 target이 되는 구간을 찾습니다. 오른쪽 포인터로 구간을 확장하면서 합을 계산하고, 합이 target을 초과하면 왼쪽 포인터를 오른쪽으로 이동해 구간을 줄입니다.

예제 2: 정렬된 배열에서 중복 요소 제거

투 포인터 기법을 사용하면 정렬된 배열에서 중복 요소를 제거할 수 있습니다. 하나의 포인터는 고유한 값을 기록하고, 다른 포인터는 배열의 끝까지 이동하면서 중복 여부를 확인합니다.

Python 코드 예제:
def remove_duplicates(arr):
    if not arr:
        return 0

    unique_index = 0  # 고유한 값이 위치할 인덱스

    for i in range(1, len(arr)):
        if arr[i] != arr[unique_index]:
            unique_index += 1
            arr[unique_index] = arr[i]

    return arr[:unique_index + 1]

# 예제 사용
arr = [1, 2, 2, 3, 3, 4, 5]
print(remove_duplicates(arr))  # 출력: [1, 2, 3, 4, 5]
                

설명: remove_duplicates 함수는 정렬된 배열에서 중복 요소를 제거하고 고유한 값들만 남깁니다. unique_index 포인터는 고유한 값이 위치할 곳을 가리키며, 중복을 발견하지 않으면 배열의 다음 고유 위치에 값을 추가합니다.

투 포인터 기법은 시간 복잡도를 줄여주는 효율적인 탐색 방식이지만, 정렬된 배열에서만 제대로 동작한다는 한계가 있습니다. 또한 배열이 정렬되지 않은 상태에서 사용하려면 정렬 작업을 먼저 수행해야 하므로 추가적인 연산이 필요할 수 있습니다.

장점

• 데이터가 정렬된 상태에서는 $$O(N)$$의 시간 복잡도로 특정 구간이나 값을 탐색할 수 있습니다.
• 단일 반복 구조를 사용하여 코드가 간단하고 가독성이 높습니다.

한계

• 정렬되지 않은 데이터에서는 사용할 수 없으며, 정렬이 추가적으로 필요할 수 있습니다.
• 다차원 배열이나 복잡한 조건이 있는 경우 적용하기 어렵습니다.