투포인터 알고리즘

이전에 포스트했던 슬라이딩 윈도우랑 비슷하지만 조금 다르다.

슬라이딩 윈도우는 배열의 크기가 같지만,
투포인터 알고리즘은 target에 해당할 때 start와 end를 바꾸어 주기 때문에 다르다.
=> 배열의 크기가 같지 않다.

기본적인 원리는...

어떤 숫자들의 리스트가 주어질 때, 해당 리스트의 연속 수열의 합이 특정 값을 가지는 것을 확인하는 문제.

1. 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 한다.
2. 현재 부분 합이 M과 같다면 카운트한다.
3. 현재 부분 합이 M보다 작다면 end를 1 증가시킨다.
4. 현재 부분 합이 M보다 크거나 같다면 start를 1 증가시킨다.
5. 모든 경우를 확인할 때까지 2-4번 과정을 반복한다.

백준 2003번. 수들의 합 2

n,target=map(int,input().split())
arr=list(map(int,input().split()))

cnt,sum=0,0
high,low=0,0
while(1):
    if sum>target:        # 합이 타겟보다 크면.. (범위를 줄여야 하니까)
        sum-=arr[low]       # sum에서 뺴고
        low+=1              # low 의 index를 1증가
    elif high==n: break
    else:
        sum+=arr[high]      # 합이 타겟보다 작거나 같다면
        high+=1             # sum에 더하고 high의 인덱스를 1증가
    if sum==target:
        cnt+=1
print(cnt)

시간복잡도

매 루프마다 항상 두 포인터 중 하나는 1씩 증가하고 각 포인터가 n번 누적 증가해야 알고리즘이 끝납니다. -> 각각 배열 끝에 다다르니 O(N)

탐색을 위한 기본적인 알고리즘이기 때문에 알아두자!