[알고리즘] 1. 조합과 순열

//개념

순열 : n개의 원소 중에서 r개의 원소들을 나열하는 경우의 수 

순서가 다르면 다른 경우 => [0, 1, 2] != [1, 2, 0] != [2, 0, 1] ... 전부 다른 경우로 친다.

---

조합 : n개의 원소 중에서 r개의 원소들을 고르는 경우의 수

순서가 달라도 같은 경우 => [0, 1, 2] == [1, 2, 0] ... 0, 1, 2 원소가 포함시 전부 같은 경우로 친다.

---

순열과 조합의 관계

순열은 조합에 순서를 포함하는 모든 경우의 수와 같다.

---

순열 문제 풀이

https://www.acmicpc.net/problem/10974

 

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int n;
vector<int> components; //원본 int list
vector<int> cur_permutation;//순열조합
map<int, bool> use_check;//순열조합을 만드는 과정에서 사용중인 int 체크

//결과 프린트
void print_vector(){
    for (int i = 0; i < cur_permutation.size(); ++i) {
        cout << cur_permutation[i] << " ";
    }
    //endl은 시간이 느림
    cout << "\n";
}

//순열 조합 재귀함수
void permutation(int depth){
    if(cur_permutation.size() == components.size()){
        print_vector();
        return;
    }
    
    //순열 조합을 만들때 하나씩 int를 가져와서 사용여부를 체크한뒤 cur_permutation에 수집해둠
    for (int i = 0; i < n; ++i) {
        if(use_check[components[i]] == true){
            continue;
        }
        //사용한 숫자요소는 사용을 true로 체크
        cur_permutation.push_back(components[i]);
        use_check[components[i]] = true;
        
        //다음 숫자를 넘겨서 순열 조합을 추가해나감
        permutation(depth+1);
        
        //다음숫자를 넘기고 아래 정렬을 다 돌리고 나면 현 숫자는 순열리스트에서 빼고 사용을 false로 초기화
        use_check[components[i]] = false;
        cur_permutation.pop_back();
    }
}


int main(int argc, const char * argv[]) {
    cin >> n;
    
    for (int i = 1; i <= n; ++i) {
        components.push_back(i);
    }
    
    permutation(0);
    
    return 0;
}

 

주의할점)

endl을 시간이 느리기때문에 시간복잡도를 고려하며 줄바꿈할때 "\n"을 사용한다.