투 포인터(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)
위 문제에서 투 포인터 기법을 사용하여 정렬된 배열에서 두 수의 합이 특정 값이 되는 두 수를 찾는 과정을 단계별로 그린 그림이에요.
각 단계에서 포인터의 위치와 현재 합계를 시각적으로 나타내어 이해를 돕습니다.
이렇게 투 포인터 기법을 사용하여 목표 값을 찾는 과정을 단계별로 시각적으로 나타내면 이해하기 쉽습니다. 각 단계에서 포인터의 위치와 합계를 보여주어, 포인터 이동의 이유와 결과를 명확히 알 수 있습니다.
다른 예제를 볼까요?
가장 긴 고유한 문자 부분 문자열 찾기
문자열에서 고유한 문자로만 이루어진 가장 긴 부분 문자열의 길이를 찾는 예제입니다.
문제) 주어진 문자열 `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]
투 포인터 기법은 배열이나 리스트를 효율적으로 탐색할 수 있습니다.
이 기법을 사용하면 문제를 효과적으로 해결할 수 있으며, 시간 복잡도를 줄이는 데 큰 도움이 됩니다.
다양한 문제에 적용해보고 숙달하면 알고리즘 설계에 활용해보세요!