투 포인터 (Two Pointers)

첨부파일

첨부된 파일이 없습니다.

투 포인터(Two Pointers) 기법은 두 개의 포인터를 사용하여 배열이나 리스트의 요소를 효율적으로 탐색하는 알고리즘 기법이에요.

주로 정렬된 배열에서 특정 조건을 만족하는 부분 배열을 찾거나 두 요소의 합을 구하는 문제에서 사용됩니다.

이 기법은 시간 복잡도를 줄여줄 수 있어서 효율적인 알고리즘 설계에 유용합니다.

투 포인터 기법의 기본 아이디어

1. 포인터 설정: 배열의 시작과 끝 또는 특정 조건을 기준으로 두 개의 포인터를 설정합니다.
2. 조건 검사: 두 포인터를 이동시키면서 조건을 검사합니다.
3. 포인터 이동: 조건에 따라 포인터를 적절히 이동시킵니다.

보통 왼쪽 포인터를 오른쪽으로 이동시키거나, 오른쪽 포인터를 왼쪽으로 이동시킵니다.

예시로 한번 알아볼까요?

정렬된 배열에서 두 수의 합이 특정 값이 되는 쌍 찾기

정렬된 배열에서 두 수의 합이 특정 값이 되는 두 수의 인덱스를 찾는 예제입니다.

문제) 정렬된 배열 `nums`와 정수 `target`이 주어졌을 때, 두 수의 합이 `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
# 예시 사용
nums = [2, 3, 4, 6, 8, 11, 15]
target = 10
result = two_sum(nums, target)
print(result)  # 출력: (0, 4)

위 문제에서 투 포인터 기법을 사용하여 정렬된 배열에서 두 수의 합이 특정 값이 되는 두 수를 찾는 과정을 단계별로 그린 그림이에요.

각 단계에서 포인터의 위치와 현재 합계를 시각적으로 나타내어 이해를 돕습니다.

설명

초기 상태:
- Left Pointer는 배열의 첫 번째 요소 2를 가리키고,
- Right Pointer는 배열의 마지막 요소 15를 가리킵니다.
- 합계는 2 + 15 = 17로, 목표 값 10보다 큽니다. 따라서, Right Pointer를 한 칸 왼쪽으로 이동합니다.
두 번째 단계:
- Left Pointer는 여전히 2를 가리키고,
- Right Pointer는 11을 가리킵니다.
- 합계는 2 + 11 = 13로, 목표 값 10보다 큽니다. 따라서, 다시 Right Pointer를 왼쪽으로 이동합니다.
세 번째 단계:
- Left Pointer는 여전히 2를 가리키고,
- Right Pointer는 8을 가리킵니다.
- 합계는 2 + 8 = 10로, 목표 값 10과 일치합니다.

이렇게 투 포인터 기법을 사용하여 목표 값을 찾는 과정을 단계별로 시각적으로 나타내면 이해하기 쉽습니다. 각 단계에서 포인터의 위치와 합계를 보여주어, 포인터 이동의 이유와 결과를 명확히 알 수 있습니다.

다른 예제를 볼까요?

가장 긴 고유한 문자 부분 문자열 찾기

문자열에서 고유한 문자로만 이루어진 가장 긴 부분 문자열의 길이를 찾는 예제입니다.

문제) 주어진 문자열 `s`에서 고유한 문자로 이루어진 가장 긴 부분 문자열의 길이를 구하세요.

def length_of_longest_substring(s):
   char_set = set()
   left = 0
   max_length = 0

   for right in range(len(s)):
       while s[right] in char_set:
           char_set.remove(s[left])
           left += 1
       char_set.add(s[right])
       max_length = max(max_length, right - left + 1)

   return max_length

# 예시 사용
s = "abcabcbb"
result = length_of_longest_substring(s)

print(result)  # 출력: 3 ("abc" 부분 문자열)

두 배열에서 공통 원소 찾기

두 개의 정렬된 배열에서 공통 원소를 찾는 예제입니다.

문제) 두 개의 정렬된 배열 `arr1`과 `arr2`가 주어졌을 때, 공통 원소를 모두 반환하세요.

def find_common_elements(arr1, arr2):
   i, j = 0, 0
   common_elements = []
   while i < len(arr1) && j < len(arr2):
       if arr1[i] < arr2[j]:
           i += 1
       elif arr1[i] > arr2[j]:
           j += 1
       else:
           common_elements.append(arr1[i])
           i += 1
           j += 1
   return common_elements
# 예시 사용
arr1 = [1, 3, 4, 5, 7]
arr2 = [2, 3, 5, 6]
result = find_common_elements(arr1, arr2)
print(result)  # 출력: [3, 5]

투 포인터 기법은 배열이나 리스트를 효율적으로 탐색할 수 있습니다.

이 기법을 사용하면 문제를 효과적으로 해결할 수 있으며, 시간 복잡도를 줄이는 데 큰 도움이 됩니다.

다양한 문제에 적용해보고 숙달하면 알고리즘 설계에 활용해보세요!