[알고리즘 일기] 33. 투자 귀재 규식이 1

문제 33. (2021-06-02)

투자 귀재 규식이 1

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

❧ 테스트 셋

def sublist_max(profits):
    #Code

#Test
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

---

❧ 정답

def sublist_max(profits):
    # 초기값 설정을 위해 임의로 인덱스 0의 값을 할당함
    max_profit = profits[0]
    # 최대 범위 인덱스 값 증가
    for i in range(len(profits) + 1):
        # 최소 범위 인덱스 값 증가
        for j in range(len(profits) + 1):
            if max_profit < sum(profits[i:j]):
                max_profit = sum(profits[i:j])
    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]))

1️⃣ Brute-Force 방식 사용

2️⃣ 중첩 for 문 사용으로 시간 복잡도 O(n2)

3️⃣ sum 내장 함수 사용으로 소요 시간 단축