관리 메뉴

Mini

순열 vs 중복순열 vs 조합 vs 중복조합 종결 본문

Algorithm/개념

순열 vs 중복순열 vs 조합 vs 중복조합 종결

Mini_96 2023. 6. 28. 21:34

* 순열 (for i=0부터)

void perm() {
    if (result.size() == 4) {	//4개뽑
        for (auto i : result) {
            cout << i << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 0; i < 4; ++i) {	//4개중
        if (visited[i]) continue;
        visited[i] = true;
        result.push_back(i);
        perm();
        result.pop_back();
        visited[i] = false;
    }
}

*중복순열 : 방문부분을 주석하면된다!

void permRe() {
    if (result.size() == 4) {
        for (auto i : result) {
            cout << i << " ";
        }
        cout << "\n";
        return;
        
    }

    for (int i = 0; i < 4; ++i) {
        //if (visited[i]) continue;
        //visited[i] = true;
        result.push_back(i);
        permRe();
        result.pop_back();
        //visited[i] = false;
    }
}

*조합 :  for i=idx부터, combi(i+1)

void combi(int idx) {
    if (result.size() == 4) {
        for (auto i : result) {
            cout << i << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = idx; i < 4; ++i) {
        if (visited[i]) continue;
        visited[i] = true;
        result.push_back(i);
        combi(i + 1);
        result.pop_back();
        visited[i] = false;
    }
}

*중복조합 :  for i=idx부터, combi(i), 방문부분주석

void combiRe(int idx) {
    if (result.size() == 4) {
        for (auto i : result) {
            cout << i << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = idx; i < 4; ++i) {
        //if (visited[i]) continue;
        //visited[i] = true;
        result.push_back(i);
        combiRe(i);
        result.pop_back();
        //visited[i] = false;
    }
}

 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
bool visited[4];
int cnt;
vector<int> result;

void combi(int idx) {
    if (result.size() == 4) {
        for (auto i : result) {
            cout << i << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = idx; i < 4; ++i) {
        if (visited[i]) continue;
        visited[i] = true;
        result.push_back(i);
        combi(i + 1);
        result.pop_back();
        visited[i] = false;
    }
}

void combiRe(int idx) {
    if (result.size() == 4) {
        for (auto i : result) {
            cout << i << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = idx; i < 4; ++i) {
        //if (visited[i]) continue;
        //visited[i] = true;
        result.push_back(i);
        combiRe(i);
        result.pop_back();
        //visited[i] = false;
    }
}

void perm() {
    if (result.size() == 4) {
        for (auto i : result) {
            cout << i << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 0; i < 4; ++i) {
        if (visited[i]) continue;
        visited[i] = true;
        result.push_back(i);
        perm();
        result.pop_back();
        visited[i] = false;
    }
}

void permRe() {
    if (result.size() == 4) {
        for (auto i : result) {
            cout << i << " ";
        }
        cout << "\n";
        return;
        
    }

    for (int i = 0; i < 4; ++i) {
        //if (visited[i]) continue;
        //visited[i] = true;
        result.push_back(i);
        permRe();
        result.pop_back();
        //visited[i] = false;
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

    cout << "순열" << endl;
    perm();

    cout << "중복순열" << endl;
    permRe();

    cout << "조합" << endl;
    combi(0);

    cout << "중복조합" << endl;
    combiRe(0);

    cout << cnt;

    return 0;
}

'Algorithm > 개념' 카테고리의 다른 글

배열 조회는 O(1)을 활용하라 => visit 배열사용  (0) 2023.08.13
배열 insert, erase 구현 cpp  (0) 2023.08.13