코딩테스트-순열

C++로 순열(Permutation) 구현하기

알고리즘 문제를 풀다 보면 "주어진 원소들을 모든 순서로 나열"해야 하는 상황이 자주 나온다. 이번 글에서는 C++에서 순열을 만드는 두 가지 방법을 정리한다.

1. STL next_permutation / prev_permutation 활용 (오름차순·내림차순 배열 기반)
2. 재귀 함수(swap)를 이용한 직접 구현

---

1. STL을 이용한 방법

가장 간단한 방법은 STL의 next_permutation과 prev_permutation을 쓰는 것이다.

#include <bits/stdc++.h>

using namespace std;

void printV(vector<int> &v){
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << " ";   // 구분을 위해 공백 추가
    }
    cout << "\n";
}

int main()
{
    int a[3] = {1, 2, 3};
    vector<int> v;

    for(int i = 0; i < 3; i++) v.push_back(a[i]);

    // 오름차순 정렬 상태에서 시작 → next_permutation
    do{
        printV(v);
    } while(next_permutation(v.begin(), v.end()));

    cout << "--------------------" << "\n";

    // 내림차순 정렬 상태에서 시작 → prev_permutation
    v.clear();
    for(int i = 2; i >= 0; i--) v.push_back(a[i]);
    do {
        printV(v);
    } while (prev_permutation(v.begin(), v.end()));

    return 0;
}

핵심 주의점: 정렬 상태가 전부다

next_permutation은 "현재 배열보다 사전순으로 다음 순열"을 만든다. 즉 현재 상태를 기준으로 그 다음 것만 찾아준다는 뜻이다. 그래서 모든 순열을 얻으려면 반드시 오름차순(가장 작은 순열)으로 정렬된 상태에서 시작해야 한다.

예를 들어 배열이 {2, 1, 3}인 상태에서 next_permutation을 돌리면 이보다 앞선 순열인 {1, 2, 3}, {1, 3, 2}는 절대 나오지 않는다. 이미 지나간 순서로 취급되기 때문이다. 결과가 "일부만" 나오는 것처럼 보이는 이유가 바로 이것이다.

• next_permutation → 시작 전 오름차순 정렬 필수
• prev_permutation → 시작 전 내림차순 정렬 필수

정렬이 보장되지 않는 입력이라면 아래처럼 명시적으로 정렬 후 사용하는 것이 안전하다.

sort(v.begin(), v.end());              // 오름차순 정렬
do {
    printV(v);
} while(next_permutation(v.begin(), v.end()));

---

2. 재귀 함수를 이용한 방법

STL이 없다고 가정하거나, 순열의 동작 원리를 직접 이해하고 싶다면 재귀 + swap 방식이 좋다.

#include <bits/stdc++.h>

using namespace std;
int a[3] = {1, 2, 3};
int n = 3, r = 3;

void print(){
    for(int i = 0; i < r; i++){
        cout << a[i] << " ";
    }
    cout << "\n";
}

void makePermutation(int n, int r, int depth){
    if(r == depth){   // 깊이가 r에 도달하면 하나의 순열 완성
        print();
        return;
    }
    for(int i = depth; i < n; i++){
        swap(a[i], a[depth]);              // 현재 자리에 원소 배치
        makePermutation(n, r, depth + 1); // 다음 자리로 진행
        swap(a[i], a[depth]);             // 원상 복구 (백트래킹)
    }
    return;
}

int main()
{
    makePermutation(n, r, 0);
    return 0;
}

동작 원리

이 방식의 핵심은 "자리(depth)마다 어떤 원소를 놓을지 하나씩 고정해 나가는 것"이다.

• depth: 현재 채우고 있는 자리(인덱스)
• swap으로 depth 자리에 후보 원소를 하나 놓는다.
• 다음 자리를 재귀로 채운다.
• 돌아오면 다시 swap으로 원상 복구한다. → 이것이 백트래킹(backtracking)이다.
• r == depth가 되면 하나의 완성된 순열이므로 출력한다.

여기서 r은 뽑을 개수다. r < n으로 설정하면 순열(nPr), 즉 "2개씩 끊어서" 뽑는 것도 가능하다. 예를 들어 r = 2로 두면 3개 중 2개를 순서 있게 뽑는 3P2가 출력된다.

---

3. 재귀 흐름 추적하기 (디버깅)

재귀가 어떻게 흘러가는지 직접 눈으로 확인하려면 로그를 찍어보는 것이 가장 확실하다. swap 전후로 n : r : depth를 출력해 호출 스택의 진행 상황을 관찰해 보자.

#include <bits/stdc++.h>

using namespace std;
int a[3] = {1, 2, 3};
int n = 3, r = 3;

void print(){
    for(int i = 0; i < r; i++){
        cout << a[i] << " ";
    }
    cout << "\n";
}

void makePermutation(int n, int r, int depth){
    if(r == depth){
        print();
        return;
    }
    for(int i = depth; i < n; i++){
        cout << n << " : " << r << " : " << depth << '\n';  // 진입 로그
        swap(a[i], a[depth]);
        makePermutation(n, r, depth + 1);
        cout << n << " : " << r << " : " << depth << '\n';  // 복귀 로그
        swap(a[i], a[depth]);
    }
    return;
}

int main()
{
    makePermutation(n, r, 0);
    return 0;
}

로그를 보면 depth가 깊어졌다가(재귀 진입) 다시 얕아지는(백트래킹) 패턴이 반복되는 것을 확인할 수 있다. 재귀 함수가 "들어갔다 나오는" 구조를 눈으로 이해하는 데 큰 도움이 된다.

---

정리

방법	장점	주의점
STL (next/prev_permutation)	코드가 짧고 간단, 실전에서 빠르게 사용	시작 전 반드시 정렬(오름/내림차순) 필요
재귀 + swap	동작 원리 이해에 좋음, nPr(일부만 뽑기) 확장 용이	중복 원소 처리 시 추가 로직 필요

실전 코딩 테스트에서는 next_permutation을 쓰되 "정렬부터 하고 시작"하는 습관만 들이면 실수가 크게 줄어든다.