투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화합니다.
알고리즘이 매우 간단하다.
이미지 출처 : https://emre.me/coding-patterns/two-pointers/
Coding Patterns: Two Pointers
In Coding Patterns series, we will try to recognize common patterns underlying behind each algorithm question, using real examples from Leetcode.
emre.me
위의 그림에서 Sum: 8이고 정렬된 배열에서 투 포인터들이 가리키는 값의 합으로 포인터의 위치를 이동시키고 있다.
1 + 9 = 10으로 원하는 값인 8보다 크기 때문에 합값을 줄이기 위해서 우측에 있는 포인터를 좌측으로 즉 값이 줄어드는 방향으로 이동시켜 최종값인 8에 가까워지게 만든다.
두번째 사진은 1 + 6 = 7으로, 원하는 값인 8보다 작기 때문에 좌측에 있는 포인터를 우측으로 즉 값이 늘어나는 방향으로 이동시켜 최종값인 8에 가까워지게 만든다.
이렇게 원하는 값인 8을 만들 수 있는 2 + 6이 완성되는데, 이 알고리즘 없이 순수하게 탐색한다면, 시간복잡도는 O(N^2)이 되지만 두 포인터중에 하나의 포인터는 무조건 움직이는 투포인터 알고리즘에서의 시간복잡도는 O(N)이 된다.
물론 정렬된 배열에만 사용 가능하기 때문에, 배열을 정렬하는데 드는 시간복잡도 O(nlogn)도 고려해야 한다.
https://mngprog.tistory.com/18
2018번 (silver5)
https://www.acmicpc.net/problem/2018간단한 투포인터 알고리즘을 사용한 문제이다. #include using namespace std;int main() { long N, start = 1, end = 1, count = 0; cin >> N; while (end N) start++; else if (sum 투포인터의 기본을 이
mngprog.tistory.com
간단한 백준문제로 투 포인터를 이해할 수 있다.
'Algorithm' 카테고리의 다른 글
| 4-1 탐색(DFS) (0) | 2025.01.20 |
|---|---|
| 3-3 정렬(RadixSort) (0) | 2025.01.20 |
| 3-2 정렬(Merge Sort) (0) | 2025.01.19 |
| 3-1 정렬(Quick Sort) (0) | 2025.01.18 |
| 1.구간 합 (0) | 2025.01.18 |