알고리즘: 예제를 풀어보자! (feat. 투자의 귀재 규식이)(Brute force, Divide and conquer)

<투자의 귀재 규식이>

 

규식이는 친구들 사이에서 투자의 귀재로 알려져 있습니다.

페이스북과 인스타그램에 자신의 성과를 과시하기 때문인데요. 사실 규식이가 그 정도의 실력자는 아닙니다. 성과가 좋을 때에만 SNS에 공유해서 그렇게 비춰질 뿐이죠.

계속해서 멋진 모습을 보여주기 위해, 특정 기간 중 수익이 가장 큰 구간을 찾아내는 함수 sublist_max를 작성해 보려고 합니다.

 

우선 함수 sublist_max는 파라미터로 며칠 동안의 수익이 담겨 있습니다.

 

예를 들어서 profits가 [7, -3, 4, -8]이라면 첫 날에는 7달러를 벌었고, 둘째 날에는 3달러를 잃었고, 셋째 날에는 4달러를 벌었고, 마지막 날에는 8달러를 잃은 거죠.

 

 

먼저 이 문제를 Brute Force 방법을 이용해서 이 문제를 한 번 풀어봅시다!

 

 

 

1. Brute Force

 

 

sublist_max 함수는 profits에서 최대 수익을 내는 구간의 수익을 리턴합니다.

 

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



print(sublist_max([4, 3, 8, -2, -5, -3, -5, -3]))
print(sublist_max([2, 3, 1, -1, -2, 5, -1, -1]))
print(sublist_max([7, -3, 14, -8, -5, 6, 8, -5, -4, 10, -1, 8]))

 

15
8
27

 

 

 

2. Divide And Conquer

 

 

 이번에는 같은 문제를 Divide and Conquer 방식으로 풀어보겠습니다. 시간 복잡도는 O(nlgn)이 되어야 합니다.

 

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

 

• profits: 며칠 동안의 수익이 담겨 있는 리스트
• start: 살펴볼 구간의 시작 인덱스
• end: 살펴볼 구간의 끝 인덱스

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

 

def max_crossing_sum(profits, start, end):  # 중간을 지날때 합이 최대가 되는 경우
    
    
    mid = (start + end) // 2
    
    
    left_sum = 0
    left_max = profits[mid]
    
    for i in range(mid, start - 1, -1):  # 중간을 기준으로 해서 left부분의 최대합 찾기
    
        left_sum += profits[i]
        left_max = max(left_max, left_sum)
            
    
    
    right_sum = 0
    right_max = profits[mid + 1]
    
    for i in range(mid + 1, end + 1):   # 중간을 기준으로 해서 right부분의 최대합 찾기
    
        right_sum += profits[i]
        right_max = max(right_max, right_sum)
        
        
        
        
    return right_max + left_max
    


def sublist_max(profits, start, end):
    
    
    if start == end:
        return profits[start]
        
        
    mid = (start + end) // 2
    
    
    left = sublist_max(profits, start, mid)  # 최대합이 좌측에 있을경우
    right = sublist_max(profits, mid + 1, end)  # 최대합이 우측에 있을경우
    crossing = max_crossing_sum(profits, start, end)  # 최대합이 중간을 가로지를 경우
    
    
    
    return max(left, right, crossing)
    
    
    
 
 
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. 시간복잡도 더 단축시키기~

 

이번에는 시간복잡도를 더 단축시켜 보겠습니다. 

 

처음에 Brute Force로 풀었을 때는 시간 복잡도가 O(n^​2​​)

 

Divide and Conquer를 사용했을 때는 O(nlgn)였습니다.

 

이번에는 O(n)으로 한번 더 단축시켜 보겠습니다. 

 

def sublist_max(profits):
   
    
    total = 0
    sum_max = profits[0]
    i = 0
   
   
    for i in range(0, len(profits)):
       
        if total <= total + profits[i] and total < 0:
        
            total = 0
           
           
        total += profits[i]
       
        sum_max = max(sum_max, total)
        
     
     
        
    return sum_max
        

print(sublist_max([7, -3, 4, -8]))
print(sublist_max([-2, -3, 4, -1, -2, 1, 5, -3, -1]))

 

8
7

 

한번씩 풀어보세요^^~

문제 출처: 코드잇(Codeit)