[알고리즘] 투 포인터(Two Pointers) 알고리즘
1차원 배열이 주어졌을 때, 특정 연속된 구간의 합이 M이 되는 경우의 수를 구하려면 어떻게 해야 할까?
가장 단순하게 생각해볼 수 있는 방법은 2중 반복문을 돌리는 것이다.
public class Main {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 2, 5, 3, 1, 1, 2}; // 크기가 10인 1차원 배열
int m = 5; // 연속된 구간의 합이 5인 경우를 찾는다.
int count = 0;
for (int i = 0; i < 10; i++) {
int sum = arr[i];
for (int j = i + 1; j < 10; j++) {
if (sum == m) {
count++;
} else if (sum > m) {
break;
} else {
sum += arr[j];
}
}
}
}
}
당연히 위의 방법과 같이 이중 반복문을 돌리게 되면 시간 복잡도가 $\mathcal{O}(N^{2})$ 으로 배열의 크기가 커지면 커질수록 느려진다.
1차원 배열의 연속된 구간에 대해 2중 반복문을 개선하기 위해 나온 것이 투 포인터 알고리즘이다.
투 포인터(Two Pointers) 알고리즘
아래와 같은 1차원 배열이 있다.
위의 1차원 배열에 대해 연속된 구간의 합이 5인 것의 경우의 수를 구해보자.
위의 2중 반복문과 큰 차이는 없는데, Right를 우측으로 하나씩 옮기면서 arr[left] + ... + arr[right]의 값이 5보다 크다면 더이상 right를 우측으로 옮기는건 무의미하다. right를 우측으로 옮겨봤자 마찬가지로 5보다 크기 때문이다. 따라서, 이 경우 left를 우측으로 옮긴다.
코드로 살펴보자.
public class Main {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 2, 5, 3, 1, 1, 2}; // 크기가 10인 1차원 배열
int m = 5; // 연속된 구간의 합이 5인 경우를 찾는다.
int count = twoPointers(arr, m);
}
private static int twoPointers(int[] arr, int m) {
int sum = 0, count = 0;
int left = 0, right = 0;
while (true) {
if (sum > m) { // 1. left를 우측으로 옮기는 경우
sum -= arr[left++];
} else if (right == arr.length - 1) { // right를 우측으로 옮기기 전에 배열의 끝을 가리키는지 확인한다.
break;
} else { // 2. right를 우측으로 옮기는 경우
sum += arr[right++];
}
if (sum == m) count++;
}
return count;
}
}
'Algorithm > Theory' 카테고리의 다른 글
[알고리즘] LIS(Longest Increasing Subsequence) (0) | 2021.03.03 |
---|---|
[알고리즘] 슬라이딩 윈도우(Sliding Window) 알고리즘 (0) | 2020.10.31 |
[알고리즘] 최단 경로 - 벨만 포드 알고리즘 (0) | 2020.10.25 |
[알고리즘] 최단 경로 - Dijkstra 알고리즘 (0) | 2020.10.25 |
[알고리즘] 최단 경로 - Floyd-Warshall 알고리즘 (0) | 2020.10.16 |
댓글
이 글 공유하기
다른 글
-
[알고리즘] LIS(Longest Increasing Subsequence)
[알고리즘] LIS(Longest Increasing Subsequence)
2021.03.03 -
[알고리즘] 슬라이딩 윈도우(Sliding Window) 알고리즘
[알고리즘] 슬라이딩 윈도우(Sliding Window) 알고리즘
2020.10.31 -
[알고리즘] 최단 경로 - 벨만 포드 알고리즘
[알고리즘] 최단 경로 - 벨만 포드 알고리즘
2020.10.25 -
[알고리즘] 최단 경로 - Dijkstra 알고리즘
[알고리즘] 최단 경로 - Dijkstra 알고리즘
2020.10.25