목차

• Bitmask를 이용한 모든 부분집합 구하기
• DP를 이용한 최적화 문제
• hashtable을 통해 array를 생성하기

---

Bitmask를 이용한 모든 부분집합 구하기

• Maximum Product of the Length of Two Palindromic Subsequences

• 풀이

• 문제 요약
  • string이 주어졌을 때, 두 disjoint palindromic subsequence의 길이의 곱의 최대값을 구하라.
  • disjoint: 두 sequence가 같은 index에 같은 문자를 가지고 있지 않은 경우
  • palindromic: 앞으로 읽어도 뒤로 읽어도 같은 문자열
  • subsequence: sequence에서 순서를 유지하며 일부 원소를 제거한 sequence
• 풀이 요약
  • Brute Force
    • 모든 subsequence를 구한 후, palindromic인지 확인하고, 이들 중 disjoint인 경우의 길이의 곱의 최대값을 구한다.
    • 모든 subsequence구하기: O(2^n)
    • palindromic인지 확인하기: O(n)
    • disjoint인지 확인하기: O(n)
    • Time Complexity: $O(2^n \cdot n)$
    • input size가 최대 12이므로 시간 복잡도를 줄일 필요가 없다.
  • bitmask를 통한 subsequence 구하기
    • loop을 통해 bitmask를 생성하고, 해당 bitmask에 해당하는 subsequence를 구한다.
    • for(int mask = 1; mask < (1 « n); mask++)
    • for(int i = 0; i < n; i++)
      • if(mask & (1 « i)) subseq += s[i]
  • disjoint인지 확인하기
    • 두 mask의 교집합이 없는지 & 연산을 통해 확인한다.O(1)
  • palindromic인지 확인하기
    • subsequence를 구한 후, palindromic인지 확인한다.O(n)

class Solution {
public:
    int maxProduct(string s) {
        unique_ptr<vector<int>> palindromic_masks = get_palindromic_masks(s);
        int max_product = max_product_of_two_palindromic_subsequences(*palindromic_masks);

        return max_product;
    }

private:
    unique_ptr<vector<int>> get_palindromic_masks(const string& s) {
        int n = s.size();
        unique_ptr<vector<int>> palindromic_masks = make_unique<vector<int>>();
        for (int mask = 1; mask < (1 << n); ++mask) {
            string subseq = "";
            for (int i = 0; i < n; ++i) {
                if (mask & (1 << i)) {
                    subseq += s[i];
                }
            }

            if (is_palindrome(subseq)) {
                palindromic_masks->push_back(mask);
            }
        }

        return palindromic_masks;
    }

    int max_product_of_two_palindromic_subsequences(const vector<int>& palindromic_masks) {
        int max_product = 0;
        for (int i = 0; i < palindromic_masks.size(); ++i) {
            for (int j = i + 1; j < palindromic_masks.size(); ++j) {
                if ((palindromic_masks[i] & palindromic_masks[j]) == 0) {
                    int product = bit_count(palindromic_masks[i]) * bit_count(palindromic_masks[j]);
                    max_product = max(max_product, product);
                }
            }
        }

        return max_product;
    }

    bool is_palindrome(const string& s) {
        int l = 0, r = s.size() - 1;
        while (l < r) {
            if (s[l++] != s[r--]) return false;
        }
        return true;
    }

    int bit_count(unsigned int x) {
        int count = 0;
        while (x) {
            count += x & 1;
            x >>= 1;
        }
        return count;
    }
};

DP를 이용한 최적화 문제

• Maximize the Profit as the Salesman

• 풀이

• 문제 요약
  • salesman이 주어진 집들을 방문할 때, 이익의 최대값을 구하라.
  • 각각의 offer는 집 i부터 집 j까지의 판매 이익을 의미한다.
  • offers[i] = [start_i, end_i, gold_i]
• 풀이 요약
  • DP
    • dp[i] = i번째 집까지 방문했을 때의 최대 이익
    • offersEndingAt[i] = i번째 집에서 끝나는 offer들의 (start, gold) 정보
    • dp[i] = max(dp[j] + gold) (j: offersEndingAt[i]의 start)

class Solution {
public:
    int maximizeTheProfit(int n, vector<vector<int>>& offers) {
        vector<int> dp(n + 1, 0); // dp[i]는 길이가 i인 길의 최대 이익
        vector<vector<pair<int, int>>> offersEndingAt(n); // offersEndingAt[i]는 길의 끝이 i인 제안들(시작, 금액)
        // Group offers by their end positions
        for (const auto& offer : offers) {
            int start = offer[0];
            int end = offer[1];
            int gold = offer[2];
            offersEndingAt[end].emplace_back(start, gold);
        }
        // Dynamic Programming to calculate maximum profit
        for (int i = 0; i < n; ++i) {
            dp[i + 1] = dp[i]; // Initialize dp[i+1] with dp[i]
            for (const auto& [start, gold] : offersEndingAt[i]) {
                dp[i + 1] = max(dp[i + 1], dp[start] + gold); // dp[i+1]은 start에서 끝나는 제안의 금액 + dp[start] 중 최대값
            }
        }
        return dp[n];
    }
};

---

hashtable을 통해 array를 생성하기

• Check Array Formation Through Concatenation

• 풀이

• 문제 요약
  • distinct한 integer로 이루어진 array arr이 주어진다.
  • distinct한 integer로 이루어진 array pieces가 주어진다.
  • pieces 내부의 순서를 바꾸지 않고 pieces를 합쳐서 arr을 만들 수 있는지 확인하라.
• 풀이 요약
  • Brute Force
    • Time Complexity: $O(n!)$
    • pieces의 순열을 구한 후, arr과 비교한다.
  • 개선 풀이
    • Time Complexity: $O(n)$
    • hashtable을 사용하여 pieces의 첫번째 숫자를 key로 하고, pieces를 value로 하는 map을 생성한다.
    • arr을 순회하면서, map에 있는 key가 나오면, pieces를 순회하면서 arr과 같은지 확인한다.

class Solution {
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        map<int, vector<int>> mp;
        for (auto& p : pieces) {
            mp[p[0]] = p;
        }
        vector<int> res;
        for (int i = 0; i < arr.size(); i++) {
            if (mp.find(arr[i]) != mp.end()) {
                res.insert(res.end(), mp[arr[i]].begin(), mp[arr[i]].end());
            }
        }
        return res == arr;
    }
};

---

2024-10-28

←이전 글: 10월 4주차 알고리즘 문제 카테고리로 돌아가기 ↩