슬라이딩 윈도우

투 포인터에서 두 포인터가 고정된 채로 움직이는 윈도우를 슬라이딩 윈도우라 한다. 저번에 투포인터에서 맨 앞 문자열을 추가하고 맨 뒤 문자열은 빼고, 이런 생각을 한 적이 있었는데 그 개념이 슬라이딩 윈도우에서 쓰인다. 네트워크 시간에도 배운 적이 있으니 잘 알고 넘어가도록 하자.

 

 

DNA 비밀번호 (12891)

처음으로 로직을 고민하고 코딩해 맞춘 문제이다. 기분이 째진다.

https://www.acmicpc.net/problem/12891

문제가 길어 링크를 남긴다.

 

1️⃣ 분석

 

문자열 길이와 부분 문자열 길이가 최대 백만이다. 최악의 경우 이중 for문을 통한 알고리즘 구현은 제한시간을 넘어가므로 불가하다. 그래서 투포인터의 진화형인 슬라이딩 윈도우를 써야 한다. 슬라이딩 윈도우는 O(N) 알고리즘이다.

 

2️⃣ 손으로 풀어보기

 

특정 길이가 되면 맨 앞은 문자열을 확인해 수를 더하고, 맨 뒤는 문자열을 확인해 수를 빼준다. 윈도우가 이동하면서 알파벳의 개수만 세면 된다.

 

3️⃣ 슈도 코드

 

위에서 생각한 걸 실제로 구현한 슈도 코드다. 리스트를 쓸지 딕셔너리를 쓸지 고민이 되었는데, 익숙한 리스트를 쓰기로 했다.

 

4️⃣ 실제 코드 작성

import sys
input = sys.stdin.readline
S, P = map(int, input().split())
A = list(input())
check = list(map(int, input().split()))
part = [0] * 4
cnt = 0

for i in range(P):
    if A[i] == "A":
        part[0] += 1
    elif A[i] == "C":
        part[1] += 1
    elif A[i] == "G":
        part[2] += 1
    elif A[i] == "T":
        part[3] += 1

i = 0
j = P - 1
while j != S:
    if part[0] == check[0] and part[1] == check[1] and part[2] == check[2] and part[3] == check[3]:
        cnt += 1
        
    if A[i] == "A":
        part[0] -= 1
    elif A[i] == "C":
        part[1] -= 1
    elif A[i] == "G":
        part[2] -= 1
    elif A[i] == "T":
        part[3] -= 1
    i += 1
    
    j += 1
    if A[j] == "A":
        part[0] += 1
    elif A[j] == "C":
        part[1] += 1
    elif A[j] == "G":
        part[2] += 1
    elif A[j] == "T":
        part[3] += 1
        
print(cnt)

틀린점이 몇 가지 있었다.

  • A = list(input()) 받은 문자열을 바로 한 글자씩 잘라 리스트로 만들고 싶었다. 문제는 "\n" 얘도 리스트에 들어가 버렸다.
  • while j != S 로 while문을 돌렸는데 마지막 인덱스는 확인하지 않는 문제가 생겼다.
  • if part[0] == check[0] ... 문자 수가 크거나 같은게 조건인데 같은 것만 확인하고 있다.

수정한 코드가 밑에 있다.

import sys
input = sys.stdin.readline
S, P = map(int, input().split())
A = list(input().rstrip())
check = list(map(int, input().split()))
part = [0] * 4
cnt = 0

for i in range(P):
    if A[i] == "A":
        part[0] += 1
    elif A[i] == "C":
        part[1] += 1
    elif A[i] == "G":
        part[2] += 1
    elif A[i] == "T":
        part[3] += 1

i = 0
j = P - 1
while True:
    if part[0] >= check[0] and part[1] >= check[1] and part[2] >= check[2] and part[3] >= check[3]:
        cnt += 1
        
    if A[i] == "A":
        part[0] -= 1
    elif A[i] == "C":
        part[1] -= 1
    elif A[i] == "G":
        part[2] -= 1
    elif A[i] == "T":
        part[3] -= 1
    i += 1
    
    j += 1
    if j == S:
        break
    if A[j] == "A":
        part[0] += 1
    elif A[j] == "C":
        part[1] += 1
    elif A[j] == "G":
        part[2] += 1
    elif A[j] == "T":
        part[3] += 1
        
print(cnt)

 

rstrip()

Return a copy of the string with trailing characters removed. The chars argument is a string specifying the set of characters to be removed. If omitted or None, the chars argument defaults to removing whitespace. The chars
 argument is not a suffix; rather, all combinations of its values are stripped

제거해야 하는 문자열을 지정하면 원 문자열에서 그것들을 제거한다. 만약 제거 문자열이 없다면 빈칸이나 \n을 제거한다.

 

💡배운점

  • rstrip()
  • 슬라이딩 윈도우 기본 개념

 

최솟값 찾기 (11003)

문제

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

예제 입력 1 

12 3
1 5 2 3 6 2 3 7 3 5 2 6

예제 출력 1 

1 1 1 2 2 2 2 2 3 3 2 2

 

1️⃣ 분석

 

