[Java]투 포인터 / 슬라이딩 윈도우 알고리즘

비슷하면서도 다른 두 알고리즘을 설명하겠습니다. 

공부를 목적으로 진행하는 포스팅으로 만약 틀린 부분이 있거나 미흡한 점이 있다면 피드백 부탁드리겠습니다.

 

투 포인터와 슬리이딩 윈도우.

이 두 알고리즘은 선형 공간(1차원 배열)을 2회 이상 반복적으로 탐색해야 할 경우 O(N^2) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다는 공통점이 있습니다. 

 

그렇다면 이 두 알고리즘의 차이점은 무엇일까요?

 

바로, 부분 배열 길이의 변화 여부입니다. 

 

더 쉽게 말해서, 투 포인터 알고리즘은 부분 배열의 길이가 가변적이지만 슬리이딩 윈도우 알고리즘은 부분 배열의 길이가 고정적입니다. 

 

 

투 포인터

투 포인터는 연속되고 길이가 가변적인 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘입니다. 여기서 중요한 것은 "연속되고 가변적인"입니다. 값이 연속된다는 말은 정렬을 뜻하는 것일 수도 있으니 부분 배열로 작성하였습니다. 만약 문제에서 주어진 배열이 연속된 부분 배열을 통하여 문제를 해결하라는 것이 아니면 (예를 들어, 연속적이지 않은 arr[0]과 arr[3]을 부분 배열로 하는 문제) 투 포인터 알고리즘을 사용할 수 없습니다. 이런 상황에서는 주어진 배열을 그대로 이용하여 문제를 해결하거나 배열의 인덱스와 값을 함께 list에 저장한 후 오름차순, 혹은 내림차순 정렬을 통하여 연속성을 추가해준 다음에 투 포인터 알고리즘을 사용하여야 합니다. 

 

즉, 투 포인터 알고리즘에서는 대게 두 개의 유형이 존재합니다. 

1) 2개의 포인터 변수 시작점이 배열의 시작점인 경우.

2) 정렬된 배열 안에서 2개의 포인터 변수가 각각 시작점과 끝점(arr.length-1)에 위치한 경우  

 

투 포인터로 해결해야 하는 문제에서는 모든 배열의 값들을 필연적으로 탐색하여 특정 조건을 일치시키는 개수 혹은 최저, 최대 값 등을 찾는 문제이므로 대게 '조합', '백트래킹'을 떠올리기 쉽습니다. 틀린 키워드는 아니지만 '백트래킹'으로 시간을 줄여준다고 하더라도 출제자는 '투 포인터'를 의도하고 출제하기 때문에 시간 초과를 벗어날 순 없을 것입니다. 

 

투 포인터 알고리즘을 해결하기 위해서는 보통 배열을 가리키는 2개의 포인터 변수를 많이 사용하는데 바로 Left, Right입니다. (취향 차이지만 Statr, End로 해도 됩니다.) 또 문제마다 다르겠지만 Target 변수(목표로 하는 값)도 사용됩니다. 이 포인터 변수들을 이동해가면서 부분 배열을 구하고 원하는 값을 찾으면 됩니다. 

 

여기서 중요한 것은 두 포인터의 의미입니다. 이 두 포인터는 [Left, Right)을 의미합니다. (arr배열이 있으면 부분 배열은 arr[Left]부터 arr[Right-1]까지의 부분 배열을 뜻합니다.) 

 

만약, 정수로 이루어진 배열에서 연속된 부분 배열의 합이 특정 값(Target)을 이루는 부분 배열의 개수를 구하는 문제가 있다고 가정했을 때, 두 포인터 변수의 이동 조건은 다음과 같습니다. 

 

(1) 부분 배열의 합이 Target 값보다 크거나 같으면  Left = Left + 1 해줍니다. (부분 배열의 길이를 줄여 합을 빼준다. )

if(sum >= Target) Left++;

(2) 부분 배열의 합이 Target 값보다 작으면 Right = Right + 1 해줍니다. (부분 배열의 길이를 늘려 합을 더한다.)

if(sum < Target) Right++;

(3) 부분 배열의 합이 Target 값과 같다면 결과 값을 +1 해줍니다. 

if( sum == Target) count++;

 

