조합과 순열 c++ 로 구현

https://yabmoons.tistory.com/99

https://yabmoons.tistory.com/100

 

저 위 블로그 주소에서 보고 알고리즘 공부중 써먹을곳이 많겠다 싶어서 작성합니다

백준 17281번 문제 푸는데 푸는법은 알겠어.. 근데 순열을 구현할 능력이 없었음

 

permutation 이라는 내장 기능이 있는데 이걸 자주 쓰는것도아니고

조합, 순열 한번쯤은 구현해봐야겠다 싶어서 시작

 

 

조합코드

백트래킹을 통해 선택 했을때 경우와 안 했을떄 경우를 재귀적으로 진입하는 방법인것 같음

#include <iostream>
 
using namespace std;
//1~5까지의 숫자중 3개를 뽑는 조합의 경우를 구하기
 
int arr[5];
bool select[5];
 
void print() {
    for (int i = 0; i < 5; i++) {
        if (select[i] == true)
            cout << arr[i] << ' ';
    }
    cout << '\n';
}
 
//idx숫자를 cnt 번째 칸에 사용했다는 뜻, 1,2,3 세 칸 사용
void dfs(int idx, int cnt) {
    if (cnt == 3) {
        print();
        return;
    }
 
    for (int i = idx; i < 5; i++) {
        if (select[i] == true) continue;
        select[i] = true;
 
        dfs(i, cnt + 1);
        select[i] = false;
    }
}
int main() {
    arr[0] = 1;
    arr[1] = 2;
    arr[2] = 3;
    arr[3] = 4;
    arr[4] = 5;
 
    dfs(0, 0);
 
    return 0;
}
 

순열코드, 지금 쓴것보다 작은 숫자도 다시 한번 봐야되기 때문에

dfs에 자릿수를 세는 cnt 변수만 넣어주면 됨

백터를 사용해서 나온 값을 저장하고 출력.

#include <iostream>
#include <vector>
using namespace std;
//1~5까지의 숫자중 3개를 뽑는 순열의 경우를 구하기
int arr[5];
bool select[5];
vector<int> v;
void print() {
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << ' ';
 
    cout << '\n';
}
//
void dfs(int cnt) {
    if (cnt == 3) {
        print();
        return;
    }
    for (int i = 0; i < 5; i++) {
        if (select[i] == true) continue;
        select[i] = true;
        v.push_back(arr[i]);
        dfs(cnt + 1);
        v.pop_back();
        select[i] = false;
    }
}
int main() {
    arr[0] = 1;
    arr[1] = 2;
    arr[2] = 3;
    arr[3] = 4;
    arr[4] = 5;
    dfs(0);
    return 0;
}