문제에서 슬라이딩 윈도우의 크기를 정해주면 윈도우 속에서 최소값을 찾고 새로 들어온 원소와 최솟값을 비교하면 된다고 생각했다.

이따가 보겠지만 다음과 같은 문제가 있다.

 

  • 최소값이 슬라이딩이 움직일 때 매번 갱신되어야 한다.
  • for 문의 idx를 잘 설정한다 하더라도 무조건 시간 초과가 될 수 밖에 없다. 

 

2️⃣ 손으로 풀어보기

 

처음에 내가 생각한대로 문제를 풀면 한번 정해진 최솟값이 다시는 바뀌지 않는 문제가 생긴다. 만약 처음 정해진 최소값이 리스트 중에서 가장 작다면 계속 그 최솟값만 리스트에 들어간다.

이걸 해결하기 위해 윈도우가 움직일 때마다 최소값을 다시 정하는 방법이 있지만 시간초과가 된다. (실제 코드 보면서 이야기)

 

3️⃣ 슈도 코드

 

 

4️⃣ 실제 코드 작성

import sys
input = sys.stdin.readline
N, L = map(int, input().split())
A = list(map(int, input().split()))
D = []
min = A[0]

def checkMin(i):
    min = A[i-L]    
    for j in range(i-L, i):
        if min > A[j]:
            min = A[j]
    
    D.append(min)

for i in range(L-1):
    if min > A[i]:
        min = A[i]
    D.append(min)

for i in range(L, N+1):
    checkMin(i)

print(D)

처음 짰던 코드다. 이 코드에서 checkMin 함수가 윈도우가 움직일 때마다 최솟값을 계산하고 갱신한 다음 새로운 리스트 D에 넣는다. 처음 윈도우를 만들 때도 고려해 윈도우가 리스트에 다 들어올 때까지를 for문으로 계산하고 나머지는 checkMin 함수를 사용한다.

이렇게 하면 예시는 해결되었지만 시간 복잡도는 O(NL)이 나온다. N과 L둘다 5백만이므로 무조건 시간복잡도를 초과한다.

 

 

💡 새로운 자료구조 덱(deque) 

덱은 양방향으로 삽입과 삭제를 할 수 있는 자료구조다. 덱을 통해 정렬한 효과를 가져갈 수 있다.

deque

 

그럼 어떻게 deque을 통해 윈도우 안의 원소들을 관리하고 최솟값을 뽑아낼 수 있을까? 윈도우의 움직임과 정렬을 모두 덱으로 구현한다. 리스트를 바로 다루는 것이 아니라 덱을 통해 윈도우로 본 리스트를 추상화하는 것이다.

덱은 (인덱스, 숫자)라는 새로운 쌍으로 데이터를 저장할 수 있다. 덱에 (인덱스, 숫자) 이런 자료형이 지원되는게 아니고 이런 튜플이 하나의 객체이자 덱의 원소로 들어가는 것이다.

 

 

어떻게 덱으로 윈도우로 본 리스트를 추상화하는지 순서대로 알아보자. (인덱스, 값)의 형태로 튜플 객체의 형식으로 덱에 원소를 집어넣는다. 

  1. 덱에 원소를 넣을 때 가장 끝에 있는 값이랑 넣으려는 값이랑 비교한다. 만약 넣으려는 값이 더 작다면 앞에 있는 값을 지워버린다. 왜냐면 최솟값이 될 수 없기 때문이다. 이런식으로 안에 있던 값들을 다 제거하고 만약 제거할 값이 없다면 그대로 집어 넣는다.
  2. 그 다음 맨 앞의 인덱스가 윈도우 안에 들어있을 수 있는지 비교한다. 만약 있을 수 없다면 맨 앞 원소를 제거한다.

다음 과정을 모두 완료하면 인덱스 안의 최솟값이므로 이 값을 출력한다. (따로 리스트를 만들 필요가 없다.)

 

from collections import deque
import sys
input = sys.stdin.readline
N,L = map(int, input().split())
A = list(map(int, input().split()))
D = deque()

for i in range(N):
    while D and D[-1][1] >= A[i]:
        D.pop()
    D.append((i, A[i]))
    if D[0][0] <= i - L:
        D.popleft()
    print(D[0][1], end=" ")

 

이런 알고리즘을 구현하는게 참 신기하다. 많은 것을 보고 내 것으로 만들어야겠다.

 

💡배운점 

  • iteration 안에 넣는 원소를 튜플이나 다른 iteration 객체로 넣기 (인덱스, 값)
  • 윈도우가 보는 리스트 관점으로 덱을 추상화하기
  • 덱 사용하기
  • 굳이 원소를 위한 iteration 만들지 말고 그냥 출력하기

'Algorithm' 카테고리의 다른 글

[프로그래머스 코딩테스트 kit] 스택 - 기능개발  (0) 2025.09.12
[Do it 알고리즘 코딩테스트] 3-5. 스택과 큐  (0) 2025.09.08
[Do it 알고리즘 코딩 테스트] 3-3. 투포인터  (0) 2025.08.09
[Do it 알고리즘 코딩 테스트] 3-2. 구간 합  (0) 2025.08.07
[Do it 알고리즘 코딩 테스트] 3-1. 배열과 리스트  (0) 2025.08.06

티스토리툴바