투 포인터 알고리즘(Two Pointer)
알고리즘 스터디를 하다가 새로운 알고리즘을 발견해서 호다닥 공부해서 정리하는 "아주 주관적인" 글입니다.
🔎투 포인터 알고리즘을 쓰는 이유
완전 탐색을 할 경우 시간초과를 피하기 위해서 쓰는 방법이다.
예를 들어서 N칸의 1차원 배열이 있을 때, 모든 경우의 수를 다 테스트 하면 O(N^2)이 된다.
입력인 N의 최대 범위가 너무 크다면 시간초과를 피 할수 없을 것이다.
이럴 때 사용하는 알고리즘이 투 포인터 알고리즘이다.
우선 해당 알고리즘은 포인터 포인터 2개를 사용한다.
2개의 포인터는 start, end, left, right 와 같은 배열의 시작과 끝을 의미하는 두개의 포인터를 사용한다는 뜻이다.
저는 포인터 2개를 start와 end로 사용하겠습니다.
start와 end의 초기값은 모두 0이며, start<=end를 반드시 만족해야 합니다.
예시 문제로 설명을 해보겠습니다.
예시 문제는 N개의 1차원 배열에서 M이상의 합을 구할 수 있는 경우의 수를 구하는 문제입니다.
아래의 과정은 start가 N인 동안 반복해줍니다.
- 만약 현재 부분합이 m이상이거나, 이미 e=N이면 s++ (탐색 범위를 감소시킴)
- 그렇지 않다면 e++ (탐색 범위를 증가시킴)
- 현재 부분합이 M과 같으면 결과를 증가시킴.
예시 진행 과정
우선 저희는 부분합이 5인 경우의 수를 찾아야 합니다.
빨간 화살표가 start, 파란 화살표가 end를 의미합니다.
초기 시작값은 위에서 설명해드린 대로 start=0, end=0입니다.
이때의 부분합인 S=1이 될것입니다.
S가 M보다 작기 때문에 탐색범위를 증가시킵니다. 즉 end를 한 칸 증가시킵니다.
위 그림은 start가 0이고, end가 1인 상황입니다.
S=3입니다.
S가 M보다 작기 때문에 탐색범위를 증가시킵니다. 즉 end를 한 칸 증가시킵니다.
위 그림은 start가 0이고, end가 2인 상황입니다
S=6이 됩니다.
S가 M보다 크기때문에 탐색범위를 감소시킵니다. 즉 start를 한 칸 증가시킵니다.
위 그림은 start가 1이고 end가 2인 상황입니다.
S=5가 됩니다.
S가 M이상이기 때문에 탐색범위를 감소시킵니다. 즉 start를 한 칸 증가시킵니다.
위 그림은 start와 end가 모두 2인 경우입니다.
S=3입니다.
S가 M보다 작기 때문에 탐색범위를 증가시킵니다.(end 한 칸 증가)
위 그림은 start가 2이고, end가 3인경우입니다.
S=7이 됩니다.
S가 M보다 크기 때문에 탐색범위를 감소시킵니다. (start 한 칸 증가)
이렇게 쭉쭉 진행하시면 됩니다.
이러한 방식으로 즉 투 포인터를 사용해서 모든 경우의수를 구할 수 있냐? 라는 생각이 들것입니다.
우리는 부분합이 M인 경우의 수를 찾는 것입니다.
그 부분합은 수열로 이어져있어야 합니다.
당연히 M을 넘는다면 앞에서 짜르는것이 당연합니다.
이렇게 M을 넘을때 앞의 범위를 짜르고, M보다 작을때 뒤의 범위를 증가시키면 모든 경우의 수를 다 찾을 수 있습니다.
⏰시간 복잡도
투 포인터 알고리즘은 매 루프마다 항상 투 포인터 중 하나는 반드시 1씩 증가하고 있고, 각 포인터가 N번 누적 증가해야 알고리즘이 끝난다.
따라서 각각 배열 끝에 다다르느는데, O(N)이라도 합쳐서 O(N)이 된다.
왜 O(N)이냐?
start와 end중 하나는 매 과정에서 무조건 1씩 증가한다. s와 e는 최대 N까지 증가할 수 있으며, 항상 s<=e이기 때문에 둘이 증가하는 과정은 최대 N번만 반복될 것이다. (N^2 을 넘을수가 없음)
따라서 투 포인터 알고리즘을 사용하면 모든 경우의 수를 비교하는( O(N^2) ) 이 걸리는 문제를 O(N)으로 해결할 수 있다.
코드는 간단하게
while문을 돌면서, 만약 start가 n까지 간다면 break시키고,
m을 넘지 않는다면 sum값을 계속 더하고, end값을 증가시켜줍니다.
만약 m을 넘는다면 start가 가르키는 값을 sum에서 빼주면 됩니다.