투자의 귀재 3가지 방법

실습과제

규식이는 친구들 사이에서 투자의 귀재로 알려져 있습니다. 페이수북과 인수타그램에 자신의 성과를 과시하기 때문인데요. 사실 규식이가 그 정도의 실력자는 아닙니다. 성과가 좋을 때에만 SNS에 공유해서 그렇게 비춰질 뿐이죠.

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

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

함수 설명

우선 함수 sublist_max는 파라미터로 리스트 profits를 받는데요. profits에는 며칠 동안의 수익이 담겨 있습니다. 예를 들어서 profits가 [7, -3, 4, -8]이라면 첫 날에는 7달러를 벌었고, 둘째 날에는 3달러를 잃었고, 셋째 날에는 4달러를 벌었고, 마지막 날에는 8달러를 잃은 거죠.

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

profits가 [7, -3, 4, -8]이라면 무엇을 리턴해야 할까요? profits에서 가장 많은 수익을 낸 구간은 [7, -3, 4]입니다. 이 구간에서 낸 수익은 8달러이니, 8을 리턴하면 되겠죠!

만약 profits가 [-2, -3, 4, -1, -2, 1, 5, -3]이라면? profits에서 수익이 가장 큰 구간은 [4, -1, -2, 1, 5]입니다. 이 구간에서 낸 수익은 7달러이니, 7을 리턴하겠죠?

 

힌트6/6

해설 보기

과제 해설

힌트 1

Brute Force는 가능한 경우를 모두 고려해서 문제의 답을 구하는 방식입니다.

Brute Force로 이 문제를 해결하기 위해서는, 리스트의 가능한 모든 범위를 봐야겠죠?

힌트 2

어떻게 가능한 모든 범위를 볼 수 있을까요? 간단한 예시를 통해서 알아봅시다.

profits가 [7, -3, 4, -8]일 때 가능한 모든 범위를 봅시다.

범위수익현재까지 최대 수익

[7]	77	77
[7, -3]	44	77
[7, -3, 4]	88	88
[7, -3, 4, -8]	00	88
[-3]	-3−3	88
[-3, 4]	11	88
[-3, 4, -8]	-7−7	88
[4]	44	88
[4, -8]	-4−4	88
[-8]	-8−8	88

모든 범위를 살피기 위해 어떻게 했는지 패턴이 보이시나요?

힌트 3

패턴을 분석해 봅시다.

기존 리스트인 [7, -3, 4, -8]의 시작 인덱스와 끝 인덱스를 잘 지켜보세요.

범위시작 인덱스끝 인덱스

[7]	00	00
[7, -3]	00	11
[7, -3, 4]	00	22
[7, -3, 4, -8]	00	33
[-3]	11	11
[-3, 4]	11	22
[-3, 4, -8]	11	33
[4]	22	22
[4, -8]	22	33
[-8]	33	33

이제 패턴이 눈에 띄네요.

이 패턴을 반복문으로 어떻게 구현할 수 있을까요?

힌트 4

시작 인덱스를 i, 끝 인덱스를 j라고 합시다.

i가 00일 때에는 j가 00부터 33, i가 11일 때에는 j가 11부터 33, i가 22일 때에는 j가 22부터 33, i가 33일 때에는 j가 33부터 33입니다.

for i in range(len(profits)): for j in range(i, len(profits)): # ...

반복문의 생김새를 알아냈습니다. 이제 sublist_max 함수를 작성할 수 있으신가요?

힌트 5

우선, 어떤 변수들이 필요할까요?

힌트 6

def sublist_max(profits): max_profit = profits[0] # 최대 수익 for i in range(len(profits)): # 인덱스 i부터 j까지 수익의 합을 보관하는 변수 total = 0 for j in range(i, len(profits)): # 코드를 작성하세요. # return문을 작성하세요.

자, 필요한 변수들을 모두 보여드렸습니다.

