본문 바로가기
프로그래밍/알고리즘 문제풀이

[Python]Sliding Window(슬라이딩 윈도우) / Prefix Sum(누적 합)

by 가유르 2024. 9. 7.

예시 문제 - [알고스팟] 록 페스티벌 (ID: FESTIVAL)

문제

커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 밴드를 몇 팀 섭외할 지는 아직 결정하지 않았지만, 페스티벌의 간판 스타인 L개의 팀은 이미 섭외가 끝난 상태입니다. 따라서 페스티벌은 최소 L일 이상 진행하게 됩니다.

이번에 사용할 공연장은 하루 빌리는 데 드는 비용이 매일 매일 다릅니다. 때문에 공연 일정을 잘 정해서 공연장 대여 비용을 줄이려고 합니다. 앞으로 N일간의 공연장 대여 비용을 알고 있다고 합시다. 이 중 L일 이상을 연속해서 대여하되, 공연장을 하루 빌리는 데 드는 평균 비용을 최소화하려면 어떻게 공연장을 빌려야 할까요?

예를 들어 앞으로 6일간 공연장을 빌리는 데 드는 비용이 각 {3, 1, 2, 3, 1, 2}라고 합시다. 이미 세 팀을 섭외했다고 하면, 3일 대신 4일 동안 공연을 진행해서 평균 비용을 더 저렴하게 할 수 있습니다. 3일 동안의 평균 대여 비용을 최소화하는 방법은 2일째부터 4일째까지 공연장을 대여하는 것인데, 이 때 하루 평균 (1+2+3)/3 = 2의 비용이 듭니다. 반면 2일째부터 5일째까지 공연장을 대여하면 평균 비용이 (1+2+3+1)/4 = 7/4밖에 되지 않습니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C ≤ 100)가 주어집니다. 각 테스트 케이스의 첫 줄에는 공연장을 대여할 수 있는 날들의 수 N (1 ≤ N ≤ 1000)과 이미 섭외한 공연 팀의 수 L (1 ≤ L ≤ 1000, L ≤ N)이 주어집니다. 그 다음 줄에는 N개의 숫자로 공연장 대여 비용이 날짜별로 주어집니다. 모든 비용은 100 이하의 자연수입니다.

출력

입력에 주어지는 각 테스트 케이스마다 한 줄에 최소의 평균 대여 비용을 출력합니다. 10-7 이하의 절대/상대 오차가 있는 답은 정답 처리됩니다.

예제 입력

2
6 3
1 2 3 1 2 3 
6 2 
1 2 3 1 2 3

예제 출력

1.75000000000
1.50000000000

 

참고 코드

def festival(N, L, cost):
    min_cost = float('inf')
    for i in range(N):
        for j in range(i, N):
            if j-i+1 >= L:
                avg_cost = sum(cost[i:j+1]) / (j-i+1)
                min_cost = min(min_cost, avg_cost)
    return min_cost

시간 복잡도: O(n^3)

Sliding Window(슬라이딩 윈도우)

배열, 리스트와 같은 선형 자료구조에서의 부분 배열 처리 테크닉. 윈도우, 즉 부분 배열을 한 원소씩 옆으로 이동시키며 계산을 수행하는데 이 때 중복 계산을 피할 수 있어 시간 복잡도가 줄어든다.

def festival(N, L, cost):
    min_cost = float('inf')
    tot_cost = sum(cost[:L])  # 처음 윈도우의 합을 구함
    min_cost = tot_cost / L  # 처음 윈도우의 평균을 구함

    for i in range(L, N):  # 윈도우를 한 칸씩 오른쪽으로 이동
        tot_cost += cost[i] - cost[i - L]  # 윈도우를 이동하면서 합을 갱신
        avg_cost = tot_cost / L
        min_cost = min(min_cost, avg_cost)

    return min_cost

시간 복잡도: O(n)

Prefix Sum(누적 합)

배열, 리스트의 구간 합을 빠르게 계산하기 위해 누적 합을 전처리 하는 방법이다.

def festival(N, L, cost):
    psum = [0] * (N + 1)  # psum[0] = 0, 나머지는 cost의 누적합을 저장할 배열
    
    # 누적합 계산
    for i in range(1, N + 1):
        psum[i] = psum[i-1] + cost[i-1]
    
    min_cost = float('inf')
    
    # 최소 평균 계산
    for i in range(N):
        for j in range(i + L - 1, N):  # 길이가 L 이상인 부분 배열만 고려
            total_cost = psum[j + 1] - psum[i]  # psum은 1부터 시작하므로 j+1

시간 복잡도: O(n^2)

반응형