조합 구현 관련해서 질문있습니다.

9 asked

1

안녕하세요 희천님 ㅎㅎ

네 맞습니다. 잘 하셨네요 ㅎㅎ

combi 자체가 index를 뽑아내는 것이라 그걸 기반으로 인덱스 참조만 하시면 됩니다.

void combi(int start, vector<int> b){ 
    if(b.size() == k){
        print(b);
        return;
    }
    for(int i = start + 1; i < n; i++){
        b.push_back(i);
        combi(i, b);
        b.pop_back();
    }
    return;
}  

교안내의 combi를 보시면 저렇게 되어있는데요.

저 b.size() == k일 때

void print(vector<int> b){
    for(int i : b)cout << i << " "; 
    cout << '\n'; 
}

이렇게 print가 동작이 되는데 만약 어떠 배열이 arr라고할 때

void print(vector<int> b){
    for(int i : b)cout << arr[i] << " "; 
    cout << '\n'; 
}

이런식으로 인덱스 참조해서 뽑아내시면 됩니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

0

저번에 순열은 인풋 배열이 주어지고 그걸 기반으로 값을 출력하는 방식이어서 이번 조합 강의를 보고 0 부터가 아닌 임의의 배열을 기반으로 조합을 만드는 함수를 구현해보고 있었거든요.... 하다가 막혀서 질문 남겼는데 큰돌님 구현 기반으로 값이 잘 찍히는거 같아요... 그래도 봐주셔서 감사합니다....

#include "../common/common.h"
#include <bits/stdc++.h>

using namespace std;

template <typename T>
void make_combination(vector<vector<T>> &result, vector<T> &source, vector<T> &local, int n, int r, int start)
{
    if (local.size() == r)
    {
        result.push_back(local);
        return;
    }

    for (int i = start + 1; i < n; ++i)
    {
        local.push_back(source[i]);
        make_combination(result, source, local, n, r, i);
        local.pop_back();
    }
}

int main()
{
    vector<vector<int>> result = {};
    vector<int> source = {1, 3, 5, 2, 4};
    vector<int> local = {};
    sort(source.begin(), source.end());
    make_combination(result, source, local, source.size(), 4, -1);

    for (auto &v : result)
        print(v);
    return 0;
}