[ C++ ] 조합, 순열 을 next_permutation() 으로 순회하기

next_permutation() 이란?

알고리즘을 하다보면 저희가 모든 경우의 수를 뽑아서 봐야할 때가 있습니다. 물론 이런 경우는 사실 대부분 재귀함수를 사용하다보면 해결이 되는 경우가 많습니다.

하지만 재귀를 통한 경우의 수 추출의 경우, 모든 경우의 수의 처리를 위해서는 해당 함수 호출스택 내에서 외부 변수에 모두 모아놓거나, 각각의 경우의 수가 완성된 경우의 함수 스택 상태 위에서 작업을 실행해야 모든 경우의 수에 대한 대응이 가능합니다.

간단한 처리의 경우는 상관 없지만, 스택 오버플로우 와 같은 오류를 내고 싶지 않은 상황이거나 재귀 함수를 사용 하는 것에 대해 약간 민감한 상황이라면, next_permutation 을 사용하는 것이 좋다고 생각합니다.

next_permutation() 함수는 algorithm 내 헤더에 있으며, 보통은 함수의 인자로 iterator 의 처음 부분과 끝 부분을 넣습니다.

이때 iterator 의 개념에 대해 간단히 이야기하자면, 그냥 배열의 요소를 가르킨다고 보시면 됩니다. C++을 알고리즘 문제풀이로 사용하는 입장에서는 일반적인 배열과 vector 의 처음과 끝 포인터가 들어간다고 생각하면 됩니다.

해당 함수가 호출되면, 함수의 인자로 들어간 배열 객체의 다음 순열의 순서로 변경해줍니다. 이때 정의된 배열의 순열의 순서는 오름차순이 기준입니다.

예를 들어, 0 0 1 의 순열을 오름차순으로 나열하였을 때, 해당 배열의 다음 순열은 0 1 0 일 겁니다. 그 다음은 1 0 0 일 것입니다.

따라서 보통 일반적으로 next_permutation()을 호출하기 전에 오름차순에 따라 정렬을 해두고 사용 해야 모든 순열의 경우의 수를 확인할 수 있습니다.

조합을 뽑는 방법

next_permutation 에서는 값이 같은 배열의 요소를 동일한 원소로 취급합니다. 이 점을 이용하여 조합을 만들 수도 있습니다.

이게 무슨 뜻이냐면, 0(1번째 원소) 0(2번째 원소) 1 이라는 내용의 배열이 있다면, 0 두개가 동일원소로 취급되지 않는 중복 순열 이라면 다음 순열은 0(2번째 원소) 0(1번째 원소) 1 이 다음 순열이여야합니다. 하지만 next_permuation 에서는 중복을 허용하지 않는 순열을 반환하기 때문에 중복 원소에 대한 순열은 스킵이 됩니다.

이를 통해 조합을 구성하는 방법은 간단합니다. 뽑는가, 뽑지 않는가 여부만 판단하는 것이 조합이므로, 뽑는 수만큼 1, 뽑지 않는 수만큼 0으로 구성된 0-1 배열을 구성하여 next_permutation 함수를 호출 하면, 모든 조합의 경우의 수를 알 수 있습니다.

응용

해당 문제는 응용입니다. 문제를 풀고 밑부분을 참고하세요.

• [ 백준 18809 ] Gaaaaarden : C++ 풀이

활용 설명

위에서 조합을 응용하는 방법은 그렇습니다.

조합을 두번 뽑지 않고, 중복순열이 아닌 점을 활용하는 겁니다.

땅이 5개, 그중에 빨간 배양액 2곳과 초록 배양액 2곳을 사용한다고 하는 예제 입력이 있다고 합시다. 그런 경우에 0 1 1 2 2 와 같은 배열의 순열을 순회하면 배양액을 뿌리는 모든 경우의 수를 저희는 확인할 수가 있을 것입니다.

위와 같은 방식으로 문제를 활용할 수도 있을 것입니다.

코드 짜는 법

이제부터는 실제 코드 사용법에 대해 알아보겠습니다.

익숙치 않는 문법을 사용할 건데요. do - while 문을 사용할 것입니다. 그것에는 이유가 있습니다. sort 를 통해 순열을 확인할 배열을 정렬했다면, 일단 맨 첫번째 순열은 이미 정렬된 해당 배열이기 때문에 해당 구문을 이용해 일단 확인해도 모든 경우의 수를 확인할 수 있기 때문입니다.

while문의 조건 문에서 next_permutation()을 호출하면 현재 해당 배열이 마지막 순열( = 현재 배열이 내림차순인지)인지 아닌지에 따라 return 값이 달라집니다.

마지막 순열이라면 false를 출력하기 때문에 순열을 순회하기도 쉽습니다.

1. 배열 구성하기
2. sort 하기
3. do - while 구문으로 순회하기

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

int main() {
    int arr[5];
    for (int i = 0; i < 5; ++i) {
        arr[i] = i + 1;
    }
    sort(arr, arr + 5);
    do {

        for (auto i : arr) {
            cout << i << ' ';
        }
        cout << '\n';
    } while (next_permutation(arr, arr + 5));
}