알고리즘

[알고리즘] 슬라이딩 윈도우(sliding window) 알고리즘 이란?

슬라이딩 윈도우 슬라이딩 윈도우 알고리즘은 연속되는 투 포인터와 알고리즘과 유사하지만 부분 배열의 길이가 고정적이다. 고정적인 틀을 오른쪽으로 밀어 오면서 틀 안에 있는 값들을 부분배열이라고 생각하면 된다. 투 포인터 알고리즘은 두 개의 포인터를 이동하기 때문에 2개의 변수가 필요하지만 슬라이딩 윈도우 알고리즘은 부분 배열의 길이를 고정적으로 하기 때문에 1개의 변수만 필요하다. 설명 아래 노란색 칸이 3의 고정길이를 가지는 부분 배열이라 가정, 주어진 문제가 부분 배열의 합을 구하는 것이라 하면 오른쪽으로 한 칸 옮기더라도 옮기기 전 부분 배열과 옮기고 난 후에 겹치는 부분이 존재한다. 즉 기존 구간에서 빠지게 되는 가장 왼쪽 칸의 값은 삭제하고 새 구간에 포함되는 값을 추가하면 된다. 예시 2가지 긴..

[알고리즘]Prefix sum 알고리즘이란?

누적합(Prefix sum)란? 나열된 수의 누적된 합을 말한다. 배열의 일부 구간에서 대한 합을 매우 빠르게 구할 수 있게 해준다. N개의 원소로 이루어진 배열이 주어졌을 때 반복문을 통해 부분 배열의 합을 구하려면 O(N)이 걸리는데, 누적합을 이용하면 부분합을 0(N+M)으로 구할 수 있다. 설명 1차원 배열 arr을 순차 탐색하면서 sum 배열을 만들어주면 된다. 활용법 arr의 i항부터 j항 까지 합을 S(i,j)라고 하자. 이때 S(ij) = sum[j] - sum[i-1]이다. S(2,4) = S[4]=S[1]이다. 쉽게 생각하면 참고문제) https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 ..