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

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

[필수개념] 조합(combination)

해결된 질문

작성

244

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

혹시 임의의 배열(벡터)를 인자로 받아서 그 배열의 조합을 리턴하는 방법도 나오나요?

예를들면

vector<int> v = {10, 20, 30, 40, 50};

combi(v, 5, 3); // where 5 == n, 3 == r


10, 20, 30
10, 20, 40
...
30, 40, 50

위와 같은 방식이요.

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 희천님 ㅎㅎ

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

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 부터가 아닌 임의의 배열을 기반으로 조합을 만드는 함수를 구현해보고 있었거든요.... 하다가 막혀서 질문 남겼는데 큰돌님 구현 기반으로 값이 잘 찍히는거 같아요... 그래도 봐주셔서 감사합니다....

#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;
}

인프런 커뮤니티 질문&답변

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