[필수개념] 조합 관련 문의

작성한 질문수 6

0

안녕하세요 9201님 ㅎㅎ

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

이부분을

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

앞의 코드처럼 바꿨다는 말씀이시죠?

안됩니다.

a[5] = {1, 2, 3, 4, 5};

이 코드의 이미는 5의 크기를 가지는 배열을 정의한 것입니다.

0, 1, 2, 3, 4 라는 인덱스로 참조가 가능하죠. 근데 여기서

<= n을 하게 되면

5라는 인덱스를 참조할거야!! 하면서 5라는 인덱스를 집어넣게 되버리겠죠?

한번 구동시켜볼까요?

#include <bits/stdc++.h>
using namespace std;

int n = 5, k = 3, a[5] = {1, 2, 3, 4, 5}; 
void print(vector<int> b){
    for(int i : b)cout << i << " "; 
    cout << '\n'; 
}
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;
}  

int main() {
    vector<int> b; 
    combi(-1, b); 
    return 0;
}

이를 구동시키면

0 1 2
0 1 3
0 1 4
0 1 5
0 2 3
0 2 4
0 2 5
0 3 4
0 3 5
0 4 5
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

다음과 같이 5라는 인덱스가 뽑혀져 나옵니다.

우리는 인덱스를 뽑는 거지, 값을 뽑는 게 아닙니다. 0번째, 1번쨰, 2번째 인덱스를 추출하는것에 집중해주세요.

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

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

감사합니다.

강사 큰돌 올림.