참고로 max_profit은 초기 설정으로 첫 번째 인덱스의 수익을 넣었습니다.

그리고 total은 i부터 j까지 수익의 합을 보관하는 변수이기 때문에, 바깥쪽 반복문(for i in range…)의 시작 부분에 매번 total = 0으로 초기화합니다.

이제 나머지 부분을 채워보세요!

해답

def sublist_max(profits):
    max_profit = profits[0] # 최대 수익
    
    for i in range(len(profits)):
        # 인덱스 i부터 j까지 수익의 합을 보관하는 변수
        total = 0
        
        for j in range(i, len(profits)):
            # i부터 j까지 수익의 합을 계산
            total += profits[j]
            
            # i부터 j까지 수익의 합이 최대 수익이라면, max_profit 업데이트
            max_profit = max(max_profit, total)

    return max_profit


# 테스트
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'''

 

 

이번에는 같은 문제를 Divide and Conquer 방식으로 풀어볼 텐데요. 시간 복잡도는 O(n\lg{n})O(nlgn)이 되어야 합니다.

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

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

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

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

 

힌트0/9

해설 보기

과제 해설

힌트 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_crossing_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−1
2. [4, -1] → 수익은 33
3. [-3, 4, -1] → 수익은 00
4. [-2, -3, 4, -1] → 수익은 -2−2

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

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

1. [-2] → 수익은 -2−2
2. [-2, 1] → 수익은 -1−1
3. [-2, 1, 5] → 수익은 44
4. [-2, 1, 5, -3] → 수익은 11

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

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

max_crossing_sum을 코드로 작성해 보세요.

힌트 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 power(x, y):
    if y == 0:
        return 1

    # 계산을 한 번만 하기 위해서 변수에 저장
    subresult = power(x, y // 2)
    
    # 문제를 최대한 똑같은 크기의 문제 두 개로 나눠준다 (짝수, 홀수 경우 따로)
    if y % 2 == 0:
        return subresult * subresult
    else:
        return x * subresult * subresult


# 테스트
print(power(3, 5))
print(power(5, 6))
print(power(7, 9))

243
15625
40353607

시간 복잡도가 어떻게 개선되었을까요?

시간 복잡도
2^82 
8
 을 계산하기 위해서는 몇 번의 함수 호출이 있을까요?

power(2, 8)
power(2, 4)
power(2, 2)
power(2, 1)
그렇다면 3^{32}3 
32
 을 계산하기 위해서는 몇 번의 함수 호출이 있을까요?

power(3, 32)
power(3, 16)
power(3, 8)
power(3, 4)
power(3, 2)
power(3, 1)
y가 8인 경우 4번 호출되고, y가 32인 경우 6번 호출됩니다. 총 \lg{y} + 1lgy+1번의 호출이 있는 거죠.

O(\lg{y} + 1)O(lgy+1)이기 때문에, 이 알고리즘의 시간 복잡도는 O(\lg{y})O(lgy)입니다.

 

 

 

 

Brute Force로 풀었을 때는 시간 복잡도가 O(n^2)O(n2), Divide and Conquer를 사용했을 때는 O(nlgn)O(nlgn)였습니다.

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

과제 설명은 저번 챕터를 참고하세요!

 

힌트0/3

해설 보기

과제 해설

힌트 1

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

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

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

1. 부분 문제 [7, -3, 4]의 최대 수익 (sublist_max([7, -3, 4]))
2. 부분 문제 [7, -3, 4, -8]에서 -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_profit_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]))

8

7
코드는 이렇게 몇 줄이면 충분합니다.

시간 복잡도
이 문제는 인풋 리스트 profits의 길이가 n이라고 했을 때 n에 비례하는 For 문이 하나가 있죠? 그렇기 때문에 총 시간 복잡도는 O(n)O(n)이 됩니다.

Brute Force 방법을 사용했을 때와, Divide and Conquer 방법을 사용했을 때 보다 훨씬 더 시간 복잡도가 좋아졌네요!