[python] 알고리즘 문제 해결 전략 1권 :: 록페스티벌 (p6) 문제

문제 : 알고리즘 문제 해결 전략 [록페스티벌] p6

문제

커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 밴드를 몇 팀 섭외할 지는 아직 결정하지 않았지만, 페스티벌의 간판 스타인 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 이하의 절대/상대 오차가 있는 답은 정답 처리됩니다.

나의 답

1번째 답

처음에는 단순히 모든 경우의 수를 계산해보는 동적 프로그래밍 방식을 사용해볼까 생각해봤다. (단순, 무식하게 풀 수 있을까?) 하지만, test case 수도 100개일 뿐더러 대여할 수 있는 날의 수가 최대 1000일이기 때문에 힘들겠다고 예상했다. 아래의 코드는 위의 그림처럼 sliding window 방식으로 옮겨가며 모든 평균을 계산하는 코드이다.

for i in range(1,len(Day)): => Day-team으로 고쳐야함...
    for j in range(0,len(Day)-i+1):
        for k in range(j,j+i):
            result += expense[k]
        result /= i
        if ex_min > result:
            ex_min = result

이 코드의 복잡도는 O(N^3) 이므로 좋은 알고리즘이라고 볼 수 없다.

따라서, 더 빠르게 알고리즘을 구현할 수 있을까 생각해보다가

평균을 계산하고 대소를 비교하는 것과 합을 계산하고 대소를 비교하는 것이 날의 수가 같을 때는 차이가 없다는 것을 깨닫고, 같은 날의 수를 비교할 때는 합만 계산해서 비교하면 되겠다고 생각했다. 하지만 나눗셈 연산이 몇 번 빠졌을 뿐 반복문의 횟수차이에는 기여하지 못하므로 복잡도는 같았다.

2번째 답

계속 생각해보던 중, 계산해야하는 날들의 수를 줄여보면 어떨까 싶었다. day가 7이고 team이 5일 때, 최소 5팀이 페스티벌에 참여하므로 5개의 비용을 묶은 경우부터 계산을 해야한다. 이 때, 5일 페스티벌을 진행할 때 가장 평균이 적은 연속된 날을 구하려면 더해서 평균 내기보다 더 적은 수인 남은 2일의 합이 큰 경우를 고르면 된다. 위의 그림에서는 중간의 경우(2번째 경우)가 4로 가장 크므로 비용의 총합이 같다는 전제 하에 남은 날들의 합이 중간의 경우가 가장 작다는 걸 알 수 있다.

쉽게 말해서, 많은 수의 계산이 필요한 최소화 문제를 적은 수의 계산으로 가능한 최대화 문제로 만들자는 것이다. 이는 team이 1일 때 동적 프로그래밍과 비슷한 성능을 내고, team이 커질 수록 효율이 커진다. 하지만 궁극적으로 for문의 수를 줄이지 못했으므로 역시 시간복잡도는 같았다.

# 록페스티벌
# 2020-02-04

testcase = int(input()) 
ex_min = [] # testcase 각각의 최소값들을 담아두는 행렬

for case in range(0,testcase): # testcase
    dayteam = input() # 문자열로 받기
    expense= input()

    Expense = [] # 해당 날짜의 금액
    Day = int() # 날들의 수
    Team = int() # 이미 섭외한 팀의 수
    ex_sum = int() # 존재하는 날짜의 금액 총합
    obj_index = int() # 공백 index 읽기
    obj_index_bf = int(0) # 이전 index 읽기

    # 공백 기준으로 '날 수', '섭외된 팀 수' 끊어읽기
    for index in range(0,len(dayteam)):
        if dayteam[index]==" ":
            obj_index = index

    Day = int(dayteam[:obj_index])
    Team = int(dayteam[obj_index:])

    # 공백 기준으로 '금액' 끊어읽기

    for index in range(0,len(expense)):
        if expense[index]==" ":
            obj_index = index
            Expense.append(int(expense[obj_index_bf:obj_index]))
            obj_index_bf = obj_index
        elif index == len(expense)-1:
            Expense.append(int(expense[obj_index_bf:]))

    # 금액의 합 계산

    for index in range(0,len(Expense)):
        ex_sum+=Expense[index]

    ex_min.append(ex_sum/Day)

    for i in range(1,Day-Team+1): # 남는 배열을 이용해서
        tmp = 0
        for j in range(0,i): # 합이 가장 큰 배열 찾기 => 나머지의 합은 가장 작은 배열
            result = 0
            for k in range(0,j):
                result += Expense[k]
            for k in range(Day-i+j,Day):
                result += Expense[k]
            if result>=tmp:
                tmp = result
        mean = (ex_sum-tmp)/(Day-i) # 미리 계산해둔 총 합 - 남는 배열의 합
        if ex_min[case] >= mean:
            ex_min[case] = mean
        else:
            continue

