[ALGORITHMS]문제 18 최대 수익 알고리즘

문제 18

최대 수익 알고리즘

어떤 주식에 대해 특정 기간 동안의 가격 변화가 주어졌을 때, 그 주식 한 주를 한번 사고 팔아 얻을 수 있는 최대 수익을 계산하는 알고리즘을 만들어 보세요

이번 문제는 주식을 거래해서 얻을 수 있는 최대 수익(이익)을 구하는 문제입니다. 최대 수익을 계산하는 단순한 상황이므로 주식을 잘 모르는 사람도 어렵지 않게 이해할 수 있을것입니다.

어떤 주식의 가격이 밑에 표와 같이 매일 변했다고 합니다

이 주식 한 주를 한 번 사고 팔아 얻을 수 있는 최대 수익은 얼마일까요? 단, 손해가 나면 주식을 사고팔지 않아도 됩니다. 따라서 최대 수익은 항상 0 이상의 값입니다.

1. 문제 분석과 모델링

주식 거래로 수익을 내는 가장 좋은 방법은 '가장 쌀 때 사서 가장 비쌀 때 파는 것'입니다. 얼핏 생각하면 주가의 최댓값에서 주가의 최솟값을 뺀 것으로 착각하기 쉽습니다.

하지만 위의 표를 예를 들면, 6월 1일의 주가 10,300원이 최댓값이고 6월 5일 주가 7,800원이 최솟값입니다. 하지만 아직 사지도 않은 주식을 6월 1일에 먼저 팔고 6월 5일에 주식을 살 수 없으므로 단순히 최댓값과 최솟값의 차이로 구하는 것은 올바른 답이 아닙니다

2. 방법 1: 가능한 모든 경우를 비교하기

일단 생각할 수 있는 가장 간단한 방법은 주식을 살 수 있는 모든 날과 팔 수 있는 모든 날의 주가를 비교해서 가장 큰 수익을 찾는 것입니다.

예를 들어 첫째 날 10,300원에 주식을 샀다면 둘째 날부터의 주식 가격인 9,600원, 9 ,800원, ... 9,500원 중 하나로 주식을 팔 기회가 생깁니다.

마찬가지로 둘째날 9,600원에 주식을 샀다면 셋째 날부터의 주식 가격인 9,800원, 8,200원,... 9,500원 중 하나로 주식을 팔 기회가 생깁니다

이런 식으로 모든 경우를 비교해서 가장 큰 이익을 내는 경우를 찾으면 원하는 최대 수익을 계산할 수 있습니다. 

문제 3 동명이인 찾기에서 가능한 모든 사람을 비교하던 방식과 똑같다는 것을 아실겁니다

* 최대 수익을 구하는 알고리즘 1

3. 방법 2: 한 번 반복으로 최대 수익 찾기

모든 경우를 비교하는 위의 방법은 간단하고 직관적이지만, 불필요한 비교를 너무 많이 하는 단점이 있습니다.

위의 알고리즘이 사는 날을 중심으로 생각한 것이라면 이번에는 파는 날을 중심으로 생각을 바꿔보겠습니다. 예를 들어 6월 10일에 9,800원을 받고 주식을 팔았다고 가정해 봅시다. 이 때 얻을 수 있는 최고 수익은 6월 10일 이전에 가장 주가가 낮았던 날인 6월 5일에 7,800원에 산 경우이므로 2000원입니다. 만약 6월 11일에 10,200원에 팔았다면, 6월 5일 7,800원과의 차이인 2,400원이 최대 수익입니다.

즉, 파는 날을 기준으로 이전 날들의 주가 중 최솟값만 알면 최대 수익을 쉽게 계산할 수 있습니다. 이 아이디어를 조금 더 체계젹으로 적어보면 다음과 같습니다

1. 최대 수익을 저장하는 변수를 만들고 0을 저장합니다

2. 지금까지의 최저 주가를 저장하는 변수를 만들고 첫째 날의 주가를 기록합니다.

3. 둘째 날의 주가부터 마지막 날의 주가까지 반복합니다.

4. 반복하는 동안 그날의 주가에서 최저 주가를 뺀 값이 현재 최대 수익보다 크면 최대 수익 값을 그 값으로 고칩니다.

5. 그날의 주가가 최저 주가보다 낮으면 최저 주가 값을 그날의 주가로 고칩니다

6. 처리 할 날이 남았으면 4번 과정으로 돌아가 반복하고, 다 마쳤으면 최대 수익에 저장 된 값을 결과값으로 돌려주고 종료합니다.

* 최대 수익을 구하는 알고리즘 2

4. 알고리즘 분석

첫 번째 알고리즘보다 두 번째 알고리즘이 더 효율적이라는 것을 알 수 있습니다.

모든 경우를 비교한 첫번째 알고리즘은 모든 이름을 일일이 비교하면서 찾는 방식으로 계산 복잡도는 O(n^2)입니다.

반면, 리스트를 한 번 탐색하면서 최대 수익을 계산한 두 번째 알고리즘은 계산복잡도는 O(n)입니다.

읽어주셔서 감사합니다