※ (1)에서 부분 배열의 합이 Target과 같은데 왜 Left를 늘려주냐 라는 의문이 생길 수도 있습니다. 이건 아주 간단합니다. 다음 배열을 탐색해야 하기 때문에 left를 늘려주는 것입니다. 

 

PPT로 간단하게 예제를 보여드리겠습니다. 부분 배열의 합이 10이 되는 부분 배열의 개수를 세는 문제입니다.

(PPT가 너무 많아서 중간 과정은 잘랐습니다;;)

 

여기서부터 조금 생략하겠습니다. 위와 같은 작업을 반복한 것입니다. 

 

 

반복문을 종료하는 시점은 R이 배열의 길이를 초과하는 경우입니다. 하지만 상황에 따라 다릅니다. 만약 R이 증가하여 배열의 마지막(arr.length)에 위치하였을 때 부분 배열의 길이가 Target보다 작다면 L의 위치 여부와 관계없이 그대로 종료해도 됩니다. 

 

투 포인터로 해결할 수 있는 대표적인 문제를 소개하겠습니다. 

 

www.acmicpc.net/problem/2003

2003번: 수들의 합 2

위에서 설명한 그대로의 문제입니다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_2003 {
	// BOJ / 2003번 / 수 들의합2 / 투 포인터 / 실버3
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
		
		int n = Integer.parseInt(stk.nextToken());
		int m = Integer.parseInt(stk.nextToken());
		stk = new StringTokenizer(br.readLine(), " ");
		int [] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(stk.nextToken());
		}
		
		int l = 0;
		int r = 0;
		int sum = 0;
		int answer = 0;
		while(true) {
			
			if(sum >= m) {
				sum -= arr[l++];
			}
			else if( r == n) break;
			else if(sum < m) {
				sum += arr[r++];
			}
			
			if(sum == m) {
				answer++;
			}
		}
		
		System.out.println(answer);
	}
}

 

저는 반복문을 무한 루프로 한 다음 따로 break 조건문을 걸어줬지만,

true 대신 r <= n으로 탈출 조건을 걸어주셔도 됩니다. 

 

투 포인터를 구성하는 코드는 짧습니다. 게다가 시간 복잡도는 O(N).

간단하면서도 강력한 알고리즘입니다.

 

다른 유형의 투 포인터 알고리즘 문제를 보여드리겠습니다. 

 

위에서 설명드렸듯이, 연속성이 존재하지 않으면 투 포인터 알고리즘을 사용할 수 없다고 했습니다. 

 

www.acmicpc.net/problem/3273

3273번: 두 수의 합

위와 같은 문제입니다. 

 

이러한 문제는 두 포인터 변수 L과 R의 시작점을 같은 0부터 시작하여 구하고자 하면 시간 복잡도 O(N) 안에서 문제를 해결할 수 없습니다.

 

그렇다면 어떻게 해야 할까요? 

정렬을 통해서 연속성을 추가해주는 것입니다. 연속성을 추가해준다는 것이 값을 연속적으로 정렬한다는 의미도 될 순 있겠지만 두 개의 포인터 변수로 구성되는 부분 배열의 연속성을 시작점부터 시작되는 같은 진행방향 연속성이 아닌 처음과 끝에서 시작하는 반대 진행방향의 연속성으로 볼 수도 있을 것입니다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_3273 {
	// BOJ / 3273번 / 두 수의 합 / 투 포인터 / 실버4
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
		
		int arr[] = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(stk.nextToken());
		}
		Arrays.sort(arr);
		int x  = Integer.parseInt(br.readLine());
		int answer = 0;
		int l = 0; 
		int r = arr.length-1;
		while(l < r) {
			int sum = arr[l] + arr[r];
			// 가장 큰 원소와 더했는데 x보다 작거나 같으면 l++
			if(sum <= x) {
				l++;
			}
			// 가장 큰 원소와 더했는데 x보다 크면 r--
			else if(sum > x) {
				r--;
			}
			if(sum == x) answer++;
			
		}
		System.out.println(answer);
	}
}

 

반복문 탈출 조건은 L 포인터 변수가 R을 넘을 경우입니다. 이러한 경우의 투 포인터 알고리즘도 O(N)으로 끝낼 수 있습니다. 

 

 

 

슬라이딩 윈도우