for case in range(0,testcase):
    print(ex_min[case])

다른 답

결국 다른 알고리즘을 찾아보고 결론을 내었다. 이 알고리즘은 중복되는 계산을 줄이고자 위의 그림처럼 요소를 하나씩 더해가며 계산하는 방식이다. 날의 수를 일치시켜서 경우의 수를 나눈 후, 경우의 수에서 최솟값을 찾으려고 했던 나는 이 알고리즘을 보고 깨달았다. 수학적으로 생각하다가 틀리는 경우가 굉장히 많은데 이번에도 그런 경우인거 같다.

# 록페스티벌
# 2020-02-04

testcase = int(input()) 
ex_min = [] # testcase 각각의 최소값들을 담아두는 행렬

for case in range(0,testcase): # testcase
    dayteam = input() # 문자열로 받기
    expense= input()

    Expense = [] # 해당 날짜의 금액
    Day = int() # 날들의 수
    Team = int() # 이미 섭외한 팀의 수
    ex_sum = int() # 존재하는 날짜의 금액 총합
    obj_index = int() # 공백 index 읽기
    obj_index_bf = int(0) # 이전 index 읽기

    # 공백 기준으로 '날 수', '섭외된 팀 수' 끊어읽기
    for index in range(0,len(dayteam)):
        if dayteam[index]==" ":
            obj_index = index

    Day = int(dayteam[:obj_index])
    Team = int(dayteam[obj_index:])

    # 공백 기준으로 '금액' 끊어읽기

    for index in range(0,len(expense)):
        if expense[index]==" ":
            obj_index = index
            Expense.append(int(expense[obj_index_bf:obj_index]))
            obj_index_bf = obj_index
        elif index == len(expense)-1:
            Expense.append(int(expense[obj_index_bf:]))

    ex_min.append(int(987654321))

'''주요코드'''
    for i in range(0,Day-Team+1): # 시작 index
        tmp_sum=0
        tmp_mean=0
        for j in range(0,Team): # 최소 날 수
            tmp_sum+=Expense[i+j]
        tmp_mean = tmp_sum/Team
        if tmp_mean<=ex_min[case]:
            ex_min[case]=tmp_mean
        for j in range(Team,Day-i) : # 계산할 날 수
            tmp_sum+=Expense[i+j]
            if tmp_mean>tmp_sum/(j+1):
                tmp_mean=tmp_sum/(j+1)
                if tmp_mean<=ex_min[case]:
                    ex_min[case]=tmp_mean
'''주요코드'''

for case in range(0,testcase):
    print(ex_min[case])

주요코드 부분만 보면, i는 요소들의 합 계산이 시작되는 index이다. 첫번째 j for문은 주어진 Team에 의해 결정되며, index i부터 가능한 한 가장 적은 날동안 페스티벌을 주최한다고 할 때 발생하는 비용의 평균을 계산하는 코드이다. 다음 j for문은 주어진 최소의 날 이상 페스티벌을 주최한다고 할 때의 경우를 나타낸다.

이와 같은 알고리즘을 가지고 코드를 짜보니 index가 헷갈려서 간단하고 적은 양의 코드를 짜는데 시간이 꽤 걸리긴했다. 중요한 건 시간 복잡도가 줄었다는 것이다. for문이 하나 사라짐으로 인해서 시간 복잡도가 감소하였고, 아직까지는 더 나은 알고리즘을 찾지 못하였다.

결론

수학적으로 생각하기 전에, 문제를 효율적으로 해결할 수 있는 방법을 찾자는 생각을 하자.