알고리즘

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

위시리 2025. 2. 14. 13:30

투포인터(Two Pointers) 알고리즘은 배열이나 리스트에서 두 개의 포인터를 사용하여 효율적으로 문제를 해결하는 알고리즘 기법이다.
주로 정렬된 배열에서 사용되며, O(n) 또는 O(n log n) 시간복잡도를 가진다.

 

투 포인터 개념
  • 두 개의 포인터를 사용하여 배열을 탐색한다.
  • 일반적으로 좌(L), 우(R)포인터를 조작하여 값을 찾거나 특정 조건을 만족하는 구간을 찾는다.
  • 정렬된 배열에서 유용하게 사용되며, O(n^2)의 시간복잡도를 O(n)으로 줄일 수 있다.

 

투 포인터가 사용되는 대표적인 유형

 

  1. 두 수의 합 찾기 (Two Sum)
  2. 구간 합(Subarray Sum)
  3. 두 배열에서 공통 원소 찾기
  4. 팰린드롬(Palindrome) 검사
  5. 정렬된 배열에서 특정 조건을 만족하는 구간 찾기 (슬라이딩 윈도우와 유사)

 

1. 두 수의 합 찾기 (Two Sum - 정렬된 배열)

정렬된 배열에서 두 숫자의 합이 target이 되는 쌍을 찾는 문제

📌 예제 문제

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 []  # 합이 target이 되는 경우가 없을 때

# 예제 실행
arr = [1, 2, 3, 4, 6, 8, 9]
target = 10
print(two_sum(arr, target))  # [1, 4]  (2 + 8 = 10)

📌 문제 설명

  • 정렬된 배열 arr에서 두 숫자의 합이 target이 되는 인덱스 쌍을 찾기
  • 투 포인터를 활용하여 O(N) 시간 복잡도로 해결

💡 동작 원리

  • left와 right 두 개의 포인터를 사용
    • left는 배열의 첫 번째 원소(가장 작은 값) 를 가리킴
    • right는 배열의 마지막 원소(가장 큰 값) 를 가리킴
  • 두 값을 더한 결과가 target과 비교됨
    • 작으면 left를 오른쪽으로 이동 (더 큰 수를 포함하기 위해)
    • 크면 right를 왼쪽으로 이동 (더 작은 수를 포함하기 위해)
    • 같으면 정답 반환

📝 시간 복잡도: O(N) : 배열을 한 번만 탐색
📝 왜 빠를까?

  • O(N^2)의 브루트포스 방법 대신 한 번의 순회로 해결 가능

 

2. 구간 합(Subarray Sum)

연속된 부분 배열의 합이 target이 되는 경우를 찾는 문제

📌 예제 문제

def subarray_sum(arr, target):
    left, right = 0, 0
    current_sum = 0

    while right < len(arr):
        current_sum += arr[right]  # 오른쪽 확장
        
        while current_sum > target:  # 합이 크면 왼쪽을 이동
            current_sum -= arr[left]
            left += 1
        
        if current_sum == target:
            return [left, right]  # 구간 반환

        right += 1
    
    return []  # 못 찾으면 빈 리스트 반환

# 예제 실행
arr = [1, 2, 3, 7, 5]
target = 12
print(subarray_sum(arr, target))  # [2, 3] (3 + 7 + 2 = 12)

📌 문제 설명

  • 배열에서 연속된 부분 배열의 합이 target과 같은 구간 찾기
  • 예제에서는 12가 되는 구간을 찾음

💡 동작 원리

  • left와 right 포인터 사용 (슬라이딩 윈도우 기법)
  • right를 확장하면서 현재 합(current_sum)을 업데이트
  • current_sum이 target을 초과하면 left를 이동하여 크기를 줄임

📝 시간 복잡도: O(N)
📝 핵심:

  • 구간의 합을 유지하면서 left와 right를 조절한다.
  • 필요할 때만 left를 이동하여 불필요한 계산을 줄인다.

 

3. 두 배열에서 공통 원소 찾기

정렬된 두 배열에서 공통 원소를 찾아라.

📌 예제 문제

def common_elements(arr1, arr2):
    p1, p2 = 0, 0
    result = []

    while p1 < len(arr1) and p2 < len(arr2):
        if arr1[p1] == arr2[p2]:
            result.append(arr1[p1])  # 공통 원소 저장
            p1 += 1
            p2 += 1
        elif arr1[p1] < arr2[p2]:
            p1 += 1  # 작은 쪽을 증가
        else:
            p2 += 1

    return result

# 예제 실행
arr1 = [1, 2, 4, 6, 8]
arr2 = [2, 4, 6, 10]
print(common_elements(arr1, arr2))  # [2, 4, 6]

📌 문제 설명

  • 정렬된 두 배열 arr1, arr2에서 공통 원소를 찾기

💡 동작 원리

  • 두 개의 포인터(p1, p2) 사용
  • arr1[p1] == arr2[p2] → 공통 원소이므로 추가
  • arr1[p1] < arr2[p2] → 작은 값을 증가시켜 다음 값과 비교

📝 시간 복잡도: O(N + M)
📝 핵심:

  • 두 배열이 정렬되어 있기 때문에 O(N^2) 대신 O(N + M)으로 해결 가능!

 

4. 팰린드롬(Palindrome) 검사

문자열이 앞뒤로 동일한지 검사하는 문제

📌 예제 문제

def is_palindrome(s):
    left, right = 0, len(s) - 1

    while left < right:
        if s[left] != s[right]:
            return False  # 한 글자라도 다르면 팰린드롬 아님
        left += 1
        right -= 1

    return True  # 끝까지 검사 성공 시 팰린드롬

# 예제 실행
print(is_palindrome("racecar"))  # True
print(is_palindrome("hello"))  # False

📝 시간 복잡도: O(N)

 

5. 특정 조건을 만족하는 부분 구간 찾기

예를 들어, "배열에서 합이 K 이하인 가장 긴 연속 부분 배열을 찾아라" 같은 문제

📌 예제 문제

def longest_subarray(arr, K):
    left, right = 0, 0
    current_sum = 0
    max_length = 0

    while right < len(arr):
        current_sum += arr[right]

        while current_sum > K:  # 합이 K를 초과하면 왼쪽 이동
            current_sum -= arr[left]
            left += 1

        max_length = max(max_length, right - left + 1)
        right += 1

    return max_length

# 예제 실행
arr = [1, 2, 3, 4, 5, 6, 7]
K = 10
print(longest_subarray(arr, K))  # 4  (1+2+3+4 = 10)

📝 시간 복잡도: O(N)

 

 

투 포인터의 핵심
  • 정렬된 배열에서 활용
  • 불필요한 반복문을 줄이고 O(N^2) → O(N)으로 최적화
  • left, right를 이동하며 조건을 만족하는 구간 찾기

 

저작자표시