슬라이딩 윈도우

[알고리즘/Java] 슬라이딩 윈도우(Sliding Window)

[ 1 ] 기본내용 슬라이딩 윈도우는 이전에 포스팅한 투 포인터(Two Pointers) 알고리즘과 원리가 유사한 알고리즘이다. 투 포인터 알고리즘은 2개의 포인터를 활용하여 부분 배열의 길이를 유동적으로 활용하거나 2개의 특정 원소 값에만 접근하는 반면, 슬라이딩 윈도우는 부분 배열의 길이가 고정적이라는 특징이 있다. "한 정수 배열에서 길이가 3인 부분 배열 중 합이 가장 큰 부분 배열은 무엇인가?"라는 문제가 있다고 가정하자. - arr = [3, 5, 2, 1, 7, 4, 10, 6, 8, 9] 위 배열이 주어졌을 때 가장 큰 부분 배열의 합을 구하기 위해서 중첩 반복문을 활용할 수 있을 것이다. 하지만, 중첩 반복문을 활용할 경우 시간 복잡도가 O(N^2)이기 때문에 효율적이지 않다. 이때 슬라..