알고리즘2 [알고리즘] 슬라이딩 윈도우(Sliding Window) 슬라이딩 윈도우(Sliding Window)고정된 사이즈의 윈도우(창)이 배열 안을 이동하면서 윈도우 내에 담은 데이터를 이용해 문제를 푸는 알고리즘.차이가 나는 양쪽 끝 원소를 갱신한다.슬라이딩 윈도우는 항상 구간의 너비가 고정되어 주어진다. 만약, 윈도우의 크기가 3일 경우 sw[0] = arr[0] + arr[1] + arr[2]...sw[n] = sw[n-1] - arr[n-1] + arr[n-1+(윈도우크기)] 예제 Q. 연속된 index n개의 합의 최소를 구하시오. 그리고 합이 최소일 때의 인덱스(a,b)를 구하시오.(a 1. sw배열에 모두 담고 최소값 구하는 방식import java.util.Scanner;public class Main { static Scanner sc.. 2024. 10. 28. [알고리즘] 누적합(Prefix Sum) +Java객체 배열 선언 & 생성 누적합 (Prefix Sum) 누적합이란? 배열의 인덱스가 증가함에 따라 그 누적된 합을 미리 구해 놓는 것, '전처리' 라고도 함.arr배열을 일일히 for문으로 돌면서 합을 구하면 되는것 아닌가란 의문을 던질 수 있다. 하지만 이렇게 하면 시간복잡도 측면에서 성능이 저하된다. (테스트케이스에서 시간초과 문제가 발생하기도 함..) 그러므로 누적합을 미리 구하여 사용한다. 누적합 구현크기가 10인 arr 배열의 누적합을 구해보자 1. 누적합으로 [a] ~ [b] 의 합을 구하기. " acc [ b ] - acc [ a - 1 ] " 2. acc배열을 채우기인덱스 0 일때는 arr[0] 그 자체가 된다.그 이후부터는 acc[i] = acc[i-1] + arr[i] " acc[0]=.. 2024. 10. 28. 이전 1 다음
