https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_profit/
MaxProfit coding task - Learn to Code - Codility
Given a log of stock prices compute the maximum possible earning.
app.codility.com
An array A consisting of N integers is given. It contains daily prices of a stock share for a period of N consecutive days. If a single share was bought on day P and sold on day Q, where 0 ≤ P ≤ Q < N, then the profit of such transaction is equal to A[Q] − A[P], provided that A[Q] ≥ A[P]. Otherwise, the transaction brings loss of A[P] − A[Q].
For example, consider the following array A consisting of six elements such that:
A[0] = 23171 A[1] = 21011 A[2] = 21123 A[3] = 21366 A[4] = 21013 A[5] = 21367
If a share was bought on day 0 and sold on day 2, a loss of 2048 would occur because A[2] − A[0] = 21123 − 23171 = −2048. If a share was bought on day 4 and sold on day 5, a profit of 354 would occur because A[5] − A[4] = 21367 − 21013 = 354. Maximum possible profit was 356. It would occur if a share was bought on day 1 and sold on day 5.
Write a function,
def solution(A)
that, given an array A consisting of N integers containing daily prices of a stock share for a period of N consecutive days, returns the maximum possible profit from one transaction during this period. The function should return 0 if it was impossible to gain any profit.
For example, given array A consisting of six elements such that:
A[0] = 23171 A[1] = 21011 A[2] = 21123 A[3] = 21366 A[4] = 21013 A[5] = 21367
the function should return 356, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..400,000];
- each element of array A is an integer within the range [0..200,000].
이번에도 다른 플랫폼에 있는 문제를 가져와봤다.
주식 가격과 관련된 코드인데, 처음엔 오? 하고 이거 잘만 이용하면 내가 원하던 자동매매 프로그램을 만들 수 있는가..? 했더만 알고보니 이미 나와 있는 주식정보를 가지고 최대의 이윤을 뽑아보라는 것이다.
예측이 아니라, 계산의 영역 ㅎㅎ..
1. Python
보아하니 매수/매도는 각 1회만 되는 거 같고..
코드를 효율적으로 짜라고 했는데, Naive한 방법만 생각이 난다.
def solution(A):
# Implement your solution here
# 매수 / 매도는 각 1회만 가능하다고 가정하는 듯
# Recursive 인가..
#worst case
temp = min(A) - max(A)
#과연 이게 efficient 한 것인가..
for i in range(len(A)):
for j in range(i+1,len(A)):
temp = max(temp,A[j]-A[i])
return temp답도 틀리고, Time Out이 발생해버렸다;;
틀린 답이야 temp의 min 값을 0으로 설정하면 될 거 같긴 한데 Time Out이 관건
def solution(A):
# Implement your solution here
temp = 0
for i in range(len(A)):
for j in range(i+1,len(A)):
if A[j] - A[i] > temp :
temp = A[j] - A[i]
return temp
일단 for문을 2번 겹쳐서 써버리면,
그 안에서 continue 든 break 든 if문이든 어떤 조건을 걸어도 N^2 시간소요가 뜬다. 이건 어쩔 수 없는 부분인듯
그래서 시간을 줄일려면 반복문 실행 횟수 자체를 줄여야 한다.
| 현재 코드는 두 개의 중첩 루프를 사용하여 모든 가능한 구매일과 판매일을 비교하고 최대 수익을 찾는 방식으로, 시간 복잡도가 O(n2)O(n^2)이어서 비효율적입니다. 이 문제는 Kadane's algorithm을 응용한 방법으로 해결할 수 있으며, 시간 복잡도를 O(n)O(n)으로 줄일 수 있습니다. 다음은 효율적인 방법을 설명하고 코드로 작성한 예시입니다. 효율적인 접근법
|
Idea 싸움이었다. 위 문제를 for문 1회 사용으로 풀 수 있다니..!
def solution(A):
# Implement your solution here
if not A : return 0
profit = 0
min_val = A[0]
for x in A :
profit = max(profit,x-min_val)
min_val = min(min_val,x)
return profitTime이 O(N)으로 깔끔하게 떨어진다.
2. C++
C++도 동일하게 처리해버리기
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<vector>
using namespace std;
int solution(vector<int> &A) {
// Implement your solution here
if(A.empty()) return 0;
int profit = 0;
int temp_min = A[0];
for(const int x : A){
profit = max(profit,x-temp_min);
temp_min = min(temp_min,x);
}
return profit;
}
3. C
C도 뭐.. 비슷한 맥락이다.
요런 찬라의 아이디어가 코드 퀄리티를 좌우한다.
좀 더 집중하고, 좀 더 경험해보자
#include <stdio.h>
int solution(int A[], int N) {
if (N < 2) return 0;
int min_price = A[0];
int max_profit = 0;
for (int i = 1; i < N; i++) {
// 최대 이익 갱신
if (A[i] - min_price > max_profit) {
max_profit = A[i] - min_price;
}
// 최소 가격 갱신
if (A[i] < min_price) {
min_price = A[i];
}
}
return max_profit;
}
int main() {
int A[] = {23171, 21011, 21123, 21366, 21013, 21367};
int N = sizeof(A) / sizeof(A[0]);
printf("Max Profit: %d\n", solution(A, N));
return 0;
}