koenjazh-CNfresde
짬뽕얼큰하게의 맨땅에 헤딩 :: '알고리즘' 카테고리의 글 목록 (7 Page)

Minimum Cost For Tickets

알고리즘 2025. 3. 3. 09:00

Leetcode Problem:

Summary

  • The problem is to find the minimum cost of traveling a list of days given the costs of 1-day, 7-day, and 30-day passes.

Approach

  • Dynamic programming is used to solve this problem
  • The idea is to create a dp array where dp[i] represents the minimum cost to reach day i
  • The dp array is initialized with zeros and then filled up in a bottom-up manner
  • For each day, if the day is less than the current day in the days array, the cost is the same as the previous day
  • Otherwise, the cost is the minimum of the cost of buying a 1-day pass, a 7-day pass, and a 30-day pass for the current day.

Complexity

  • O(n) where n is the number of days.

Explanation

  • The dynamic programming approach is used to solve this problem efficiently
  • The dp array is filled up in a bottom-up manner, starting from day 1
  • For each day, if the day is less than the current day in the days array, the cost is the same as the previous day
  • Otherwise, the cost is the minimum of the cost of buying a 1-day pass, a 7-day pass, and a 30-day pass for the current day
  • This approach avoids the need to calculate the cost for each day multiple times, making it more efficient.

Solution Code:


class Solution {
public:
    int mincostTickets(vector& days, vector& costs) {
        int lastDay = days[days.size() - 1];
        vector dp(lastDay + 1, 0);
        
        int i = 0;
        for (int day = 1; day <= lastDay; day++) {
            if (day < days[i]) {
                dp[day] = dp[day - 1];
            } else {
                i++;
                dp[day] = min({dp[day - 1] + costs[0],
                               dp[max(0, day - 7)] + costs[1],
                               dp[max(0, day - 30)] + costs[2]});
            }
        }
     
        return dp[lastDay];
    }
};

'알고리즘' 카테고리의 다른 글

Number of Ways to Split Array  (0) 2025.03.03
Count Vowel Strings in Ranges  (0) 2025.03.03
Count Ways To Build Good Strings  (0) 2025.03.03
Number of Ways to Form a Target String Given a Dictionary  (0) 2025.03.03
Maximum Sum of 3 Non-Overlapping Subarrays  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Count Ways To Build Good Strings

알고리즘 2025. 3. 3. 08:57

Leetcode Problem:

Summary

  • Find the number of different good strings that can be constructed satisfying the given properties.

Approach

  • This problem can be solved using dynamic programming
  • We use a memoization table to store the results of subproblems and avoid redundant computation.

Complexity

  • O(n * zero * one), where n is the range of possible lengths (high - low + 1)

Explanation

  • The `getCnt` function calculates the number of good strings of a given length that can be constructed using the given number of zeros and ones
  • It uses memoization to store the results of subproblems and avoid redundant computation
  • The `countGoodStrings` function iterates over the range of possible lengths and calls `getCnt` to calculate the total number of good strings
  • The result is then taken modulo 10^9 + 7 to avoid overflow.

Solution Code:


