📘투포인터

투포인터 알고리즘은 배열이나 리스트와 같은 자료구조에서 두 개의 포인터를 사용하여 특정한 조건을 만족하는 구간이나 요소들을 효율적으로 탐색하는 방법이다. 이 알고리즘은 주로 정렬된 배열에서 많이 사용되며, 특정한 합을 찾거나, 구간의 길이를 조절하면서 문제를 해결할 때 유용하다.

✅투포인터 동작 순서

투포인터 알고리즘의 핵심은 두 개의 포인터를 사용하여 배열을 탐색하는 것이다. 이 투포인터는 일반적으로 시작과 끝 또는 두 위치를 가리키며, 각각의 포인터를 조작하여 문제를 해결한다.

1. 초기화

두 포인터를 초기화한다. 하나는 배열의 시작 또는 특정 위치에, 다른 하나는 배열의 끝 또는 특정 위치에 놓는다.

2. 조건 검사

두 포인터가 가리키는 요소를 기반으로 특정 조건을 검사한다.

3. 포인터 이동

조건을 만족하거나 불만족할 때 포인터를 이동하여 조건을 만족하도록 시도한다.

4. 반복

포인터가 배열의 경계를 벗어나거나 조건을 만족할 때까지 2와 3을 반복한다.

📖투포인터 예제

1. 두 수의 합 찾기

문제

정렬된 배열 lst와 목표 값 target이 주어졌을 때, 두 수의 합이 target이 되는 배열의 두 요소가 존재하는지 찾으시오.

풀이

1. 포인터 left를 배열의 첫 번째 요소에, 포인터 right를 배열의 마지막 요소에 놓는다.
2. 두 포인터가 가리키는 요소의 합을 계산한다.
3. 합이 target과 같다면 해당 요소를 반환한다.
4. 합이 target보다 작다면 left 포인터를 오른쪽으로 이동한다.
5. 합이 target보다 크면 right 포인터를 왼쪽으로 이동한다.
6. 두 포인터가 만나거나 교차할 때까지 2~5 단계를 반복한다.

코드

lst = [1, 2, 3, 4, 5]
target = 7
left = 0
right = len(lst) - 1

while left < right:
    current_sum = lst[left] + lst[right]

    if current_sum == target:
        break
    elif current_sum < target:
        left += 1
    elif current_sum > target:
        right += 1

print(lst[left], lst[right])

2. 부분 배열의 합이 특정 값을 가지는지 찾기

문제

배열 lst와 목표 값 target이 주어졌을 때, 부분 배열의 합이 target이 되는 경우가 있는지 찾으시오.

풀이

1. 두 포인터 start와 end를 배열의 첫 번째 요소에 놓는다.
2. 현재 부분 배열의 합을 current_sum으로 저장한다.
3. current_sum이 target보다 작으면 end 포인터를 오른쪽으로 이동하고, current_sum에 새로운 요소를 더한다.
4. current_sum이 target보다 크다면 start 포인터를 오른쪽으로 이동하고, current_sum에서 해당 요소를 뺀다.
5. current_sum이 target과 같다면 해당 부분 배열을 반환한다.
6. end 포인터가 배열의 끝에 도달할 때까지 3~5 단계를 반복한다.

lst = [1, 2, 3, 4, 5]
target = 9
start = 0
end = 0
current_sum = 0

while end < len(lst):
    if current_sum < target:
        current_sum += lst[end]
        end += 1
    elif current_sum > target:
        current_sum -= lst[start]
        start += 1
    elif current_sum == target:
        break

print(lst[start:end])

💡투포인터 장점

효율성

두 포인터를 사용하여 한 번의 순회로 문제를 해결할 수 있어 시간 복잡도를 줄일 수 있다. 참고로 투 포인터 시간 복잡도는 O(n)이다.

단순성

코드가 비교적 간단하고 직관적이다.