[PS] 순열과 조합

yeonjiyooo·2025년 2월 9일

PS

목록 보기

17/18

👋 순열과 조합의 구현을 시간복잡도의 관점에서 생각해보자!

✏️ 순열 permutation

nPk : n개의 수 중에서 k개를 골라 순서를 고려하여 나열하는 경우의 수

순열과 조합을 구분하는 기준은 "순서를 고려할 것인가" 이다.

예를 들어, 회장-부회장-차장 각 1명씩 총 3명을 뽑는 경우와 대표 3명 뽑는 경우가 각각 순열과 조합의 예시가 될 수 있다.

Backtracking을 이용한 순열 구현: O(N!)

백준 5568 카드 놓기

가장 간단한 순열의 구현 방식으로는 backtracking이 있다. 길이 5 짜리의 모든 순열을 만든다고 할 때 현재 자리에 아직 사용되지 않은 숫자 중 가장 작은 것부터 넣은 후, 남은 자리에 대해 permutation 함수를 재귀 호출한다.

이 코드에서 주의해야 할 점은 특정 값에 대해 방문 처리를 하고 해당 값을 포함한 모든 순열을 만든 이후에는 다시 그 값의 방문 처리를 해제 해야된다는 점이다!

#include <stdio.h>
#include <iostream>
#include <set>
#include <cmath>

using namespace std;

string input[11];
bool visited[11] = {false, };
set<string> p;

int n, k;
int cnt = 0;

void permutation(int length, string num) {
    
    if (length == k) {
        if (p.find(num) == p.end()) cnt++; //기존에 만들어지지 않은 정수인 경우
        //cout << num << "생성\n";
        p.insert(num);
        return;
    }
    
    ⭐ ⭐ ⭐ ⭐ ⭐ ⭐ ⭐ ⭐ ⭐ ⭐ ⭐ ⭐
    for (int i=1; i<=n; i++) {
        if (!visited[i]) {
            visited[i] = true;      //방문 처리
            permutation(length+1, num + input[i]);
            visited[i] = false;     //방문 처리 해제
        }
    }
    ⭐ ⭐ ⭐ ⭐ ⭐ ⭐ ⭐ ⭐ ⭐ ⭐ ⭐ ⭐
    
    return;
}

int main(){
    ios::sync_with_stdio();
    cin.tie(NULL);
    
    string m;
    cin >> n >>  k;
    
    for (int i=1; i<=n; i++) {
        cin >> m;
        input[i] = m;
    }
    
    permutation(0, "");
    cout << cnt;
    
    return 0;
}

backtracking을 이용하는 경우의 시간 복잡도는 O(N!) 이다. 가능한 모든 경우를 다 탐색하기 때문에 N개의 수로 만들 수 있는 모든 순열의 개수인 N! 만큼의 연산이 필요하다.

따라서 문제에서 주어지는 N의 값이 큰 경우 시간초과 등의 이유로 사용이 부적절 할 수 있다. N이 20만 되더라도 20! = 2,432,902,008,176,640,000 이다.

Backtracking 제외 다른 방법

백준 1722번 순열의 순서

위 문제가 대표적으로 backtracking을 이용한 구현이 불가능한 경우이다.

반복문을 통해 1! ~ 20!의 값을 계산하여 배열에 담아놓고 꺼내 쓰는 식으로 구현을 했는데, 어디서 틀린 건지 아직 해결이 안돼서 나중에...^^* 수정해놓겠습니다!!! 혹시 이 글을 보시는 분들 중 제 코드에서 오류를 발견해주시는 분이 계시다면 그 쪽 방향으로 절 한 번 올리겠습니다.

#include <stdio.h>
#include <iostream>

using namespace std;

int n, m, value;
long long k;

bool visited[21] = {false, };
int num[21];
int input[21];

long long factorial[21];

void permutation(long long order) {
    int now = 0;
    for (int i=1; i<=n; i++) {
        for (int j =1; j<=n; j++) {
            if (visited[j]) continue;
            
            if (now + factorial[n-i] < order) {
                now += factorial[n-i];
            } else {
                num[i] = j;
                visited[j] = true;
                break;
            }
        }
    }
    for (int i=1; i<=n; i++) cout << num[i] << " ";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    
    cin >> n >> m; //1부터 n까지의 자연수
    
    factorial[0] = 1;
    
    for (int i=1; i<=n; i++) {
        factorial[i] = factorial[i-1] * i;
    }
    
    if (m == 1) { //k번째 순열 구하기
        cin >> k;
        permutation(k);
    }
    else if (m == 2) { //입력받은 순열의 순서 구하기
        
        for (int i=1; i<=n; i++) {
            cin >> value;
            input[i] = value;
        }
        
        long long result = 1;
        
        for (int i=1; i<=n;i++){
            for (int j=1; j<input[i]; j++) {
                if (visited[j] == false) result += factorial[n-i];
            }
            visited[input[i]] = true;
        }
        cout << result;
    }
    
    return 0;
}