[Algorithms] 투 포인터 알고리즘
[Algorithms] 투 포인터 알고리즘
안녕하세요? 정리하는 개발자 워니즈입니다. 이번시간에는 투 포인터 알고리즘에 대해서 정리를 해보도록 하겠습니다. 필자가 생각하기에는 특정 알고리즘의 영역이라기보다는 기법중 하나로 생각이 됩니다.
문제 유형으로는 1차원 배열에서 합이 특정 값이 되는 부분 배열이 몇개가 되는지를 구하는 내용이 많습니다.
이번 포스팅은 특정 알고리즘이 아니므로, 예시 문제를 먼저 정리하고 관련해서 투포인터 기법을 적용하여 풀이를 하는 내용에 대해서 정리하겠습니다.
1. 문제 설명
N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.
10 5
1 2 3 4 2 5 3 1 1 2
예시는 위와 같습니다. 총 10개의 input이 있고, 값의 합이 5만큼 되는 연속되는 부분 수열을 찾는 것입니다.
예를들어, {2, 3}의 합이 총 5가 되므로 답중 하나의 예시가 됩니다.
2. 투 포인터 기법 적용
만약, 전체 해답을 모두 구한다면, 2중 for문을 돌려서 해결 할 수 있습니다. 모든 경우의 수를 봤을 때, O(N^2)만큼의 시간 복잡도가 걸리므로, 조건에서 fail이 되게 됩니다.
따라서, 위와 같은 문제는 특정 기법을 적용해야 되는데 여기서 사용되는 것이 바로 투포인터 기법입니다.
start, end이렇게 2개의 포인터를 준비합니다. 그리고 다음과 같은 알고리즘 순서로 진행을 합니다.
- end 포인터가 계속 늘려가면서 합의 값이 M이거나 보다 크게 되는 구간까지 늘립니다.
- 구간합이 M보다 작아지는 지점까지 start 포인터를 늘려 갑니다.
- 합의 구간이 M이 되는 경우 result값을 한개씩 증가합니다.
2개의 포인터가 동시에 움직이면서, 전체 가지 수중에서 불필요한 검증을 제거 하기위해서 최적의 해만을 찾아나가는 기법입니다.
3. 투 포인터 그림 설명
위의 예시에 대해서 애니메이션으로 보시면 확실히 이해가 되실 것입니다. 아래의 그림이미지를 보면서 하나씩 정리해보겠습니다.
처음에는 위에 보이는것과 같이, start/end 포인터가 0지점을 가리키고 있습니다. 그리고 현재의 SUM값은 0 입니다.
end포인터를 우측으로 옮기면서 값을 하나씩 더해나갑니다. 구간합이 M(위의 예시에서는 5)과 같거나 커지는 지점까지 늘려나갑니다.
그리고 위의 그림과 같이 M값을 넘어가게 되면, start 포인터를 오른쪽으로 옮기면서 SUM값을 빼게 됩니다.
위의 그림과 같이 합이 M이 되는 구간을 찾고 result에 값을 한개 더하게 됩니다. 그리고 M과 같거나 커졌기 때문에 다시 start 포인터를 우측으로 옮깁니다.
위와 같은 방식으로 계속해서 start/end 2개의 포인터를 움직이면서 구간합이 M이 되는 것을 찾고 result를 추가해줍니다.
2번째 해답은 위와같습니다.
3번째 해답은 위와같습니다.
다시 start/end 포인터를 하나씩 옮기게 되면 위와 같고, end포인터는 끝까지 갔습니다. 더이상의 해답이 없기 때문에 start 포인터도 끝까지 우측으로 옮기게 되고, 해답을 찾습니다.
최종적으로는 답이 3개가 되고 while 문은 끝이 납니다.
4. 소스 코드
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N,K;
static int[] Arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine().trim());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
Arr = new int[N + 1];
st = new StringTokenizer(br.readLine().trim());
for (int i = 0; i < N; i++) {
Arr[i] = Integer.parseInt(st.nextToken());
}
int i,j;
i = 0 ; j = 0;
int sum = 0;
int count = 0;
while(true){
if(sum >= K) sum -= Arr[i++];
else if(j == N) break;
else sum += Arr[j++];
if(sum == K) count++;
}
System.out.println(count);
}
}
위의 소스코드는 모든 내용을 기입하였고, 그 내용중에서 투포인터가 적용되는 부분은 아래와 같습니다.
while(true){
if(sum >= K) sum -= Arr[i++];
else if(j == N) break;
else sum += Arr[j++];
if(sum == K) count++;
}
while문이 계속해서 수행되면서, 아래의 if문을 보게 되면, j포인터가 end포인터고, i포인터가 start포인터가 되면서 수행하게 됩니다.
5. 마치며…
이번시간에는 투포인터 기법에 대해서 정리를 해보았습니다. 알고리즘을 학습하면서 정말 하나의 문제를 풀더라도 다양한 기법과 알고리즘이 존재한다는 것을 알게 되었습니다. 관련한 알고리즈 문제는 추후에 포스팅 하도록 하겠습니다. 투포인터 문제는 1차원 배열이 존재하고 특정값으로 매칭되는 부분 수열을 구하는 문제에서 적용해 볼 수 있다는 것을 알게 되었습니다.
