[알고리즘] 코테 유형 분석 13. 슬라이딩 윈도우

안녕하세요 오늘은 슬라이드 윈도우 문제에 대해 분석해보는 시간을 갖도록 하겠습니다.

슬라이딩 윈도우란 2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하며 문제를 해결하는 방식입니다. 투 포인터와 유사하나 포인터가 가리키는 범위가 고정되어 탐색한다는 차이점이 존재합니다. 따라서 슬라이딩 윈도우 문제는 고정된 범위를 탐색하는 문제에서 사용됩니다. 슬라이딩 윈도우의 장점은 새롭게 추가된 값과 제거될 값 2개만을 탐색하면 되기 때문에 탐색 속도를 줄일 수 있습니다.

백준 12891(DNA 비밀번호) 문제는 모든 문자열에 등장하는 문자가 A C G T일 때 각 문자가 주어진 문자의 부분 문자열 중 각 문자가 특정 횟수 이상 존재하게 만들 수 있는 비밀번호의 종류의 수를 구하는 문제입니다. 비밀번호의 크기만큼 포인터 범위를 설정해서 시작부터 끝까지 탐색하여 범위 내의 각 문자의 개수가 최소 문자 개수보다 모두 크다면 경우를 증가하면 됩니다. 여기서 주의할 점은 문자 전체를 탐색하면 시간 초과가 발생하기 때문에 삭제된 문자와 추가된 문자의 카운트만 체크하여 시간 초과를 방지하는 것입니다.

백준 11003(최솟값 찾기) 문제의 경우 D = A_i-L+1 ~ A_i 중 최솟값이라고 할 때 D에 저장된 수를 구하는 문제입니다. 이 경우 deque를 이용하여 읽어올 값의 인덱스와 값을 저장하여 문제를 풀 수 있습니다. deque의 가장 앞이 최솟값이 오도록 설정하면 새롭게 읽은 값이 deque의 뒤의 값보다 클 때까지 deque의 끝 값을 제거한 후 새롭게 읽은 값을 추가합니다. 이 후 가장 처음 값의 인덱스가 현재 인덱스 범위 내에 존재하지 않을 경우 deque의 제일 앞의 값을 제거합니다. 로직이 완료되면 deque의 제일 앞의 값을 D에 추가하여 정답을 리턴합니다.