C++ 코딩테스트 강좌, 순열의 순서 구하기

안녕하세요, 여러분! 오늘은 C++ 코딩테스트에서 자주 등장하는 순열의 순서 구하기 문제에 대해 깊이 있게 살펴보도록 하겠습니다. 이 문제는 순열의 개념을 이해하고, 조합론적인 문제 해결 능력을 기르는데 큰 도움이 될 것입니다. 순열(pemutations)은 주어진 숫자들의 모든 나열을 의미하며, 이를 활용한 문제들은 다양한 분야에서 응용됩니다.

문제 설명

다음과 같은 문제를 푸는 과정을 통해 순열의 개념과 C++ 구현 방식에 대해 알아보겠습니다:

문제: 정수 N과 K가 주어질 때, 1부터 N까지의 수를 이용하여 만들 수 있는 모든 순열 중 K번째 순열을 구하시오. K는 1부터 시작한다고 가정한다.

입력 형식

첫 번째 줄에 정수 N (1 ≤ N ≤ 10)과 K (1 ≤ K ≤ N!)이 주어진다.

출력 형식

K번째 순열을 한 줄에 공백으로 구분하여 출력한다.

예제

입력:
3 2

출력:
2 1 3

문제 접근 방법

이 문제를 해결하기 위해서는 다음과 같은 단계로 접근할 수 있습니다:

순열의 기본 개념을 이해합니다.
N개의 숫자가 주어졌을 때, K번째 순열을 찾기 위한 방법을 설계합니다.
순열 생성 방법을 코드로 구현합니다.
K번째 순열을 반환합니다.

순열 생성 방법

순열을 생성하는 방법에는 여러 가지가 있지만, 여기서는 팩토리얼을 활용한 방법을 사용할 것입니다. N개의 숫자로 이루어진 순열은 N!개의 조합이 가능하며, 이 조합들을 생성하는 알고리즘은 효율적으로 K번째 순열을 직접 계산할 수 있게 도와줍니다.

팩토리얼 계산

팩토리얼 N!는 N * (N-1) * (N-2) * … * 1로 정의됩니다. 예를 들어, 3! = 6입니다. 이를 통해, 주어진 N에 대해 각 숫자를 선택하기 위한 가능한 경우의 수를 계산할 수 있습니다.

조금 더 구체적으로

1부터 N까지의 숫자를 나열할 때, 첫 번째 숫자는 K에 따라 선택될 수 있습니다. 예를 들어, 만약 K가 2라면, 첫 번째 숫자를 결정할 때 각각의 첫 번째 숫자에 대한 다음 숫자 선택의 방법을 고려하여 K번째 순열을 찾습니다.

C++ 코드 구현

이제 위의 접근 방식을 바탕으로 C++ 코드를 작성해 보겠습니다. 이 코드는 주어진 N과 K를 사용하여 K번째 순열을 출력합니다.


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 팩토리얼 계산 함수
long long factorial(int n) {
    if (n == 0) return 1;
    long long result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

// K번째 순열 구하는 함수
vector<int> getKthPermutation(int n, int k) {
    vector<int> numbers;
    for (int i = 1; i <= n; i++) {
        numbers.push_back(i);
    }
    
    k--; // 0-indexing
    vector<int> permutation;

    for (int i = 0; i < n; i++) {
        long long fact = factorial(n - 1 - i);
        int index = k / fact;
        permutation.push_back(numbers[index]);
        numbers.erase(numbers.begin() + index); // 선택된 숫자는 리스트에서 제거
        k %= fact;
    }

    return permutation;
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> kthPermutation = getKthPermutation(n, k);
    
    for (int num : kthPermutation) {
        cout << num << " ";
    }
    
    return 0;
}

코드 설명

팩토리얼 함수: 주어진 N의 팩토리얼을 계산하여 반환합니다.
K번째 순열 함수: 1부터 N까지의 숫자를 벡터에 저장한 후, K번째 순열을 찾기 위해 반복합니다.
각 단계에서 가능한 경우의 수를 계산하여 어떤 숫자를 선택할지를 결정합니다.
선택된 숫자는 리스트에서 제거하고, K값도 업데이트하여 다음 숫자를 선택합니다.

테스트 및 결과 확인

위의 코드에서 입력값으로 N과 K를 주고, K번째 순열을 잘 출력하는지 확인해보세요. 예를 들어 N=3, K=2를 입력하면 2 1 3이 출력되어야 합니다.

마무리

오늘은 C++을 이용하여 순열의 순서를 구하는 방법에 대해 알아보았습니다. 이 알고리즘을 통해 순열에 대한 이해도를 높일 수 있고, 나아가 다양한 알고리즘 문제를 해결하는 데 도움을 줄 수 있을 것입니다. 실전 코딩테스트에 자주 출제되는 유형이니만큼, 충분히 연습해두시기 바랍니다.

감사합니다!