[BinarySearch] 두 배열의 합

투포인터 알고리즘$O(N)$

 

1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가며 원하는 것을 얻는 형태

출처: m.blog.naver.com/kks227/220795165570

투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)

 

---

이진탐색도 2개의 포인트로 움직이는 것은 동일하지만 다른점은 이진탐색은 탐색의 범위가 줄어든다는 점이고

투포인터 알고리즘은 그렇지 않다. 또한, 이진탐색은 정렬이 필요하지만 투포인터는 그렇지 않다.

따라서 투포인터는 $O(N)$, 이진탐색은 $O(logN)$의 복잡도를 가진다.

---

투포인터로 푸는 방법

from collections import Counter

t=int(input())
n=int(input())
a=list(map(int, input().split()))
m=int(input())
b=list(map(int,input().split()))

def toPointer(lst,l):
    r=[]
    for i in range(l):
        temp=0
        for j in range(i,l):
            temp += lst[j]
            r.append(temp)
    return r

al = toPointer(a,n)
bl = toPointer(b,m)

result = 0
c = Counter(bl)
for i in al:
    result+=c[t-i]

print(result) 

blog.naver.com/PostView.nhn?blogId=hands731&logNo=221885544050

백준 2143번 : [파이썬] 두 배열의 합