[python] 투 포인터(Two Pointers) 알고리즘

코딩테스트를 풀다보면 투 포인터로 풀어야하는 문제들을 자주 볼 수 있습니다. 오늘은 투 포인터 알고리즘에 대해 알아봅시다.

 

 

[투 포인터(Two Pointers) 알고리즘]

---

 

• 리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리하는 알고리즘
• 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다.

 

위 그림과같이 두 개의 포인터(점)의 위치를 기록하면서 처리한다. 

 

 

[시간복잡도]

---

O(N)

매 루프마다 항상 두 포인터 중 하나는 1씩 증가하고 각 포인터가 n번 누적 증가해야 알고리즘이 끝난다.

각각 배열 끝에 다다르는데 O(N)이라 둘을 합해도 여전히 O(N)이다.

 

 

 

 

[예제]

---

백준 3237 두 수의 합이 투 포인터의 예제입니다.

https://e-you.tistory.com/330로 가시면 자세한 문제와 풀이를 볼 수 있습니다.