슬라이딩 윈도우 알고리즘
슬라이딩 윈도우 알고리즘
- 슬라이딩 윈도우 알고리즘
고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 푸는 알고리즘
예를 들면 0, 1, 2, 3, 4, 5, 6이 있고 윈도우는 배열[0]~[2] 정도의 사이즈라면…
[0, 1, 2], 3, 4, 5, 6
0, [1, 2, 3], 4, 5, 6
…
0, 1, 2, 3, [4, 5, 6]
이런 식으로 진행해서 푸는 것이다.
[0, 1, 2]의 합을 구하고 > 3
다음 배열은 [1, 2, 3]
0이 빠지고 3이 들어온 배열이다.
그렇다면 3-0+3 = 6이 된다.다음 배열은 [2, 3, 4]
1이 빠지고 4가 들어온 배열이다.
그렇다면 6-1+4 = 9가 된다.
이런 식으로 구간 합 구하기, 부분 문자열 구하기 등 일정 범위의 값을 비교할 때 사용된다고 한다. 교집합의 정보를 공유하고 차이가 나는 양쪽 끝 원소만 갱신하는 방법이라고 서술되기도 한다.
위의 예시로 보자면 [1, 2, 3]와 [2, 3, 4]의 교집합은 [2, 3] 이고 차이가 나는 양쪽 끝 원소인 [1, 4]가 계속 갱신된다.
투포인터 알고리즘
※ 미리 적어두자면 이 부분은 아직 공부가 부족한 부분이기 때문에 다른 분의 글을 참조하는 것을 권장합니다.
슬라이딩 윈도우 알고리즘은 투 포인터 알고리즘과 연동된다고도 한다.
- 투포인터 알고리즘
2개의 포인터를 두고 조작하며 원하는 값을 도출한다고 하는 알고리즘
연속의 수의 합이 5가 되는 경우를 찾는다고 가정했을 때, 현재 부분합이 5보다 작을 경우 right 포인터를 증가시켜 arr[right]값을 더하고, 5보다 크면 left 포인터를 증가시켜 arr[left] 값을 뺀다.
5와 같을 경우 right포인터 증가 후 arr[right]를 증가시키거나, left포인터 증가 후 arr[left]값을 빼주는데 후자의 경우는 left 인덱스가 right 인덱스를 넘어서는 경우를 고려해야 된다.
임의로 만든 배열이라서 그런지, 혼자서 해보다보니 헷갈린다. 코드를 돌려보면서 확인할 시간이 없는 관계로 나중에 더 깊이 공부할 필요가 있어보인다.
공통점과 차이점
- 공통점
1차원 배열을 2회 이상 반복 탐색해야 할 경우 O(N^2) 이상 걸리며, 부분 배열을 활용하여 O(N)으로 이용된다.
슬라이딩 윈도우 알고리즘의 경우는 처음 창문에서만 O(N)이고 이후 한칸씩 밀대마다 O(1)에 구간합을 구할 수 있다고 한다. 투포인터 알고리즘도 마찬가지로 두 포인터 중 하나씩 1씩 증가하면서 진행하기 때문이다.
- 차이점
투포인터 알고리즘: 부분 배열의 길이가** 가변적
슬라이딩 윈도우 알고리즘: 부분 배열의 길이가 **고정적
공부가 너무 부족한 것 같다. 열심히 해야겠다…