중요한건 꺾이지 않는 마음 이라고 하지만 Hard 문제 앞에서는 거의 항상 좌절하는것 같습니다.
아직 갈 길이 멀다는 뜻이겠지요.
이번 문제는 처음 dp 문제를 잘못 정의해서 고생만 하다 결국 풀지 못하고 chatGPT 의 도움을 받았습니다.
처음 정의했던 dp 문제는 아래와 같았습니다.
dp[i][j] => i번째 day 에서 시작해서 j day 까지 얻을 수 있는 max profit
이렇게 해서 두 파트로 나눠서 두번 구매하는 경우와 한번 구매했을 경우의 max 를 구해서 값을 구하려고 했으나,
제가 문제 정의에서 최대 2번 구매가능한 조건을 반영하지 않아서 실제 코드로도 가능한 최대한 구매할 때 얻을 수 있는 max profit 값이 나와버렸습니다.
(DP 문제에서는 문제 정의가 이렇게 중요합니다)
잘못 정의된 문제로 억지로 2번만 구매하도록 구현했으나 O(N^2) 의 시간복잡도를 가진 알고리즘으로 time out 이 발생합니다. ( 10^5^2 , 보통 1억보다 클 경우 TLE)
1 <= prices.length <= 105
O(N^2) 보다 좋은 알고리즘을 찾아야하는데 아무리 고민해봐도 새로운 접근법이 떠오르지 않아 리트코드의 solution 과 ChatGPT 의 도움을 받았습니다.
문제 자체를 구매는 (-) 판매는 (+) 로 이해하고 시작합니다.
크게 2가지 접근법으로 정리 될 것 같습니다.
- state machine 을 이용한 방법
- k th transaction 을 따로 관리해서 dp 푸는 방법
1번의 경우 정말 아름답고 너무 깔끔한 코드지만 제가 다시 이 문제를 푼다고 해도 다시 생각할 수 없을 알고리즘인것 같아 참고만 하였습니다.
개인적으로는 아래 discussion 이 가장 잘 정리된것 같습니다.
2번째 접근법(k th transaction) 은 리트코드 discussion 에 마음에 드는 접근법이 없어 chatGPT 에게 물어봤습니다.
아래와 같은 아름다운 코드를 만들어주는데 바로 이해하기가 힘들어 조금 나눠 생각해보았습니다.
위의 접근법에서 dp 문제는 아래와 같이 정의됩니다.
dp[i][k] => 최대 k 번의 transaction 을 실행했을때 i 번째 day 에서의 max profit
그리고 이 문제를 dp문제(작은 문제들을 사용해서 큰 문제를 푸는 접근법)로 만들어주는 변수가 max_diff 입니다.
max_diff => k-1 번째의 transaction 을 실행했을때 i 번째 day 까지 얻을 수 있는 max profit 에 현재의 stock 을 구매한 값
이익을 최대화 하면서도 가장 저렴한 stock 을 구매한 값이 max_diff 입니다.
그럼 dp[i][k] 는 아무것도 사지 않거나( dp[i-1][k] ) 1회 transaction 이 수행되고 stock을 구매한 상태의 값을 현재 가격에 파는 ( prices[i] + max_diff ) 것 중 max 가 최대 profit 입니다.
dp[i][k] = max( dp[i-1][k] , prices[i] + max_diff )
ChatGPT 의 코드를 그대로 사용했지만 그래도 제가 이해한 순서대로 코드는 조금 나눠보았습니다.
문제를 구매는 (-) 판매는 (+) 로 생각하는것과 transaction 단위로 dp 적으로 생각하는 부분이 부족했던것 같습니다.
특히 dp 문제는 생각의 한계를 넘는 노력이 많이 필요할것 같습니다.