목록PS/알고리즘 (1)
Always awake
[알고리즘] 투 포인터와 슬라이딩 윈도우
투 포인터 S, E 혹은 L, R이라는 두가지 변수를 지정하여, 인덱싱을 저장하고자 한다. (두 포인터) 이후 각 포인터들을 이용하여 목표를 달성하자. 문제의 경우는 [3, 7, 2, 1, 6, 9, 11, 14] 라는 배열에서 합이 9인 연속된 부분을 찾는것 S, E 포인터 모두 인덱스 0번에서 시작하여 현재 합이 9보다 작다면 E를 한칸 오른쪽으로, 크다면 S를 한칸 오른쪽으로 이동하며 값을 구한다. 여러가지 방면에서 활용할 수 있으며, 이때 E-S가 일정하다면 슬라이딩 윈도우 라고 한다. 슬라이딩 윈도우 투 포인터 와 비슷하지만, 두 포인터 사이 간격이 일정해서 마치 유리창을 미닫는 모양이라고 하여 슬라이딩 윈도우라고 불리는 알고리즘 위 그림은 N = 8인 배열에서 K = 3의 길이를 가지는 부분수..
PS/알고리즘
2023. 12. 18. 17:38