[Swift Algorithm] 투 포인터 알고리즘

투 포인트 알고리즘은

구간의 합같이 구간을 비교할 때 효율적으로 사용할 수 있는 알고리즘이에요

보통 for문 중첩을 통해서 O(N^2)시간초과로 인해서 사용하구요

 

이 알고리즘의 시간복잡도는 O(N)으로 한번의 순회에 조건을 찾을 수 있어요

 

 

구간을 비교하면서

원하는 조건에 달성할때까지 먼저 end를 움직인 다음

start를 하나씩 이동하면서 구간을 좁혀가며 조건을 확인해요

 

조건에 해당하지않게되면

end가 배열의 끝까지 이동했는지 확인하고

끝까지 가지않았다면 end를 하나씩 이동하며 다시 start와 비교하는 과정을 거쳐요

.

.

.

.

예를 들어서

sum이 10이상인 구간을 찾는데

그 중에서 제일 빠른 구간을 찾는다고 할게요

초기상태의 배열은 처음과끝이 같고 현재합은 1이죠

다음으로는 end를 이동시키면서 우선 조건에 맞는지 검사할거에요

end를 이동하면서 현재 배열의 요소를 더해주고 이동해요

 

(시작위치 1이라고 가정)

[1, 4] 인경우에 합이 10이되면서 조건에 만족하네요

 

이다음에는

end가아니라 start를 움직일거에요

start를 움직일때 현재 배열의 요소를 빼주고 움직여요

다시 조건에 맞지않게되었네요

end를 움직여서 다시 구간을 찾아가야해요

[2,5] 인경우에 합이14로 조건에 만족하네요

다시 start를 움직여서 구간을 최소화 시켜요

 

[4, 5]일 때 다시 조건에 맞지않으니까

end를 뒤로!!

 

이런식으로 계속 뒤로 가면서 조건을 찾아가는 알고리즘이에요

 

 

비교를 위해서 끝까지가는 과정을 보여드렸지만

문제의 조건인 제일 빠른 구간이여야하므로

도중에 조건문을 통해서 빠져나와서 답은 [1,4]가 되겠죠?