[기초 알고리즘 #06] 슬라이딩 윈도우

이번에 공부해 볼 알고리즘은 슬라이딩 윈도우(Sliding Window)입니다.

투 포인터 알고리즘과 엮어서 복잡한 구현을 요하는 문제로 자주 출제되는 유형이기도 하죠!

1. 슬라이딩 윈도우 (Sliding Window)

3명이서 나란히 앉아서 영화를 보고 싶다는 가정을 해봅시다…!

영화관 좌석의 예매 상태는 아래와 같다고 하네요.

3명이 나란히 앉기 위해서는,

예매 가능한 좌석 3개가 나란히 붙어있는 좌석을 찾아야할 겁니다.

아래 이미지 처럼요.

이처럼,

주어진 데이터 중 고정된 범위 내에서 값을 확인하고 문제를 해결하는 방식이

슬라이딩 윈도우 알고리즘 입니다.

여기서 고정된 범위를 윈도우(Window)라고 칭하며,

이 윈도우를 미끄러지듯 이동하며 연산을 수행하기 때문에 슬라이딩 윈도우 알고리즘 이라고 부릅니다.

2. 연습문제

위의 예시는 아래 문제에서 참고해봤는데요.

• 백준 29700 우당탕탕 영화예매 » 링크

이 문제를 풀어보면서 슬라이딩 윈도우 알고리즘을 연습해봅시다.

• 영화관 좌석의 세로길이 N과 가로길이 M, 그리고 영화를 관람할 인원수 K를 입력받습니다.

    N, M, K = map(int, input().split())
  

• 이어서, 영화관 좌석의 예매현황을 담아줄 seats 변수에 담아줍니다.

    seats = []
  
    for _ in range(N):
        seats.append(list(input().strip()))
  

• 좌석의 왼쪽 위(seats[0][0])부터 각 행 별로 윈도우를 슬라이딩하며 예매 가능한 경우의 수를 탐색합니다.

    answer = 0
  
    for i in range(N):
        window = [] # 각 행마다 window를 초기화
        for j in range(M):
            if len(window) < K: # K보다 window의 길이가 작을 때
                window.append(seats[i][j])
            elif len(window) == K: # window의 길이가 K와 같을 때
                window.pop(0)
                window.append(seats[i][j])
  
            if K == window.count('0'): # window의 모든 값이 '0', 즉 예매 가능한 좌석일 때
                answer += 1
  

  • 각 행을 j 인덱스로 순회하면서 window를 슬라이딩 합니다.
  • 아직 K 보다 window의 길이가 작다면 window를 채워줍니다.
  • window의 길이가 K와 같다면, window의 가장 앞에 값을 pop()해주고 seats[i][j]값을 window에 append() 해줍니다.
  • window의 모든 값이 ‘0’, 즉 예매 가능한 좌석일 때, answer 변수의 값을 1 증가시킵니다.

이제 전체 코드를 봐봅시다.

N, M, K = map(int, input().split())
seats = []

for _ in range(N):
    seats.append(list(input().strip()))

def solution(N, M, K, seats):
    answer = 0

    for i in range(N):
        window = []
        for j in range(M):
            if len(window) < K:
                window.append(seats[i][j])
            elif len(window) == K:
                window.pop(0)
                window.append(seats[i][j])

            if K == window.count('0'):
                answer += 1

    return answer

print(solution(N, M, K, seats))

이렇게 슬라이딩 윈도우 알고리즘을 활용해서 문제를 풀어보았는데요.

아래 코드는 순회 도중 ‘0’값을 만났을 때, 브루트 포스한 방법으로 다시 반복문을 활용해 예매 가능여부를 탐색하는 방법입니다.

N, M, K = map(int, input().split())
seats = []

for _ in range(N):
    seats.append(list(input().strip()))

def solution(N, M, K, seats):
    answer = 0

    for i in range(N):
        for j in range(M):
            if seats[i][j] == '0':
                check = True
                for k in range(K):
                    if j + k < M:
                        if seats[i][j + k] != '0':
                            check = False
                    else:
                        check = False
                if check:
                    answer += 1

    return answer

print(solution(N, M, K, seats))

오류 없이 정답은 나오지만,

채점 결과 슬라이딩 윈도우 풀이보다 더 오래 걸리는 것을 확인 할 수 있습니다.

⚫ 더 연습해볼 수 있는 문제

1. 백준 10025 게으른 백곰 » 링크
2. 백준 30804 과일탕후루 » 링크

---