05. 투자의 귀재, 합 구간이 가장 큰 함수

05. 투자의 귀재, 합 구간이 가장 큰 함수

 

Divide and Conquer 방식 풀이

-풀이 생각 순서

Divide: 구간을 왼쪽 반과 오른쪽 반으로 나눈다.
Conquer: 왼쪽 반에서 가능한 최대 수익과 오른쪽 반에서 가능한 최대 수익을 각각 계산한다.
Combine: 왼쪽 반에서 가능한 최대 수익, 오른쪽 반에서 가능한 최대 수익, 중앙을 관통하면서 가능한 최대 수익을 비교해서 그 중 가장 큰 값을 고른다.

 

풀이 1) Brute Force (시간 복잡도 O(n^2))

def sublist_max(profits, start, end):
    maximum = 0
    for i in range(len(profits)):
        total = 0
        for j in range(i,len(profits)):
            total += profits[j]
            maximum = max(maximum, total)

    return maximum
    
    
# 테스트
list1 = [-2, -3, 4, -1, -2, 1, 5, -3]
print(sublist_max(list1, 0, len(list1) - 1))

list2 = [4, 7, -6, 9, 2, 6, -5, 7, 3, 1, -1, -7, 2]
print(sublist_max(list2, 0, len(list2) - 1))

list3 = [9, -8, 0, -7, 8, -6, -3, -8, 9, 2, 8, 3, -5, 1, -7, -1, 10, -1, -9, -5]
print(sublist_max(list3, 0, len(list3) - 1))

list4 = [-9, -8, -8, 6, -4, 6, -2, -3, -10, -8, -9, -9, 6, 2, 8, -1, -1]
print(sublist_max(list4, 0, len(list4) - 1))

 결과
 7
 28
 22
 16

 

 

 

 

 

풀이 2) Brute Force : 최대 합 구간 출력 해보기

def sublist_max(profits, start, end):
    max_list = []
    maximum = 0
    for i in range(len(profits)):
        total = 0
        temp = []
        for j in range(i,len(profits)):
            total += profits[j]
            temp.append(profits[j])
            if maximum < total:
                maximum = total
                max_list = temp.copy()
    print(sum(max_list))

    return max_list
    
    
# 테스트
list1 = [-2, -3, 4, -1, -2, 1, 5, -3]
print(sublist_max(list1, 0, len(list1) - 1))

list2 = [4, 7, -6, 9, 2, 6, -5, 7, 3, 1, -1, -7, 2]
print(sublist_max(list2, 0, len(list2) - 1))

list3 = [9, -8, 0, -7, 8, -6, -3, -8, 9, 2, 8, 3, -5, 1, -7, -1, 10, -1, -9, -5]
print(sublist_max(list3, 0, len(list3) - 1))

list4 = [-9, -8, -8, 6, -4, 6, -2, -3, -10, -8, -9, -9, 6, 2, 8, -1, -1]
print(sublist_max(list4, 0, len(list4) - 1))

결과
7
[4, -1, -2, 1, 5]

28
[4, 7, -6, 9, 2, 6, -5, 7, 3, 1]

22
[9, 2, 8, 3]

16
[6, 2, 8]

 

 

풀이 3-1) Divide and Conquer : 시간복잡도 O(n lg n)

1. 가운데를 포함한 수익 함수 : max_crossing_sum 을 먼저 작성해준다.
  1) 가운데 왼쪽 profits[half] 을 포함한 최대수익
  2) 가운데 오른쪽 profits[half+1] 을 포함한 최대수익
  3) 두 리스트 합쳐서 return

 

2. sublist_max 함수에서 좌측의 최댓값, 우측의 최댓값

   위에서 만든 가운데 최댓값 모두 구해서

   max 내장 함수로 셋 중의 최댓값을 리턴해준다.

# 먼저 중간값을 포함한 최대 합을 리턴하는 함수를 만든다.
def max_crossing_sum(profits, start, end):
    mid = (start + end) // 2      # 중간 인덱스

    '''
    왼쪽에서의 가장 큰 수익 계산
    인덱스 mid부터 인덱스 0까지 범위를 넓혀가며 최대 수익을 찾는다
    '''
    left_sum = 0                  # 왼쪽 누적 수익
    left_max = profits[mid]       # 왼쪽 최고 수익; 왼쪽 반 중 가장 오른쪽 값으로 초기화

    for i in range(mid, start - 1, -1):
        left_sum += profits[i]
        left_max = max(left_max, left_sum)

    '''
    오른쪽에서의 가장 큰 수익 계산
    인덱스 mid+1부터 인덱스 end까지 범위를 넓혀가며 최대 수익을 찾는다
    '''
    right_sum = 0                 # 오른쪽 누적 수익
    right_max = profits[mid + 1]  # 오른쪽 최고 수익; 오른쪽 반 중 가장 왼쪽 값으로 초기화

    for i in range(mid + 1, end + 1):
        right_sum += profits[i]
        right_max = max(right_max, right_sum)

    return left_max + right_max


def sublist_max(profits, start, end):
    # 범위에 하나의 항목밖에 없으면, 그 항목을 리턴한다
    if start == end:
        return profits[start]

    # 중간 인덱스
    mid = (start + end) // 2

    # 상황별로 최대 수익을 구한다
    max_left = sublist_max(profits, start, mid)
    max_right = sublist_max(profits, mid + 1, end)
    max_cross = max_crossing_sum(profits, start, end)

    # 위 세 경우 중 가장 큰 결괏값을 리턴한다
    return max(max_left, max_right, max_cross)

# 테스트
list1 = [-2, -3, 4, -1, -2, 1, 5, -3]
print(sublist_max(list1, 0, len(list1) - 1))

list2 = [4, 7, -6, 9, 2, 6, -5, 7, 3, 1, -1, -7, 2]
print(sublist_max(list2, 0, len(list2) - 1))

list3 = [9, -8, 0, -7, 8, -6, -3, -8, 9, 2, 8, 3, -5, 1, -7, -1, 10, -1, -9, -5]
print(sublist_max(list3, 0, len(list3) - 1))

list4 = [-9, -8, -8, 6, -4, 6, -2, -3, -10, -8, -9, -9, 6, 2, 8, -1, -1]
print(sublist_max(list4, 0, len(list4) - 1))

# 결과
 7
 28
 22
 16

 

 

 

풀이 3-2) Divide and Conquer : 시간복잡도 O(n) <- 최선의 답

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]))

결과
8
7