[Programmers]_C++_Algorithm_비밀코드해독

python을 쓸때는 lib에 permutation과 combination이 모두 있었다. 하지만 C++에는 없음.
permutation은 있지만 combination은 없음.
permutation을 이용하여 combination을 만드는 방법, 아무것도 없이 만드는 방법 등 다양한 방법을 이해하고 사용할 줄 알아야겠다.

그리고 오늘부로 Programmers의 level1은 끝

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int comp (vector<int> comb, vector<vector<int>> q, vector<int> ans){
    bool flag = false;
    for (int i = 0; i < q.size(); i++){
        int temp =0;
        for (int j=0; j<q[i].size(); j++){
            auto it = find(comb.begin(), comb.end(), q[i][j]);
            if (it != comb.end())
                temp++;
        }
        if (temp != ans[i])
            flag = true;
        if (flag == true)
            break;
    }
    if (flag == false)
        return 1;
    else
        return 0;
}

int combi(int n, int r, vector<vector<int>> q, vector<int> ans) {
    vector<int> nums(n, 0);
    int result = 0;
    for (int i = 0; i < r; i++) {
        nums[i] = 1; 
    }
    
    sort(nums.begin(), nums.end());
    
    do {
        vector<int> combination;
        for (int i = 0; i < n; i++) {
            if (nums[i]) combination.push_back(i + 1);
        }
        
        result += comp(combination, q, ans);
    } while (next_permutation(nums.begin(), nums.end()));
    
    return result;
}

int solution(int n, vector<vector<int>> q, vector<int> ans) {
    int answer = 0;
    answer = combi(n, 5, q, ans);
    
    
    
    return answer;
}

lib 없이 combination을 만드는 방법

#include <iostream>
using namespace std;

// 팩토리얼을 이용한 조합 계산
long long factorial(int n) {
    long long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

long long combination(int n, int r) {
    if (r > n) return 0;
    return factorial(n) / (factorial(r) * factorial(n - r));
}

// 동적 계획법을 이용한 조합 계산 (메모이제이션)
long long combinationDP(int n, int r) {
    long long dp[n + 1][r + 1];
    
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= min(i, r); j++) {
            if (j == 0 || j == i)
                dp[i][j] = 1;
            else
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        }
    }
    return dp[n][r];
}

int main() {
    int n = 5, r = 2;
    cout << "Combination using factorial: " << combination(n, r) << endl;
    cout << "Combination using DP: " << combinationDP(n, r) << endl;
    return 0;
}