TIL : Two-Pointer 알고리즘 (7)

💻 알고리즘

 ✔️ Two-Pointer 알고리즘이란?

리스트에 순차적으로 접근할 때 두 개의 점 위치를 기록하면서 처리하는 알고리즘!

간단히 말해서 포인터 두 개를 사용해서 데이터에 접근하겠다는 소리이다.

 

💡 특징

• 포인터 2개가 같은 방향으로 이동 → 특정 값과 일치하는 배열을 찾는 경우
• 포인터 2개가 양끝에서 출발해서 만남 → 특정 값과 일치하는 합을 찾는 경우
• 모든 범위를 확인하지 않고 O(n^2), 포인터가 각각 N번만 이동하기 때문에 O(N)

 ✔️ 포인터가 같은 방향으로 이동

def two_pointer(array, target):
    end, sum_ = 0, 0
    cnt = 0
    
    for start in range(len(array)):
        while sum_ < target and end < len(array):
            sum_ += array[end]
            end += 1
        if sum_ == target: cnt += 1
        sum_ -= array[start]

    return cnt

💡 동작 원리

1. 두 포인터가 0부터 시작한다.
2. 부분 합(sum_)이 target 값과 같다면 카운트 한다.
3. sum_ > target 이라면 start += 1
4. sum_ < target 이라면 end += 1
5. 모든 경우를 확인할 때까지 2, 3, 4번을 반복한다.

구간 합(prefix sum) 알고리즘과 유사하다.

 ✔️ 포인터가 양끝에서부터 만남

### array는 정렬되어있어야한다. ###
def two_pointer2(array, target):
    start, end = 0, len(array)-1
    cnt = 0
    
    while start < end:
        tmp = array[start] + array[end]
        if tmp == target: cnt += 1
        if tmp < target:
            start += 1
            continue
        end -= 1
        
    return cnt

💡 동작 원리

1. 양쪽 끝에 포인터를 지정한다.
2. 포인터의 합(tmp) > target 이라면 end를 1 감소.
3. tmp < target 이라면 start += 1
4. tmp == target 이라면 카운트 한다.
5. 두 포인터가 만날 때까지 2, 3, 4번 반복한다.