[ ᴀʟɢᴏʀɪᴛʜᴍ ] Sliding Window (슬라이딩 윈도우) & Two Pointer(투 포인터)

⚠️

[백준 2559번 - 수열] 문제를 풀며 공부한 내용이라, 부득이하게 문제에 대한 설명이 위에 있습니다.

백준 2559번 - 수열

매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.

예를 들어, [3, -2, -4, -9, 0, 3, 7, 13, 8, -3]와 같이 10일 간의 온도가 주어졌을 때, 모든 연속적인 이틀간의 온도의 합은 [1, -6, -13, -9, 3, 10, 20, 21, 5]와 같다.

이때, 온도의 합이 가장 큰 값은 21이다.

매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다.

10 2
3 -2 -4 -9 0 3 7 13 8 -3

출력

첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.

21

문제 풀이

우선, 아주 쉽게 생각해서 반복문으로 돌면서 n개의 수를 더한 값들을 구하기로 했습니다.

// 최저 온도는 -100이지만, 결과값은 -100보다 더 작을 수 있으므로, -Infinity로 설정한다.
let result = -Infinity;;

for(let i = 0; i <= N - K; i++){
    let temp = 0;
    for(let j = 0; j < K; j++){
        temp += temperatures[i + j]
    }
    result = Math.max(result, temp)
}

console.log(result)

구현이 간단하지만, 이렇게 하면 N 즉, temperatures의 길이가 2 이상 100,000 이하이므로 최대 O(100,000 * K) 시간이 걸립니다. 보시다시피 ‘4520ms’라는 어마어마한 시간이 걸립니다. 만약 시간 제한이 더 짧다면 통과하지 못합니다.

더 나은 방법들을 검색해보다가 슬라이딩 윈도우라는 알고리즘을 알게 되었습니다.

슬라이딩 윈도우(Sliding Window)

슬라이딩 윈도우란, 고정된 크기의 부분 배열(윈도우)를 한 칸씩 움직이며 연속된 값을 효율적으로 계산하는 알고리즘입니다. 연속된 구간에 창문을 한 칸씩 밀며 창문에 나타난 범위만 계산을 하는 모양이라서 슬라이딩 윈도우라고 합니다. 위 문제와 같이 연속된 구간의 최댓값/합을 구하는 문제에서 쓰입니다.

하나씩 옆으로 밀면서 새로 들어오는 값을 + 하고, 가장 왼쪽 값 하나를 - 하는 방식으로 구간을 계산합니다. 이 때, Math.max() 를 사용하면 최댓값을, 계속해서 더한 다면 누적 합을 구할 수 있습니다.

풀던 문제를 기준으로 슬라이딩 윈도우를 적용하는 모습을 표현하면 아래와 같습니다.

• 최대 온도의 합으로 처음 K개의 합을 구합니다.
• 한칸씩 이동하며 다음 숫자를 더하고, K개 이전의 값을 빼줍니다.
• 계산한 값을 기존 최대 온도의 합과 비교하여 큰 값을 저장합니다.
• 배열을 전부 순회하여 값을 출력합니다.

이를 코드로 구현하면 다음과 같습니다.

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = Number(input[0].split(' ')[0]);
const K = Number(input[0].split(' ')[1]);
const temperatures = input[1].split(' ').map(temperature => Number(temperature));

let result = 0;

// 처음 K까지의 합을 먼저 구합니다.
for(let i = 0; i < K; i++) {
	result += temperatures[i];
}

let curSum = result;

// 합을 구한 다음 수부터 구해야 하므로 i는 K부터 순회합니다.
for(let i = K; i < N; i++) {
	curSum += temperatures[i]; // 새로운 값을 추가하고
	curSum -= temperatures[i - K]; // 가장 왼쪽의 값을 뺴줍니다.
	result = Math.max(result, curSum); // 기존의 값과 비교하여 큰 수를 저장합니다.
}

console.log(result);

이렇게 하면 O(N)의 시간복잡도로, 한번의 순회만으로 답을 구할 수 있습니다.

비교해보면 기존의 4520ms에서 176ms로 시간을 크게 단축시킬 수 있었습니다.

투 포인터(Two Pointer)

배열을 한 번만 순회하여 답을 도출하는 기법에는, 슬라이딩 윈도우의 연장선으로 투 포인터 알고리즘도 있습니다. 사실상 슬라이딩 윈도우보다 자주 접하게 되는 알고리즘입니다.

투 포인터는 두 개의 포인터(인덱스를 가리키는 포인터)를 이용해서 하나의 배열을 탐색하는 알고리즘입니다.

슬라이딩 윈도우와 다른점은, 투 포인터는 윈도우의 크기를 유동적으로 조절할 수 있다는 것입니다.

기존의 슬라이딩 윈도우는 윈도우의 크기가 K로 정해진 채로 순회합니다. 즉, 포인터가 하나입니다.

이와 달리 투 포인터는 포인터가 두 개입니다. 조건에 따라 윈도우를 늘리거나 줄일 수 있고, 유지할 수도 있습니다.

풀던 문제와 같은 수열 문제나, 부분합을 구하는 문제에서 사용할 수 있습니다. 예를 들면 조건을 만족하는 가장 긴/짧은 구간을 구하는 것과 같이 구간의 크기가 바뀌는 문제에는 슬라이딩 윈도우 대신 투 포인터를 사용해야 합니다.

풀 던 문제에 적용하면 다음과 같이 구현할 수 있습니다.

let curSum = 0;

for (let i = 0; i < K; i++) {
  curSum += temperatures[i];
}

let result = curSum;

// 포인터를 만들어줍니다.
let start = 0;
let end = K - 1;

// 배열을 순회하면서 값을 계산하고 
// 포인터의 간격을 유지(같은 값으로 커지게 함)하면서 포인터를 이동합니다.
while (end < N - 1) {
  curSum = curSum - temperatures[start] + temperatures[end + 1];
  start++;
  end++;
  result = Math.max(result, curSum);
}

console.log(result)