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

실습설명

규식이는 친구들 사이에서 투자의 귀재로 알려져 있습니다. 페이수북과 인수타그램에 자신의 성과를 과시하기 때문인데요. 사실 규식이가 그정도의 실력자는 아닙니다. 성과가 좋을 때에만 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을 리턴하겠죠?

 

 

 

힌트1

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

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

 

힌트2

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

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

 

[7]	7	7
[7, -3]	4	7
[7, -3, 4]	8	88
[7, -3, 4, -8]	0	8
[-3]	−3	8
[-3, 4]	1	8
[-3, 4, -8]	−7	8
[4]	4	8
[4, -8]	−4	8
[-8]	−8	8

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

 

힌트3

패턴을 분석해 봅시다.

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

 

[7]	0	0
[7, -3]	0	1
[7, -3, 4]	0	2
[7, -3, 4, -8]	0	3
[-3]	1	1
[-3, 4]	1	2
[-3, 4, -8]	1	3
[4]	2	2
[4, -8]	2	3
[-8]	3	3

이제 패턴이 눈에 띄네요.

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

 

힌트4

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

i가 0일때에는 j가 0부터3, i가 1일 때에는 j가 1부터 3, i가 2일때에는 j가 2부터 3, i가 3일때에는 j가 3부터 3입니다.

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까지 수익의 합을 보관하는 변수이기 떄문에, 바깥쪽 반복문의 시작부분에 매번 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]))