[알고리즘] 투 포인터, 슬라이딩 윈도우 알고리즘 자바 구현 (백준 2003, 2559)

투 포인터 알고리즘이란?

▶ 1차원 배열에 존재하는 순차적 부분 배열에 접근해야 할 때 두개의 점을 활용하여 중복 연산을 줄이는 알고리즘

 

예시 문제를 활용하여 알아보자.

 

문제 : https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

연속되는 부분수열의 합이 M인 경우를 찾는 문제이다.

 

예제 입력 2의

1 2 3 4 2 5 3 1 1 2 의 경우를 살펴보면

 

단순 탐색 시

1	2	3	4	2	5	3	1	1	2
1

연속되는 합이 5가 되는 경우를 찾기 위해

첫 번째 원소의 합 = 1

1	2	3	4	2	5	3	1	1	2
1	3

1 + 2 번째의 원소의 합 = 3

1	2	3	4	2	5	3	1	1	2
1	3	6

1 + 2 + 3번째의 원소의 합 = 6 이고, 나머지 숫자는 자연수이므로

더이상 만족할 수 없기 때문에 반복을 중지하고,

 

이제 두번째 원소부터 위의 연산을 반복할 것이다.

하지만 위 방법은 첫 번째 탐색시 방문한 1,2,3을 두 번째 탐색 시 2,3 중복 방문하므로 수가 길어질수록 매우 비효율적이 될 것이다.

 

이와 같은 상황에 투 포인터 알고리즘을 사용할 수 있다.

 

 

 

투 포인터 알고리즘

배열의 위치를 가르키는 Left, Right 라는 두 개의 포인터를 사용한다.

초기 상태에선 둘 다 arr[0] 값을 가르키고 있다.

 

이제 찾고자 하는 숫자가 M 이라고 할때

 

1. L ~ R 까지의 부분배열의 합이 M 보다 크면 L + 1
2. L ~ R 까지의 부분배열의 합이 M 보다 작으면 R + 1
3. L ~ R 까지의 부분배열의 합이 M 이면 L + 1, 결과 카운트 + 1

위 규칙에 따라 연산을 진행한다.

 

1은 M보다 작으므로 R이 한 칸 이동한다.

 

3은 M보다 작으므로 R이 한 칸 이동한다.

 

6은 M보다 크므로 L이 한 칸 이동한다.

 

현재 정답을 찾았으므로 정답 카운트를 +1 해주고

다시 탐색하기 위하여 L도 한 칸 이동한다.

 

위와 같은 작업을 배열의 마지막까지 반복하면 O(n) 의 시간복잡도로 결과를 얻을 수 있다.

이제 이 과정을 코드로 나타내보자.

전체 코드

// [백준] 2003. 수들의 합 2 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int[] arr;
	static int n;
	static int m;
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	n = Integer.parseInt(st.nextToken());
    	m = Integer.parseInt(st.nextToken());
    	arr = new int[n];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i = 0; i < n; i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}

    	System.out.println(twoPointer());
    }
    
    public static int twoPointer() {
    	int left = 0; 
    	int right = 0;
    	int sum = 0;
    	int count = 0;
    	
    	while (true) {
    		
    		// 1 + 3. L ~ R 까지의 부분배열의 합이 M 보다 크거나 같으면 L + 1
    		if(sum >= m) {
    			sum -= arr[left++];
    		}
    		// 종료 조건 (right이 마지막 범위를 넘어갔을 경우)
    		else if(right == n) {
    			break;
    		}
    		// 2. L ~ R 까지의 부분배열의 합이 M 보다 작으면 R + 1
    		else if(sum < m) {
    			sum += arr[right++];
    		}
    		// 3.L ~ R 까지의 부분배열의 합이 M 이면 결과 카운트 + 1
    		if(sum == m){
    			count++;
    		}
    	}	
    	return count;
    }
}

 

위에서 살펴본 것 같이, 투 포인터 알고리즘은 부분 배열의 길이가 가변적인 것을 알 수 있다.

 

문제에서 부분 배열의 길이가 일정하다면

투 포인터 알고리즘과 유사한 슬라이딩 윈도우 알고리즘을 사용할 수 있다.

 

 

 

 

 

슬라이딩 윈도우 알고리즘이란?

▶ 투 포인터와 유사하게 부분 배열에 효율적으로 접근하기 위한 알고리즘. (부분 배열 길이 고정)

 

위와 같이 창문을 오른쪽으로 쭉 밀면서 안에 들어오는 배열을 탐색한다고 생각하면 된다. 

길이가 고정적이므로 투 포인터와 다르게 하나의 포인터만 있으면 된다.

 

예시 문제를 활용하여 알아보자.

 

문제 : https://www.acmicpc.net/problem/2559

2559번: 수열

특정 길이의 부분 배열들의 합을 각각 구해서, 그 중 가장 큰 값을 찾아야 하는 문제이다.

위 문제도 일반적인 탐색 방법을 사용할 경우 매우 비효율적이라는 것을 위의 투 포인터 때의 예시에서 알 수 있다.

 

 

슬라이딩 알고리즘

 

예제 입력 1의

주어진 배열 : 3 -2 -4 -9 0 3 7 13 8 -3

배열의 길이 : 2

 

의 경우를 살펴보면

 

위와 같이 한칸씩 길이가 2인 창문을 밀어가며 확인하면서

 

결과적으로 문제에서 요구하는 결과를 O(n) 의 시간복잡도로 빠르게 얻을 수 있다.

 

이 과정도 코드로 나타내보자.

 

전체 코드

// [백준] 2559. 수열 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int 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());
       	n = Integer.parseInt(st.nextToken());
    	k = Integer.parseInt(st.nextToken());
    	arr = new int[n];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i = 0; i < n; i++) {
    		arr[i] = Integer.parseInt(st.nextToken());	
    	} 

    	System.out.println(slidingWindow());
    }
    
    public static int slidingWindow() {
    	int max = 0;
    	int sum = 0;
    	
    	for(int i = 0; i < n; i++) {
    		sum += arr[i];
    		
    		// 최초에 나온 합을 최댓값으로 잡아놓음
    		if(i == k - 1) {
    			max = sum;				
    		}
    		
    		// 처음 길이를 벗어났을 때 부터 한칸씩 밀어주면서 최댓값 비교
    		if(i >= k) {
    			sum -= arr[i - k];
    			max = Math.max(max, sum);   
    		}
    	}   	
    	return max;
    }
}