투자 귀재 규식이 II

투자귀재규식이II.py

def sublist_max(profits, start, end):
    # 여기에 코드를 작성하세요
    # base case: 범위에 하나의 항목밖에 없으면, 그 항목 리턴
    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)
    
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
    


# 테스트 코드
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))

 

해결과정

 

Divide and Conquer로 문제를 풀기 위해서는 문제를 더 작은 부분 문제로 나누고, 재귀적으로 부분 문제를 해결해야한다.

 

먼저 base case는 start와 end가 같으면 범위에 항목이 하나이면서 리턴해준다.

 

Divide and Conquer 관점으로 본다면,

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

이다. 

test_list = [-2, -3, 4, -1, -2, 1, 5, -3]
sublist_max(test_list, 0, 7)

1. 왼쪽 반에서 가능한 최대 수익: sublist_max(test_list, 0, 3)
2. 오른쪽 반에서 가능한 최대 수익: sublist_max(test_list, 4, 7)
3. -1과 -2를 포함하는 모든 경우 중 최대 수익

이걸 일반화시켜서 코드를 작성하면 시간 복잡도는 O(nlogn)이 된다.