: 주어진 배열에서 고정 크기의 윈도우(창문)를 이동하면서, 윈도우 내의 정보를 처리하는 알고리즘 기법
주어진 배열의 크기가 n
이고, 윈도우의 크기가 w
일 때, 모든 구간 합을 배열에 넣어 리턴하라.
- 창문을 한 칸 옮기면,
w - 1
칸은 겹친다.- 이때, 창문을 옮길 때마다
w
개를 전부 다 더하는 작업을 하지 말고, 이전에 계산한 값을 사용하는 방향으로 접근해야 한다.
만약 모든 창문 위치마다 O(W)
에 합을 구하면 전체가 O(NW)
의 시간복잡도를 가지게 된다.
하지만 슬라이딩 윈도우 테크닉을 사용하면, 처음 한 번의 작업에 대해서만 O(W)
에 구간 합을 구할 수 있고, 이후 윈도우를 한 칸씩 밀 때마다 O(1)
에 구간 합을 구할 수 있다.
따라서 전체 시간복잡도는 O(N)
이 된다.
function slidingWindowSum(arr, w) {
const result = [];
let windowSum = 0;
// 초기 윈도우 합 구하기
for (let i = 0; i < w; i++) {
windowSum += arr[i];
}
result.push(windowSum);
// 윈도우 이동하며 구간합 계산
for (let i = w; i < arr.length; i++) {
windowSum += n[i] - n[i - w]; // 새로운 값 더하고, 이전 값 빼준다.
result.push(windowSum);
}
return result;
}
슬라이딩 윈도우라는 걸 공부하게 만든 프로그래머스 문제..
철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4]
로 원형 수열을 만들면 다음과 같습니다.
원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.
3 ≤ elements의 길이 ≤ 1,000
1 ≤ elements의 원소 ≤ 1,000
elements | result |
---|---|
[7,9,1,1,4] | 18 |
길이가 1인 연속 부분 수열로부터 [1, 4, 7, 9] 네 가지의 합이 나올 수 있습니다.
길이가 2인 연속 부분 수열로부터 [2, 5, 10, 11, 16] 다섯 가지의 합이 나올 수 있습니다.
길이가 3인 연속 부분 수열로부터 [6, 11, 12, 17, 20] 다섯 가지의 합이 나올 수 있습니다.
길이가 4인 연속 부분 수열로부터 [13, 15, 18, 21] 네 가지의 합이 나올 수 있습니다.
길이가 5인 연속 부분 수열로부터 [22] 한 가지의 합이 나올 수 있습니다.
이들 중 중복되는 값을 제외하면 다음과 같은 18가지의 수들을 얻습니다.
[1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22]
function solution(elements) {
const sumSet = new Set();
for (let w = 1; w <= elements.length; w++) { // w는 window의 크기
let windowSum = 0;
for (let j = 0; j < elements.length; j++) { // 배열 elements를 순회 (j는 창문 시작 인덱스)
if (j === 0) { // 맨 처음의 창문에 대해서만 직접 합을 구한다.
for (let k = 0; k < w; k++) { // 창문 안에 있는 요소들을 (w개)
windowSum += elements[k]; // windowSum에 더해준다.
}
} else { // 이후 창문들은 이전에 계산한 값을 활용한다.
windowSum -= elements[j - 1]; // 이전 값 빼주기
windowSum += elements[(j + w - 1) % elements.length]; // 다음 값 더해주기, 원형 수열이므로 % 이용
}
sumSet.add(windowSum);
}
}
return sumSet.size;
}
슬라이딩 윈도우 신기하다라구여 고생하셨습니다