#define MOD 1000000007
class Solution {
public:
    int memo[100001];
    long long getCnt(int length, int zero, int one){
        if(length < 0) return 0;
        if(length == 0){
            return 1;
        }
        if(memo[length] != -1) return memo[length];
        long long ret = 0;
        ret += getCnt(length - zero, zero, one);
        ret %= MOD;
        ret += getCnt(length - one , zero, one);
        ret %= MOD;
        return memo[length] = ret;
    }
    int countGoodStrings(int low, int high, int zero, int one) {
        memset(memo, -1, sizeof(memo));
        long long ans = 0;
        for(int i = low; i <= high; i++){
            ans += getCnt(i, zero, one);
            ans %= MOD;
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Count Vowel Strings in Ranges  (0) 2025.03.03
Minimum Cost For Tickets  (0) 2025.03.03
Number of Ways to Form a Target String Given a Dictionary  (0) 2025.03.03
Maximum Sum of 3 Non-Overlapping Subarrays  (0) 2025.03.03
Best Sightseeing Pair  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Number of Ways to Form a Target String Given a Dictionary

알고리즘 2025. 3. 3. 08:54

Leetcode Problem:

Summary

  • This is a problem of forming a target string using given words with certain restrictions.

Approach

  • Dynamic programming is used to solve this problem
  • The approach involves creating a dictionary to store the frequency of each character in each word and a memoization table to store the intermediate results.

Complexity

  • O(n*m*d) where n is the length of the target string, m is the number of words, and d is the number of unique characters in the words.

Explanation

  • The solution starts by initializing a dictionary to store the frequency of each character in each word and a memoization table to store the intermediate results
  • It then iterates over each word and character in the target string, using the dictionary to get the frequency of the current character and the memoization table to store the intermediate results
  • The final result is obtained by summing up the number of ways to form the target string using each word and character.

Solution Code:


class Solution {
public:
    int dict[1001][128];
    int memo[1001][1001];
    int dictN;
    long long getCnt(string& target, int targetIdx, int dictIdx){
        if(target.size() == targetIdx) return 1;
        if(dictIdx >= dictN) return 0;
        if(memo[dictIdx][targetIdx] != -1) return memo[dictIdx][targetIdx];
        long long ret = 0;
        for(int i = dictIdx; i < dictN - (target.size() - targetIdx - 1); i++){
            if(dict[i][target[targetIdx]] == 0) continue;
            ret += getCnt(target, targetIdx+1, i + 1) * dict[i][target[targetIdx]] % 1000000007;
            ret %= 1000000007;
        }
        return memo[dictIdx][targetIdx] = ret;
    }
    int numWays(vector& words, string target) {
        dictN = words[0].size();
        memset(memo, -1, sizeof(memo));
        if(dictN < target.size()) return 0;
        for(int i = 0 ; i < words.size(); i++){
            for(int j = 0 ; j < dictN; j++){
                dict[j][words[i][j]]++;
            }
        }
        return getCnt(target, 0, 0);
    }
};

'알고리즘' 카테고리의 다른 글

Minimum Cost For Tickets  (0) 2025.03.03
Count Ways To Build Good Strings  (0) 2025.03.03
Maximum Sum of 3 Non-Overlapping Subarrays  (0) 2025.03.03
Best Sightseeing Pair  (0) 2025.03.03
Target Sum  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Maximum Sum of 3 Non-Overlapping Subarrays

알고리즘 2025. 3. 3. 08:50

Leetcode Problem:

Summary

  • Given an integer array and an integer k, find three non-overlapping subarrays of length k with maximum sum and return their starting indices.

Approach

  • Dynamic programming and depth-first search are used to find the maximum possible sum of subarrays and then reconstruct the path to find the starting indices.

Complexity

  • O(n * 4^k) where n is the size of the input array, as the dynamic programming function is called for each possible subarray and for each possible number of subarrays remaining.

Explanation

  • The solution first calculates the sum of all possible k-length subarrays using a sliding window approach
  • Then, it uses dynamic programming to find the maximum possible sum of subarrays
  • The dynamic programming function tries taking the current subarray vs skipping it and returns the maximum result
  • Finally, the solution uses depth-first search to reconstruct the path to find the starting indices of the subarrays.

Solution Code:


class Solution {
public:
    vector maxSumOfThreeSubarrays(vector& nums, int k) {
        // Number of possible subarray starting positions
        int n = nums.size() - k + 1;

        // Calculate sum of all possible k-length subarrays
        vector sums(n);
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }
        sums[0] = windowSum;

        // Sliding window to calculate remaining sums
        for (int i = k; i < nums.size(); i++) {
            windowSum = windowSum - nums[i - k] + nums[i];
            sums[i - k + 1] = windowSum;
        }

        // memo[i][j]: max sum possible starting from index i with j subarrays
        // remaining
        vector> memo(n, vector(4, -1));
        vector indices;

        // First find optimal sum using DP
        dp(sums, k, 0, 3, memo);

        // Then reconstruct the path to find indices
        dfs(sums, k, 0, 3, memo, indices);

        return indices;
    }

private:
    // DP function to find maximum possible sum
    int dp(vector& sums, int k, int idx, int rem,
           vector>& memo) {
        if (rem == 0) return 0;
        if (idx >= sums.size()) {
            return rem > 0 ? INT_MIN : 0;
        }

        if (memo[idx][rem] != -1) {
            return memo[idx][rem];
        }

        // Try taking current subarray vs skipping it
        int withCurrent = sums[idx] + dp(sums, k, idx + k, rem - 1, memo);
        int skipCurrent = dp(sums, k, idx + 1, rem, memo);

        memo[idx][rem] = max(withCurrent, skipCurrent);
        return memo[idx][rem];
    }

    // DFS to reconstruct the solution path
    void dfs(vector& sums, int k, int idx, int rem,
             vector>& memo, vector& indices) {
        if (rem == 0) return;
        if (idx >= sums.size()) return;

        int withCurrent = sums[idx] + dp(sums, k, idx + k, rem - 1, memo);
        int skipCurrent = dp(sums, k, idx + 1, rem, memo);

        // Choose path that gave optimal result in DP
        if (withCurrent >= skipCurrent) {  // Take current subarray
            indices.push_back(idx);
            dfs(sums, k, idx + k, rem - 1, memo, indices);
        } else {  // Skip current subarray
            dfs(sums, k, idx + 1, rem, memo, indices);
        }
    }
};

'알고리즘' 카테고리의 다른 글

Count Ways To Build Good Strings  (0) 2025.03.03
Number of Ways to Form a Target String Given a Dictionary  (0) 2025.03.03
Best Sightseeing Pair  (0) 2025.03.03
Target Sum  (0) 2025.03.03
Find Largest Value in Each Tree Row  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Best Sightseeing Pair

알고리즘 2025. 3. 3. 08:46

Leetcode Problem:

Summary

  • Given an array of sightseeing spot values, find the maximum score of a pair of sightseeing spots.

Approach

  • This problem can be solved using dynamic programming
  • We maintain two arrays: maxLeftScore and maxRightScore
  • maxLeftScore[i] represents the maximum score of a sightseeing spot at index i from the left, and maxRightScore[i] represents the maximum score of a sightseeing spot at index i from the right
  • We update these arrays iteratively, and the maximum score is the maximum of the sum of maxLeftScore[i-1] and maxRightScore[i], or maxLeftScore[i-1] plus the current right score.

Complexity

  • O(n)

Explanation

  • The time complexity is O(n) because we are iterating through the array once
  • The space complexity is O(n) because we are storing the maximum left and right scores for each index.

Solution Code:


class Solution {
public:
    int maxScoreSightseeingPair(vector& values) {
        int n = values.size();
        // Initialize an array to store the maximum left scores up to each
        // index.
        vector maxLeftScore(n);
        // The left score at the first index is just the value of the first
        // element.
        maxLeftScore[0] = values[0];

        int maxScore = 0;

        for (int i = 1; i < n; i++) {
            int currentRightScore = values[i] - i;
            // Update the maximum score by combining the best left score so far
            // with the current right score.
            maxScore = max(maxScore, maxLeftScore[i - 1] + currentRightScore);

            int currentLeftScore = values[i] + i;
            // Update the maximum left score up to the current index.
            maxLeftScore[i] = max(maxLeftScore[i - 1], currentLeftScore);
        }

        return maxScore;
    }
};

'알고리즘' 카테고리의 다른 글

Number of Ways to Form a Target String Given a Dictionary  (0) 2025.03.03
Maximum Sum of 3 Non-Overlapping Subarrays  (0) 2025.03.03
Target Sum  (0) 2025.03.03
Find Largest Value in Each Tree Row  (0) 2025.03.03
Minimum Number of Operations to Sort a Binary Tree by Level  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Target Sum

알고리즘 2025. 3. 3. 08:43

Leetcode Problem:

Summary

  • Find the number of different expressions that can be built from the given integer array and target sum.

Approach

  • Dynamic programming with memoization
  • The function recursively tries all possible combinations of '+' and '-' operations before the current number and stores the results in a memoization table to avoid redundant calculations.

Complexity

  • O(n * sum), where n is the length of the input array and sum is the target sum.

Explanation

  • The solution uses a recursive function with memoization to try all possible combinations of '+' and '-' operations before the current number
  • The memoization table stores the results of subproblems to avoid redundant calculations
  • The base cases are when the current index is 0 (no more numbers to process) or when the sum equals the target
  • The function returns 1 if the sum equals the target and 0 otherwise
  • The results are stored in the memoization table and returned.

Solution Code:


class Solution {
public:
    int memo[20][2001];
    int findTargetSumWays(vector& nums, int target, int cur=0, int sum=0) {
        if(cur == 0){
            memset(memo, -1, sizeof(memo));
        }
        if(cur == nums.size()){
            if (sum == target){
                return 1;
            }
            return 0;
        }
        if(memo[cur][sum+1000] != -1) return memo[cur][sum+1000];
        int res = 0;
        res += findTargetSumWays(nums, target, cur+1, sum + nums[cur]);
        res += findTargetSumWays(nums, target, cur+1, sum - nums[cur]);
        return memo[cur][sum+1000] = res;
    }
};

'알고리즘' 카테고리의 다른 글

Maximum Sum of 3 Non-Overlapping Subarrays  (0) 2025.03.03
Best Sightseeing Pair  (0) 2025.03.03
Find Largest Value in Each Tree Row  (0) 2025.03.03
Minimum Number of Operations to Sort a Binary Tree by Level  (0) 2025.03.03
Merge Two 2D Arrays by Summing Values  (0) 2025.03.02
블로그 이미지

짬뽕얼큰하게

,

Find Largest Value in Each Tree Row

알고리즘 2025. 3. 3. 08:40

Leetcode Problem:

Summary

  • Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Approach

  • The solution uses a level order traversal (BFS) approach with a depth-first traversal (DFS) to find the largest value in each row
  • It uses a queue to store the nodes at each level and a vector to store the largest values.

Complexity

  • O(n), where n is the number of nodes in the tree
  • Each node is visited once.

Explanation

  • The solution starts by initializing a vector to store the largest values and a queue to store the nodes at each level
  • It then performs a level order traversal of the tree using a BFS approach
  • At each level, it finds the maximum value and stores it in the vector
  • The traversal is done using a DFS approach by recursively visiting the left and right children of each node
  • The time complexity is O(n) because each node is visited once, and the space complexity is O(n) because the queue stores the nodes at each level.

Solution Code:


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector ans;
    void traversal(TreeNode* root, int depth){
        if(root == nullptr) return;
        if(ans.size() == depth){
            ans.push_back(root->val);
        } else{
            ans[depth] = max(ans[depth], root->val);
        }
        traversal(root->left, depth + 1);
        traversal(root->right, depth + 1);
    }
    vector largestValues(TreeNode* root) {
        traversal(root, 0);
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Best Sightseeing Pair  (0) 2025.03.03
Target Sum  (0) 2025.03.03
Minimum Number of Operations to Sort a Binary Tree by Level  (0) 2025.03.03
Merge Two 2D Arrays by Summing Values  (0) 2025.03.02
Apply Operations to an Array  (0) 2025.03.01
블로그 이미지

짬뽕얼큰하게

,

Minimum Number of Operations to Sort a Binary Tree by Level

알고리즘 2025. 3. 3. 08:37

Leetcode Problem:

Summary

  • This is a solution for the problem of finding the minimum number of operations needed to make the values at each level of a binary tree strictly increasing.

Approach

  • This solution uses a level-order traversal to store the node values at each level in a vector
  • Then it sorts the node values at each level and checks for any swaps needed to make the values strictly increasing
  • The solution keeps track of the number of swaps needed and returns the total number of swaps as the minimum number of operations.

Complexity

  • O(n log n) where n is the number of nodes in the tree, due to the sorting operation at each level.

Explanation

  • The solution first performs a level-order traversal of the tree and stores the node values at each level in a vector
  • Then it sorts the node values at each level and checks for any swaps needed to make the values strictly increasing
  • The solution keeps track of the number of swaps needed and returns the total number of swaps as the minimum number of operations.

Solution Code:


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector equalLevelNode[100001];
    void traversal(TreeNode* root, int level){
        if(root == nullptr) return;
        equalLevelNode[level].push_back(root->val);
        traversal(root->left, level + 1);
        traversal(root->right, level + 1);
    }
    int minimumOperations(TreeNode* root) {
        traversal(root, 0);
        int ans = 0;
        for(int i = 0 ; i <= 100000; i++){
            if(equalLevelNode[i].size() == 0) break;
            unordered_map m;
            vector sorted;
            for(int j = 0 ; j < equalLevelNode[i].size(); j++){
                sorted.push_back(j);
            }
            sort(sorted.begin(), sorted.end(), [&](int a, int b){
                return equalLevelNode[i][a] < equalLevelNode[i][b];
            });
            for(int j = 0; j < sorted.size(); j++){
                m[sorted[j]] = j;
            }
            for(int j = 0; j < sorted.size(); j++){
                if(equalLevelNode[i][sorted[j]] != equalLevelNode[i][j]){
                    ans++;
                    int t = equalLevelNode[i][sorted[j]];
                    equalLevelNode[i][sorted[j]] = equalLevelNode[i][j];
                    equalLevelNode[i][j] = t;

                    sorted[m[j]] = sorted[j];
                    m[sorted[j]] = m[j];
                }
            }
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Target Sum  (0) 2025.03.03
Find Largest Value in Each Tree Row  (0) 2025.03.03
Merge Two 2D Arrays by Summing Values  (0) 2025.03.02
Apply Operations to an Array  (0) 2025.03.01
Maximum Number of K-Divisible Components  (0) 2025.03.01
블로그 이미지

짬뽕얼큰하게

,

Merge Two 2D Arrays by Summing Values

알고리즘 2025. 3. 2. 09:19

Leetcode Problem:

Summary

  • Merge two sorted arrays of integers with unique ids, into one array sorted by id, respecting the conditions that only ids appearing in at least one array should be included and each id should be included only once with its value being the sum of the values of this id in the two arrays.

Approach

  • The approach used is to first create a map where the keys are the ids and the values are the sums of the values of each id in the two arrays
  • Then, we create a vector of vectors and iterate over the map, pushing back a vector for each key-value pair into the vector.

Complexity

  • O(n + m) where n and m are the sizes of the two input arrays, because we are iterating over each element in both arrays once.

Explanation

  • The solution starts by creating a map where the keys are the ids and the values are the sums of the values of each id in the two arrays
  • This is done by iterating over the first array and adding the value of each id to the corresponding key in the map
  • Then, we do the same for the second array
  • After that, we create a vector of vectors and iterate over the map, pushing back a vector for each key-value pair into the vector
  • This results in a vector of vectors where each inner vector contains an id and its corresponding sum, sorted by id in ascending order.

Solution Code:


class Solution {
public:
    vector> mergeArrays(vector>& nums1, vector>& nums2) {
        map m;
        for(int i = 0 ; i < nums1.size(); i++){
            int id = nums1[i][0];
            int v = nums1[i][1];
            m[id] += v;
        }
        for(int i = 0 ; i < nums2.size(); i++){
            int id = nums2[i][0];
            int v = nums2[i][1];
            m[id] += v;
        }
        vector> ans;
        for (auto iter : m){
            int id = iter.first;
            int v = iter.second;
            ans.push_back({id, v});
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Find Largest Value in Each Tree Row  (0) 2025.03.03
Minimum Number of Operations to Sort a Binary Tree by Level  (0) 2025.03.03
Apply Operations to an Array  (0) 2025.03.01
Maximum Number of K-Divisible Components  (0) 2025.03.01
Length of Longest Fibonacci Subsequence  (0) 2025.02.27
블로그 이미지

짬뽕얼큰하게

,

Apply Operations to an Array

알고리즘 2025. 3. 1. 20:51

Leetcode Problem:

Summary

  • The problem requires applying operations to a given array of non-negative integers, where in each operation, if the current element is equal to the next element, the current element is multiplied by 2 and the next element is set to 0
  • The operations are applied sequentially, and after all operations, the 0's are shifted to the end of the array.

Approach

  • The approach used is to iterate over the array, apply the operations, and then shift the 0's to the end
  • The operations are applied sequentially, and the 0's are shifted to the end by adding them to the end of the array.

Complexity

  • O(n), where n is the size of the array, because each element is visited once.

Explanation

  • The solution code starts by initializing an index to 0 and an empty array to store the result
  • It then enters a while loop that continues until the index is greater than or equal to the size of the array
  • Inside the loop, it skips the 0's by incrementing the index until it finds a non-zero element
  • If the current element is equal to the next element, it multiplies the current element by 2 and increments the index
  • It then pushes the current element to the result array and increments the index
  • After the while loop, it shifts the 0's to the end of the array by adding them to the end of the array
  • Finally, it returns the result array.

Solution Code:


class Solution {
public:
    vector applyOperations(vector& nums) {
        int idx = 0;
        vector ans;
        while(idx < nums.size()){
            while(idx < nums.size() && nums[idx] == 0){
                idx++;
            }
            if(idx >= nums.size()) break;
            int num = nums[idx];
            if((idx + 1) < nums.size() && (nums[idx] == nums[idx+1])){
                num <<= 1;
                idx++;
            }
            ans.push_back(num);
            idx++;
        }
        int ansSize = ans.size();
        while(ansSize < nums.size()){
            ans.push_back(0);
            ansSize++;
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Minimum Number of Operations to Sort a Binary Tree by Level  (0) 2025.03.03
Merge Two 2D Arrays by Summing Values  (0) 2025.03.02
Maximum Number of K-Divisible Components  (0) 2025.03.01
Length of Longest Fibonacci Subsequence  (0) 2025.02.27
Reverse Odd Levels of Binary Tree  (0) 2025.02.27
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   2025/04   »
일 월 화 수 목 금 토
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30

티스토리툴바