[알고리즘] 코드잇 - 투자 귀재 규식이3(Python)

실습설명

이미 sublist_max() 함수를 각각 Brute Force 과 Divide and Conquer 방식으로 작성했는데요. Brute Force로 풀었을 때는 시간 복잡도가 O(n^2), Divide and Conquer를 사용했을 때는 O(n lg n)였습니다.

 

이번 과제에서는 시간 복잡도를 O(n)로 한 번 더 단축 해 보세요.

 

힌트1

아래의 리스트를 예시로 생각해 봅시다.

profits = [7, -3, 4, -8]

profits의 최대 수익은 아래 두가지 중 하나입니다.

1. 부분문제 [7, -3, 4]의 최대 수익 (sublist_max([7, -3, 4]))

2. 부분문제 [7, -3, 4, -8]에서 -8을 포함한 구간의 최대 수익

 

첫 번째 경우는 당연하죠? 최대 수익 구간에 마지막 요소가 포함되지 않을 때 최대 수익은 부분 문제와 똑같습니다.

 

두번 째 경우는 첫 번째와 반대되는 경우인데요. 마지막 요소 -8이 포함돼서 최대 수익이 기존 값에서 변하는 경우죠. -8이 포함된 구간들은 총 네개의 구간이 있습니다.

 

1. [-8]

2. [4, -8]

3. [-3, 4, -8]

4. [7, -3, 4, -8]

 

이 구간들에서나올수 있는최대 수익이 바로마지막 요소 -8 이 포함된 경우의 최대 수익이죠.

 

첫 번째 경우는 아래와 같습니다.

max_profit_so_far = sublist_max([7, -3, 4])

두 번째 경우에는 아래처럼 표현할 수 있고요.

max_check = max(sum([-8]), sum([4, -8]), sum([-3, 4, -8]), sum([7, -3, 4, -8]))

 

힌트2

sublist_max(profits)는 아래 두 값 중 더 큰 값이 됩니다.

 

1. max_profit_so_far = sublist_max([7, -3, 4])

2. max_check = max(sum([-8]), sum([4, -8]), sum([-3, 4, -8]), sum([7, -3, 4, -8]) )

 

이를 코드로 나타내면 아래처럼 표현할 수 있습니다.

max_profit_so_far = max(max_profit_so_far, max_check)

for문을 돌면서 각 요소까지의 max_profit_so_far와 max_check를 효율적으로 구할 수 있는 방법에 대해서 생각해 보세요.

 

 

힌트3

두 정보 모두, 바로 전 부분 문제에서 받아올 수 있는 정보를 이용해서 효율적으로 알아낼 수 있는데요.

 

max_porfit_so_far = sublist_max([7, -3, 4])이 정보는 바로 전 요소 까지의 부분 문제의 답을 그대로 쓰면 되겠죠?

 

max_check도 마찬가지입니다.

 

max_check_1 = max(sum([-8]), sum([4, -8]), sum([-3, 4, -8]), sum([7, -3, 4, -8]))를 하나하나 계산할 필요 없이, 바로 전 부분 문제에서 계산한 max_check_2 = max(sum([4]), sum([-3, 4]), sum([7, -3, 4]))을 구했을 때의 값을 저장해 놓으면, 아래 코드로 구할 수 있습니다.

max_check_1 = max(max_check_2 - 8, -8)

 

 

 

답안

def sublist_max(profits):
    max_profit_so_far = profits[0] # 반복문에서 현재까지의 부분 문제의 답
    max_check = profits[0] # 가장 끝 요소를 포함하는 구간의 최대 합
    
    # 반복문을 통하여 각 요소까지의 최대 수익을 저장한다
    for i in range(1, len(profits)):
        # 새로운 요소를 포함하는 구간의 최대합을 비교를 통해 정한다
        max_check = max(max_check + profits[i], profits[i])
        
        # 최대 구간 합을 비교를 통해 정한다
        max_profit_so_far = max(max_profit_so_far, max_check)
    
    return max_profit_so_far

# 테스트 코드
print(sublist_max([7, -3, 4, -8]))
print(sublist_max([-2, -3, 4, -1, -2, 1, 5, -3, -1]))