C++ STL의 prev_permutation 함수 완벽 정리: 구현 방법과 예제 코드

C++ STL의 prev_permutation 함수는 [first, last] 범위 내의 요소들을 사전순으로 바로 이전에 해당하는 순열로 재배치하는 데 사용됩니다. 순열(permutation)이란 N개의 요소를 나열할 수 있는 N!가지의 모든 가능한 배열을 의미합니다. 이 글에서는 STL의 prev_permutation을 활용하는 C++ 프로그램을 소개합니다.

prev_permutation이란?

prev_permutation은 현재 순열을 사전순(lexicographical order) 기준으로 바로 이전 순열로 변환합니다. 만약 현재 배열이 이미 가장 작은 순열이라면 false를 반환하고, 그렇지 않으면 이전 순열로 변환한 후 true를 반환합니다. 이 특성을 활용하면 do-while 반복문을 통해 모든 순열을 내림차순 순서로 출력할 수 있습니다.

알고리즘

prev_permutation을 사용한 순열 생성 알고리즘은 다음과 같습니다.

시작
    정수형 배열 변수 elements[]를 선언한다.
    사용자로부터 데이터 개수 e를 입력받는다.
    키보드로 입력받은 e개의 데이터로 배열 elements[]를 초기화한다.
    배열의 모든 요소를 오름차순으로 정렬한다.
    배열의 요소 순서를 뒤집는다(내림차순으로 만듦).
    반복
        show(elements) // 배열의 현재 내용을 출력
        prev_permutation(elements, elements + e)가 true인 동안 반복
종료.

예제 코드

아래는 prev_permutation을 사용하여 모든 순열을 사전순 역순으로 출력하는 전체 C++ 코드입니다.

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

// 배열의 현재 내용을 출력하는 함수
void show(int a[], int n) {
    for(int i = 0; i < n; i++) {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}

int main () {
    int e, i;
    cout<<"입력할 요소의 개수를 입력하세요: ";
    cin>>e;
    int elements[e];
    
    // 사용자로부터 배열 요소 입력받기
    for (i = 0; i < e; i++) {
        cout<<"요소 "<<i + 1<<" 입력: ";
        cin>>elements[i];
    }
    
    // 배열을 오름차순 정렬 후 뒤집어 내림차순으로 만든다
    sort (elements, elements + e);
    reverse (elements, elements + e);
    
    cout << "요소 "<<e<<"개로 만들 수 있는 "<<e<<"!가지 순열: "<<endl;
    
    // prev_permutation으로 이전 순열을 반복 생성
    do {
        show(elements, e);
    }
    while (prev_permutation(elements, elements + e));
    
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과를 확인할 수 있습니다.

입력할 요소의 개수를 입력하세요: 4
요소 1 입력: 7
요소 2 입력: 6
요소 3 입력: 10
요소 4 입력: 2
요소 4개로 만들 수 있는 4!가지 순열:
10 7 6 2
10 7 2 6
10 6 7 2
10 6 2 7
10 2 7 6
10 2 6 7
7 10 6 2
7 10 2 6
7 6 10 2
7 6 2 10
7 2 10 6
7 2 6 10
6 10 7 2
6 10 2 7
6 7 10 2
6 7 2 10
6 2 10 7
6 2 7 10
2 10 7 6
2 10 6 7
2 7 10 6
2 7 6 10
2 6 10 7
2 6 7 10

핵심 포인트 정리

내림차순 정렬이 필수: prev_permutation은 사전순으로 이전 순열을 찾기 때문에, 모든 순열을 얻으려면 배열을 내림차순으로 정렬한 상태에서 시작해야 합니다. sort() 후 reverse()를 호출하는 이유입니다.
반환값 활용: prev_permutation은 새로운 순열이 생성되면 true를, 더 이상 이전 순열이 없으면 false를 반환합니다. do-while문의 조건으로 사용하면 모든 순열을 빠짐없이 순회할 수 있습니다.
시간 복잡도: N개의 요소에 대해 총 N!개의 순열이 생성되며, 각 순열 변환은 O(N)의 시간이 걸립니다.
next_permutation과의 관계: 반대로 사전순으로 다음 순열을 찾으려면 next_permutation을 사용하며, 이 경우 배열을 오름차순으로 정렬한 상태에서 시작해야 합니다.

이처럼 prev_permutation은 순열 기반 문제 풀이, 브루트포스 알고리즘 구현 등 다양한 상황에서 유용하게 활용할 수 있는 STL 함수입니다.