[알고리즘] 투 포인터

투 포인터 알고리즘은 배열에서 두 개의 포인터를 사용하여 특정 목표를 달성하기 위한 기법입니다. 일반적으로 정렬된 배열에서 특정 조건을 충족하는 요소를 찾거나 연속된 서브 배열의 합과 같은 문제를 해결할 때 사용됩니다.

투 포인터 알고리즘의 전제와 조건

1. 배열은 정렬되어 있어야 함: 투 포인터 알고리즘이 작동하려면 배열이 정렬되어 있어야 합니다. 포인터가 이동하는 방식 때문에 정렬되지 않은 배열에서는 올바른 답을 찾지 못할 수 있습니다.
2. 두 개의 포인터를 사용함: 하나의 포인터는 배열의 시작점에, 다른 하나는 끝점에 위치시킵니다. 이 두 포인터는 문제에 따라 서로를 향해 움직이거나 같은 방향으로 움직일 수 있습니다.

투 포인터 알고리즘 설명

1. 포인터 초기화: 두 개의 포인터를 배열의 시작과 끝에 위치시킵니다.
2. 조건 검사: 특정 조건(예: 두 수의 합)을 만족하는지 검사합니다.
3. 포인터 이동: 조건을 만족하면 결과를 저장하고, 포인터를 적절히 이동시킵니다. 만족하지 않으면, 다른 포인터를 이동시킵니다.
4. 반복 실행: 모든 요소를 검사할 때까지 2와 3 단계를 반복합니다.
5. 결과 반환: 찾은 결과를 반환합니다.

예시: 정렬된 배열에서 두 수의 합이 특정 값 X인 요소 찾기

1. 배열을 정렬합니다.
2. 두 개의 포인터를 배열의 시작과 끝에 위치시킵니다.
3. 두 포인터가 가리키는 요소의 합이 X와 같은지 확인합니다.
   • 합이 X보다 크면 오른쪽 포인터를 왼쪽으로 이동시킵니다.
   • 합이 X보다 작으면 왼쪽 포인터를 오른쪽으로 이동시킵니다.
4. 두 포인터가 교차할 때까지 3 단계를 반복합니다.
5. 결과를 반환합니다.

투 포인터 알고리즘은 간단하고 효율적인 해법을 제공합니다. O(N)의 시간 복잡도로 문제를 해결할 수 있어, 많은 문제에서 유용하게 사용됩니다.

 

위 사진은 투 포인터 알고리즘의 예시이다.

https://www.acmicpc.net/problem/2470

2470번: 두 용액

https://www.acmicpc.net/problem/2467

2467번: 용액

# 정렬된 숫자들이 들어오는지 확인해줘야한다.
# 백준 2470번 두 용액 코드

n = int(input())
liquid = list(map(int, input().split()))
liquid.sort()
start = 0
end = n-1
closeToEnd = sys.maxsize 
ans = [0,0]
while start < end:
    total = liquid[start] + liquid[end]
    if abs(total) < closeToEnd:
        closeToEnd = abs(total)
        ans[0], ans[1] = liquid[start], liquid[end]
    # 포인터를 이동해준다.
    elif total > 0:
        end -=1
    # 다른 포인터를 이동해준다.
    else:
        start += 1

print(*ans)