슬라이딩 윈도우 알고리즘은 연속되는 투 포인터와 유사하게 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘이지만 부분 배열의 길이(크기)가 고정적입니다. 어떤 창문을 왼쪽부터 오른쪽으로 밀어 오면서 창문 안에 있는 값들을 부분 배열이라고 생각하면 될 것 같습니다. 

 

또 다른 차이점은 투 포인터 알고리즘은 부분 배열의 길이가 가변적이기 때문에 부분 배열의 구간을 정할 2개의 포인터 변수가 필요한 반면, 슬라이딩 윈도우 알고리즘은 부분 배열의 길이를 고정적으로 잡기 때문에 포인터 변수가 2개일 필요가 없습니다. 즉, 고정적인 부분 배열의 크기를 나타내는 변수가 있다면 포인터 하나만 있어도 부분 배열의 크기를 알고 있기 때문에 각 배열의 끝을 어딘지 알 수 있습니다. 

 

슬라이딩 윈도우 알고리즘을 구현하는 방법도 간단합니다. 아래 주황색 칸이 3의 고정 길이를 가지는 부분 배열이라 가정하겠습니다. 주어진 문제가 부분 배열의 합을 구하는 것이라 할 때, 오른쪽으로 한 칸 옮기더라도 옮기기 전 부분 배열과 옮기고 난 후에는 겹치는 부분이 존재합니다. 즉, 기존 구간에서 빠지게 되는 가장 왼쪽 칸의 값은 삭제하고 새 구간에 포함되는 값을 추가해주면 됩니다. 

 

몇 가지 유형의 슬라이딩 윈도우 알고리즘 문제를 소개하겠습니다. 

 

www.acmicpc.net/problem/10025

10025번: 게으른 백곰

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_10025 {
	// BOJ / 10025번 / 게으른 백곰 / 슬라이딩 윈도우 / 실버4
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
		
		int n = Integer.parseInt(stk.nextToken());
		int k = Integer.parseInt(stk.nextToken());
		
		int arr[] = new int[1000001];
		for(int i=0; i<n; i++) {
			stk = new StringTokenizer(br.readLine(), " ");
			int w = Integer.parseInt(stk.nextToken());
			int p = Integer.parseInt(stk.nextToken());
			
			arr[p] = w; 
		}
		int sum = 0;
		int max = 0;
		int window = 1 +(2*k);
        	boolean flag = false;
            
		for(int i=0; i<=1000000; i++) {
        		// 초반 k-1범위 전까지는 sum을 max랑 비교하면안됨.
			if(i == window-1) flag = true;
			if(i >= window) {
				sum -= arr[i-window];
			}
			sum += arr[i];
			if(sum > max && flag) {
				max = sum;
			}
		}
		System.out.println(max);
	}
}

누적합을 이용하는 방법입니다. window 변수에 부분 배열의 고정 길이를 저장하고 i를 포인터 변수로 지정하여 i가 window크기를 넘어가면 직전 부분 배열과 현재 부분 배열중 겹치지 않는 값(arr[i-window])을 빼주고 추가된 값을 더해줍니다. 

  

flag의 역할은 처음 부분 배열이 완성되지 않았는데 sum과 max값을 비교하는 것을 방지해주는 역할을 합니다. 

 

 

www.acmicpc.net/problem/2075

2075번: N번째 큰 수

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ_2075 {
	// BOJ / 2075번 / N번째 큰 수 / 슬라이딩 윈도우 / 골드5
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		
		StringTokenizer stk;
		stk= new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<n; i++) {
			pq.add(Integer.parseInt(stk.nextToken()));
		}
		
		for(int i=1; i<n; i++) {
			stk = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<n; j++) {
				int num = Integer.parseInt(stk.nextToken());
				
				if(pq.peek() < num) {
					pq.poll();
					pq.add(num);
				}
			}
		}
		
		System.out.println(pq.poll());
	}
}

자료구조(우선순위 큐)를 활용한 유형입니다.  

 

부분 배열의 고정 길이는 우선순위 큐의 size(길이)입니다. 즉, 고정 길이만큼 초기에 우선순위 큐에 넣어주고 

그다음 원소들을 poll(), add()함으로써 고정 길이를 유지해주는 것입니다.