순열과 조합: C++에서의 사용 방법 정리

순열과 조합은 컴퓨터 과학과 수학에서 중요한 개념으로, 다양한 문제를 해결하는 데 사용된다. C++의 표준 라이브러리에는 이러한 작업을 쉽게 처리할 수 있도록 next_permutation과 같은 유용한 함수가 제공된다. 이 글에서는 순열과 조합의 개념과 C++에서의 구현 방법을 알아보았다.

1. 순열 (Permutation)

수학적으로 순열은 서로 다른 n개의 원소에서 r개를 뽑아 한 줄로 나열하는 경우의 수를 의미한다. 예를 들어, {1, 2, 3}이라는 세 원소가 있을 때, 이 원소들로 만들 수 있는 모든 순열은 다음과 같다:

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

C++에서 순열 구하기: next_permutation

C++의 <algorithm> 헤더에는 next_permutation이라는 함수가 제공되며, 이 함수를 사용하면 손쉽게 순열을 구할 수 있다.

사용 예시: {1, 2, 3}의 모든 순열 출력

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v{ 1, 2, 3 };

    // 먼저 오름차순으로 정렬
    sort(v.begin(), v.end());

    // 모든 순열 출력
    do {
        for (auto it = v.begin(); it != v.end(); ++it)
            cout << *it << ' ';
        cout << endl;
    } while (next_permutation(v.begin(), v.end()));

    return 0;
}

주의할 점

1. next_permutation 함수는 컨테이너가 오름차순으로 정렬된 상태에서 사용해야 한다.
2. next_permutation은 오름차순으로 다음 순열을 생성하며, operator<를 사용한다.
3. 중복된 원소가 있는 경우, 중복되지 않은 순열만 생성된다.

2. 조합 (Combination)

조합은 n개의 원소 중에서 r개를 순서에 상관없이 뽑는 경우의 수를 말한다. 예를 들어, {1, 2, 3, 4}에서 두 개의 원소를 뽑는 모든 조합은 다음과 같다:

• 1, 2
• 1, 3
• 1, 4
• 2, 3
• 2, 4
• 3, 4

C++에서 조합 구하기: prev_permutation을 이용한 방법

조합을 구할 때는 특정 원소의 선택 여부를 표시하는 임시 배열을 사용하여 해결할 수 있다. 예를 들어, {1, 2, 3, 4}에서 두 개의 원소를 뽑기 위해 [1, 1, 0, 0]와 같이 임시 배열을 설정하고, 이 배열의 모든 순열을 구한다. 여기서 1의 위치가 선택된 원소를 나타낸다.

사용 예시: {1, 2, 3, 4} 중 두 개의 원소를 뽑는 모든 조합 출력

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> s{ 1, 2, 3, 4 };
    vector<int> temp{ 1, 1, 0, 0 }; // 1이 있는 위치는 조합에 포함될 원소

    do {
        for (int i = 0; i < s.size(); ++i) {
            if (temp[i] == 1)
                cout << s[i] << ' ';
        }
        cout << endl;
    } while (prev_permutation(temp.begin(), temp.end()));

    return 0;
}

주의할 점

1. prev_permutation은 내림차순으로 정렬된 상태에서 사용해야 한다.
2. 임시 배열에서 1과 0의 개수로 조합을 설정한다.
3. prev_permutation을 사용하면 조합이 오름차순으로 출력된다.

결론

순열과 조합은 다양한 경우의 수를 계산하는 데 필수적인 개념이다. C++에서는 next_permutation과 prev_permutation을 사용하여 이를 쉽게 구현할 수 있다. 이러한 함수들을 활용하면 복잡한 문제를 간단하게 해결할 수 있으므로, 알고리즘 문제를 해결할 때 적극적으로 사용해보도록 한다.

참고 자료

• [C++ / Algorithm] 순열(next_permutation) 사용 방법과 조합(Combination) 구하기
• C++ Reference: next_permutation