알고리즘
[알고리즘] 투 포인터
rubato.dev
2025. 7. 15. 11:22
- 1차원 배열에서 이중 for문으로 O(N^2)에 처리되는 작업을 2개의 포인터를 사용하여 O(N)에 해결하는 알고리즘
- 연속된 구간의 원소들을 처리하거나 정렬된 배열에서의 작업을 구현할 때 시도
📕 문제 1. 다음의 배열에서 원소들의 합이 x인 연속 부분 배열의 개수를 구하라.
arr = [1, 3, 6, 5, 2, 7, 9], x = 9
- 시작 시점을 한 칸씩 전진해나가면서 구간의 합을 구해야함.
📕 문제 2. 다음의 배열에서 두 개의 원소의 합이 x와 같은지를 확인하고, 같다면 각 원소의 인덱스를 반환하라.
arr = [10, 4, 15, 11, 7, 5], x = 15
- 이전 문제처럼 배열을 그대로 두고 st와 en 두 포인터를 0으로 잡으면 답을 찾을 수 없음.
- 배열이 정렬되어 있지 않으면 다음에 올 값이 이전 값보다 큰지 작은지 알 수 없음.
- 배열을 정렬 시킨 후 두 개의 포인터를 잡아야 한다. st = 0, en = N-1
- 두 원소의 합이 x보다 크면 en 감소 (st를 증가시키면 합이 더 커짐.)
💻 연습 문제
ℹ 참고