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

실습설명

저번 챕터에서 sublist_max() 함수를 Brute Force 방식으로 작성했습니다. 이번에는 같은 문제를 Divide and Conquer 방식으로 풀어볼 텐데요. 시간 복잡도는 O(n lg n)이 되어야 합니다.

 

이번 sublist_max() 함수는 3개의 파라미터를 받습니다.

- profits : 며칠 동안의 수익이 담겨 있는 리스트

- start : 살펴볼 구간의 시작 인덱스

- end : 살펴볼 구간의 끝 인덱스

 

sublist_max()는 profits의 start부터 end까지 구간에서 가능한 가장 큰 수익을 리턴합니다.

 

합병정렬을 구현할 때 merge_sort() 함수를 깔끔하게 작성하기 위해 추가로 merge() 함수를 작성했던 것 기억 나시나요? 마찬가지로 퀵 정렬을 구현할 때 quicksort() 함수에 추가로 partition()함수를 작성했습니다. 이번에도  sublist_max()함수에 추가로 새로운 함수를 작성하면 도움이 되실 겁니다.

 

힌트1

Divide and Conquer로 문제를 풀기 위해서는 문제를 더 작은 부분 문제로 나누고, 재귀적으로 부분 문제들을 해결해야 하는데요. 재귀적으로 문제를 풀 때에는 늘 base case와 recursive case가 있어야 하죠?

 

그럼 문제를 제대로 파고들기 전에 가장 쉬우 base case부터 봅시다. Base case는 문제가 충분히 작아서 바로 풀 수 있는 경우 인데요. 

 

sublist_max()의 base case는 무엇일까요?

 

힌트2

start와 end가 같으면 범위에 항목이 하나입니다.그러면 그냥 그 항목을 리턴해 주면 되겠죠?

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

 

 

힌트3

이제 Divide and Conquer를 해야 하는데요. Divide and Conquer는 총 세 단계로 나뉘게 됩니다.

1. Divide 주어진 문제를 동일한 형태의 부분 문제로 나눈다.

2. COnquer 각 부분 문제를 해결 한다.

3. Combine 부분 문제의 답을 활용해서 주어진 문제의 답을 얻는다.

 

각 부분을 어떻게 구현해야 답을 구할 수 있을 까요?

 

힌트4

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

 위 예시에서 정답 구간은 어디에 있을 까요?

 

크게 세가지 가능성이 있습니다.

 

1. 정답 구간이 왼쪽 반 어딘가에 있다.

2. 정답 구간이 오른쪽 반 어딘가에 있다.

3. 정답 구간이 중앙을 관통한다. 즉, 왼쪽 반에서 가장 오른쪽에 있는 -1과 오른쪽 반에서 가장 왼쪽에 있는 -2가 포함된다.

 

셋 중 가장 큰 결괏값이 이 문제의 정답이 되겠네요.

 

Divide and Conquer의 관점에서 살펴보면 이렇습니다.

 

1. Divide 구간을 왼쪽 반과 오른쪽 반으로 나눈다.

2. Conquer 왼쪽 반에서 가능한 최대 수익과 오른쪽 반에서 가능한 최대 수익을 각각 계산한다.

3. Combine 왼쪽 반에서 가능한 최대수익, 오른쪽 반에서 가능한 최대수익, 중앙을 관통하면서 가능한 최대 수익을 비교해서 그 중 가장 큰 값을 고른다.

 

힌트5

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를 포함하는 모든 경우 중 최대 수익

 

1번과 2번은 재귀적인 호출로 쉽게 표현이 가능한데. 3번은 어떻게 할 수 있을까요?

 

힌트6

merge_sort()를 돕기 위해 merge()함수를작성하고 quicksort()를 돕기위해 partition()함수를 작성한 것처럼 sublist_max()를 돕기위해 max_corssing_sum() 함수를 작성하겠습니다.

def max_crossing_sum(profits, start, end):
    # 여기에 코드를 작성하세요

max_crossing_sum()은 sublist_max()와 똑같이 파라미터로 profits, start, end를 받습니다. 그리고 중앙을 관통하는 경우 중 가장 큰 수익을 리턴합니다.

 

힌트7

아까와 같은 예시 리스트로 max_crossing_sum()함수를 볼게요.

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

왼쪽 반과 오른쪽 반을 나눠서 따로 살펴봅시다.

왼쪽 반의 일부를 포함시킬 때 가능한 모든 경우입니다.

1. [-1] -> 수익은 -1

2. [4, -1] -> 수익은 3

3. [-3, 4, -1] -> 수익은 0

4. [-2, -3, 4, -1] -> 수익은 -2

 

위의네 경우 중 2번의 수익이 가장 크네요.

이번에는 오른쪽 반의 일부를 포함 시킬때 가능한 모든 경우 입니다.

1. [-2] -> 수익은 -2

2. [-2, 1] -> 수익은 -1

3. [-2, 1, 5] -> 수익은 4

4. [-2, 1, 5, -3] -> 수익은 1

 

위의 네 경우중 3번의 수익이 가장 큽니다.

test_list의 왼쪽 반 일부와 오른쪽 반 일부를 포함하는 경우 중, 가장 큰 수익을 내는 구간은 어디일까요? 3의 수익을 내는 [4, -1]과 4의 수익을 내는 [-2,1,5]를 연결시킨 구간입니다. 이 구간의 총 수익은 3+4의 결과값인 7이기 때문에, max_crossing_sum(test_list, 0, 7)은 7을 리턴합니다.

 

힌트8

def max_crossing_sum(profit, start, end):
    mid = (start + end) // 2     # 중간 인덱스

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

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

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

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

    return left_max + right_max

max_crossing_sum() 함수를 완성했으니, 다시 sublist_max() 함수로 돌아가 봅시다.

 

힌트9

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

힌트5에서 이야기 했듯, 우리는 세 경우를 봐야합니다.

1. 왼쪽 반에서 가능한 최대 수익: sublist_max(test_list, 0,3)

2, 오른쪽 반에서 가능한 최대 수익 : sublist_max(test_list, 4, 7)

3. -1과 -2를 포함하는 모든 경우 중 최대 수익

 

 

답안

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