[알고리즘] 이번주 알고리즘 문제 풀기

[SongGwanSeok]

📝 Description

무엇을?

• 알고리즘 문제 풀기

왜?

• 알고리즘 공부

❗️Todo

ETC

기타사항

[SongGwanSeok]

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/

[SongGwanSeok]

재귀를 수행하며 vector를 넘겨주는 풀이 : 시간초과

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int profit = 0;
    for(int i = 0; i < prices.size(); i++){
        int buy = prices[i];
        for(int j = i + 1; j < prices.size(); j++){
            int sell = prices[j];
            int now = sell - buy - fee;
            if(now > 0){
                vector<int> next_prices = vector<int>(prices.begin() + (j+1), prices.end());
                profit = max(profit, now + maxProfit(next_prices, fee));
            }
        }
    }
    return profit;
    }
};

[SongGwanSeok]

답은 나오는데 IDE에서도 엄청 오래걸린다. -> 2차원 vector를 만들면 50000 * 50000 터져버리는 듯?

#include<bits/stdc++.h>
using namespace std;

void fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
}

vector<vector<int>> dp(50001, vector<int>(50001));

// [1, 3, 2, 8, 4, 9]
// [0, 0, 0, 0, 5, 1, 6]

void calculateDp(vector<int>& prices, int fee){
    for(int buyIdx = 1; buyIdx <= prices.size(); buyIdx++){
        int buy = prices[buyIdx-1];
        for(int sellIdx = buyIdx+1; sellIdx <= prices.size(); sellIdx++){
            int sell = prices[sellIdx-1];
            int now = sell - buy - fee;
            if(now <= 0) continue;
            dp[buyIdx][sellIdx] = now;
        }
    }
}

int calculateProfit(int n){
    int profit = 0;
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            int max_before = 0;
            for(int k = 1; k < j; k++){
                if(max_before < dp[k][i-1]){
                    max_before = dp[k][i-1];
                }
            }
            profit = max(profit, dp[i][j] + max_before);
        }
    }
    return profit;
}

int maxProfit(vector<int>& prices, int fee) {
    calculateDp(prices, fee);

//    for(int i = 0; i <= prices.size(); i++){
//        for(int j = 0; j <= prices.size(); j++){
//            cout << dp[i][j] << ' ';
//        }
//        cout << '\n';
//    }

    return calculateProfit(prices.size());
}

int main() {
    fast();

    vector<int> prices = {1,3,2,8,4,9};
    int fee = 2;
    int result = maxProfit(prices, fee);

    cout << result;
}

[SongGwanSeok]

시간초과 미치곘네 n^3으로 절대 안풀릴듯; 더 시간을 낮출 방법 찾아...

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {

        vector<int> dp(prices.size() + 1);

        for(int buyIdx = 1; buyIdx <= prices.size(); buyIdx++){
            int buyPrice = prices[buyIdx-1];

            for(int sellIdx = buyIdx + 1; sellIdx <= prices.size(); sellIdx++){
                int sellPrice = prices[sellIdx-1];
                int price = sellPrice - buyPrice - fee;

                if(price <= 0) continue;
                int max_before = 0;
                for(int i = 0; i < buyIdx; i++){
                    max_before = max(max_before,dp[buyIdx-i]); 
                }
                dp[sellIdx] = max(dp[sellIdx], max_before + price);
            }

        }

        return *max_element(dp.begin(), dp.end());
    }
};