투 포인터 (Two Pointers)

투 포인터 (Two Pointers) 투 포인터 알고리즘은 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻어내는 알고리즘입니다. 🎈 예제 길이가 n인 1차원 배열이 있을 때, 그 부분 배열의 원소의 합이 m이 되는 경우의 수를 알고 싶습니다. 모든 부분 배열을 탐색한다면 시간복잡도는 O(n^2)이 되겠습니다. 그러나 투 포인터를 사용하면 O(n) 에 문제를 해결할 수 있습니다. 포인터 2개를 만듭니다. start, end라고 하겠습니다. 처음 시작할 때는 start, end = 0 입니다. start = m) { start++; // start를 오른쪽으로 옮김 sum -= arr[start]; } else if (end == n) { break; } else { end++; // end를 ..
알고리즘 2022. 5. 23. 21:09
1