안녕하세요, 여러분! 오늘은 “투 포인터” 알고리즘에 대해 자세히 알아보고, 이 알고리즘을 활용한 문제를 풀어보는 시간을 가지겠습니다. 투 포인터 기법은 배열이나 리스트와 같이 정해진 크기를 가진 데이터 구조에서 문제를 해결할 때 매우 유용한 방법입니다. 각각의 포인터는 데이터 구조의 위치를 식별하는 용도로 사용되며, 이를 통해 시간 복잡도를 줄일 수 있습니다.
1. 투 포인터 알고리즘이란?
투 포인터 알고리즘은 주어진 배열에서 두 지점을 동시에 사용할 때 효율적으로 문제를 해결하기 위한 대표적인 기법입니다. 주로 정렬된 배열에서 부분합, 최대/최소값 문제를 해결하거나, 특정 조건을 만족하는 데이터 쌍을 찾을 때 유용하게 사용됩니다.
투 포인터의 장점은 반복문 하나로 배열을 한 번만 순회하면서 필요한 결과를 얻을 수 있다는 점입니다. 이를 통하여 O(n)의 시간 복잡도로 문제를 해결할 수 있습니다.
2. 문제 설명
이번에 풀어볼 문제는 “정수 배열에서 이상적인 쌍 찾기”입니다. 주어진 정수 배열 arr와 정수 K가 있을 때, 느낌표(!) 없이 K의 합이 되는 두 수를 찾아라. 이 때의 두 수의 인덱스를 반환하는 함수를 작성하세요. 만약 such a pair가 없다면, -1을 반환합니다.
문제 예시
- 입력:
arr = [10, 15, 3, 7],K = 17 - 출력:
(0, 2)// 인덱스는 0 기준 - 입력:
arr = [10, 15, 3, 7],K = 20 - 출력:
-1
3. 접근 방법
이 문제를 해결하는 데 있어 수학적 접근을 사용할 수 있습니다. 두 수의 합이 K가 되어야 하므로, 첫 번째 포인터는 배열의 시작을 가리키고, 두 번째 포인터는 배열의 끝을 가리킵니다. 그리고 두 포인터가 가리키는 값의 합을 계산한 후, 이 합이 K와 비교됩니다.
1. 먼저 첫 번째 포인터를 배열의 가장 왼쪽, 두 번째 포인터를 배열의 가장 오른쪽에 위치시킵니다.
2. 두 포인터가 서로 교차할 때까지 반복합니다:
- 합계가
K와 같으면 두 포인터의 인덱스를 반환합니다. - 합계가
K보다 작으면, 첫 번째 포인터를 오른쪽으로 이동하여 합계를 증가시킵니다. - 합계가
K보다 크면, 두 번째 포인터를 왼쪽으로 이동하여 합계를 감소시킵니다.
3. 만약 두 포인터가 교차했지만 쌍을 찾지 못했다면, -1을 반환합니다.
4. 코드 구현
def two_sum(arr, K):
left = 0
right = len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == K:
return (left, right) # 쌍을 찾음
elif current_sum < K:
left += 1 # 더 큰 합을 위해 왼쪽 포인터 이동
else:
right -= 1 # 더 작은 합을 위해 오른쪽 포인터 이동
return -1 # 쌍을 찾지 못함
5. 코드 설명
위의 코드는 투자녀의 두 포인터 기법을 사용하여 두 수의 합으로 K가 되는 인덱스 쌍을 찾는 함수입니다. left와 right 두 변수를 사용하여 포인터를 배열의 양 끝에서부터 시작합니다.
먼저 while 루프에서 두 포인터가 방향성으로 개선되고 있는지 확인합니다. 현재의 두 값의 합을 계산한 후, 이 값이 K와 같다면 해당 인덱스를 반환합니다. 그렇지 않다면 합의 크기에 따라 포인터를 조정하고 반복합니다.
6. 시간 복잡도 분석
이 알고리즘의 시간복잡도는 O(n)입니다. 두 포인터가 배열의 양 끝에서 시작하므로, 배열을 전부 순회할 필요가 없이 조건을 만족하기 위해 단 한번의 반복으로 끝나게 됩니다. 공간복잡도는 O(1)로 상수 공간만 사용하는 매우 효율적인 방법입니다.
7. 추가 예제
테스트 케이스를 통해 코드의 올바름을 검증할 수 있습니다.
print(two_sum([10, 15, 3, 7], 17)) # 출력: (0, 2)
print(two_sum([10, 15, 3, 7], 20)) # 출력: -1
print(two_sum([1, 2, 3, 4, 6], 10)) # 출력: (3, 4)
8. 마무리
오늘은 투 포인터 기법을 사용하여 문제를 해결해보았습니다. 파이썬 알고리즘 문제를 풀 때, 이러한 기법을 활용하면 시간을 절약하고 효율적으로 문제를 해결할 수 있습니다. 다양한 문제에서 연습하여 더 많은 노하우를 쌓아보세요. 다음 시간에는 다이나믹 프로그래밍에 대해 다뤄보겠습니다. 오늘도 수고하셨습니다!