C++ Algorithm Permutation | "순열 알고리즘" 가이드
이 글의 핵심
C++ Algorithm Permutation에 대한 실전 가이드입니다.
Permutation이란?
순열(permutation) 은 원소들을 다른 순서로 나열한 것입니다. 예를 들어 {1,2,3}의 순열은 123, 132, 213, 231, 312, 321 여섯 가지입니다. C++에서는 std::next_permutation / std::prev_permutation으로 사전순(lexicographic) 으로 다음·이전 순열을 구할 수 있어, 브루트포스 탐색·스케줄링·암호 후보 생성 등에 쓰입니다.
언제 쓰나요?
- 모든 경우를 체크해야 할 때 (완전 탐색)
- n이 작을 때 (대략 10 이하 권장; 11! ≈ 4천만, 12!은 4억 이상)
- 조합을 비트나
next_permutation으로 표현할 때
아래는 반드시 범위를 정렬한 뒤 루프로 모든 순열을 도는 기본 패턴입니다.
#include <algorithm>
#include <vector>
std::vector<int> v = {1, 2, 3};
// 모든 순열
do {
for (int x : v) {
std::cout << x << " ";
}
std::cout << std::endl;
} while (std::next_permutation(v.begin(), v.end()));동작: next_permutation은 현재 순열을 사전순 다음으로 바꾸고 true를 반환합니다. 이미 마지막 순열이면 다음이 없으므로 false를 반환하고, 이때 범위는 사전순 첫 순열(오름차순)로 돌아갑니다. 그래서 위처럼 do-while로 쓰면 첫 순열부터 마지막 순열까지 정확히 한 번씩만 처리할 수 있습니다.
기본 사용
한 번만 “다음/이전”으로 넘기고 싶을 때는 반환값으로 다음 순열이 있었는지 확인할 수 있습니다.
#include <algorithm>
std::vector<int> v = {1, 2, 3};
// 다음 순열로 바꾸고, 성공 여부 반환
bool ok = std::next_permutation(v.begin(), v.end());
// v는 {1, 3, 2}, ok == true
// 이전 순열로 되돌리기
std::prev_permutation(v.begin(), v.end());
// v는 다시 {1, 2, 3}실전 예시
예시 1: 모든 순열 출력
시작점을 오름차순(사전순 첫 순열) 로 맞추기 위해 std::sort를 먼저 호출하는 것이 중요합니다. 정렬하지 않으면 “현재 순열부터” 마지막 순열까지만 생성되어 앞쪽 순열들이 빠집니다.
#include <algorithm>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3};
// 정렬 (시작점)
std::sort(v.begin(), v.end());
int count = 0;
do {
++count;
for (int x : v) {
std::cout << x;
}
std::cout << std::endl;
} while (std::next_permutation(v.begin(), v.end()));
std::cout << "총 " << count << "개" << std::endl; // 6
}n=3이면 3! = 6개이므로 위 루프는 정확히 6번 돌며, 매번 서로 다른 순열이 출력됩니다.
예시 2: 문자열 순열
#include <algorithm>
#include <string>
int main() {
std::string str = "abc";
do {
std::cout << str << std::endl;
} while (std::next_permutation(str.begin(), str.end()));
// abc
// acb
// bac
// bca
// cab
// cba
}std::string도 연속 메모리이므로 begin()/end()로 같은 방식으로 사용할 수 있습니다. 애너그램·암호 후보 생성 등에 활용할 수 있습니다.
예시 3: k-순열 (n개 중 k개 뽑아 순서대로 나열)
#include <algorithm>
#include <vector>
void kPermutation(std::vector<int> v, int k) {
std::sort(v.begin(), v.end());
do {
for (int i = 0; i < k; ++i) {
std::cout << v[i] << " ";
}
std::cout << std::endl;
} while (std::next_permutation(v.begin(), v.end()));
}
int main() {
std::vector<int> v = {1, 2, 3, 4};
kPermutation(v, 2); // 2-순열
}k-순열은 “앞 k개만 사용”하면 됩니다. next_permutation이 전체를 재배열하므로, 매번 앞 k개만 읽어서 처리하면 n개 중 k개를 뽑아 순서대로 나열한 모든 경우를 얻습니다.
예시 4: 조합 (n개 중 k개 뽑기, 순서 무관)
#include <algorithm>
#include <vector>
void combination(std::vector<int> v, int k) {
std::vector<bool> selector(v.size());
std::fill(selector.begin(), selector.begin() + k, true);
do {
for (size_t i = 0; i < v.size(); ++i) {
if (selector[i]) {
std::cout << v[i] << " ";
}
}
std::cout << std::endl;
} while (std::prev_permutation(selector.begin(), selector.end()));
}
int main() {
std::vector<int> v = {1, 2, 3, 4};
combination(v, 2); // 2-조합
}조합은 true/false로 “뽑음/안 뽑음”을 나타내는 selector 벡터를 두고, 이 벡터의 순열을 돌리면 됩니다. prev_permutation을 쓰면 사전순으로 “이전” 조합이 나오므로, fill(..., true)로 앞 k개만 true로 둔 뒤 루프를 돌면 nCk 가지를 모두 생성할 수 있습니다.
자주 발생하는 문제
문제 1: 정렬
std::vector<int> v = {3, 1, 2};
// ❌ 정렬 안 됨
do {
// 일부 순열만 생성
} while (std::next_permutation(v.begin(), v.end()));
// ✅ 정렬 후
std::sort(v.begin(), v.end());
do {
// 모든 순열 생성
} while (std::next_permutation(v.begin(), v.end()));문제 2: 반환값으로 “다음이 있었는지” 확인
next_permutation은 다음 순열로 바꾼 뒤 “다음이 있었는지”를 bool로 반환합니다. 마지막 순열에서 한 번 더 호출하면 false가 나오고, 이때 범위는 사전순 첫 순열(오름차순) 으로 초기화됩니다. while로 쓸 때는 “첫 순열”을 먼저 처리할지, do-while으로 첫 순열부터 돌지 정하면 됩니다.
std::vector<int> v = {1, 2, 3};
// next_permutation은 bool 반환
while (std::next_permutation(v.begin(), v.end())) {
// 순열 처리 (첫 순열 123은 여기서 처리 안 됨!)
}
// 마지막 순열(321) 다음은 없으므로 false, v는 123으로 돌아감문제 3: 중복
std::vector<int> v = {1, 1, 2};
std::sort(v.begin(), v.end());
do {
for (int x : v) {
std::cout << x;
}
std::cout << std::endl;
} while (std::next_permutation(v.begin(), v.end()));
// 112
// 121
// 211
// 중복 자동 처리같은 값이 여러 개 있으면 같은 수열은 한 번만 나옵니다. next_permutation이 사전순으로 “다음”만 만들기 때문에, 중복 조합을 따로 걸러 줄 필요가 없습니다.
문제 4: n이 크면 순열 개수가 폭발함
순열 개수는 n! 이라서 n이 조금만 커져도 매우 커집니다. n=10이면 약 362만, n=12면 약 4억 7천만이므로, “모든 순열”을 도는 방식은 n이 작을 때만(실무에서는 보통 10 이하) 사용하는 것이 좋습니다.
// n! 순열
// n=10: 3,628,800
// n=12: 479,001,600
// 큰 n은 비현실적
std::vector<int> v(15);
std::iota(v.begin(), v.end(), 1);
// ❌ 너무 많음
// do { /* ... */ } while (std::next_permutation(v.begin(), v.end()));활용 패턴 요약
| 목적 | 패턴 |
|---|---|
| 모든 순열 | sort 후 do { process(v); } while (next_permutation(...)); |
| k-순열 | 같은 루프에서 매번 v의 앞 k개만 사용 |
| 조합 (nCk) | vector<bool>로 뽑을 위치 표시 후, 이 벡터에 prev_permutation 적용 |
// 1. 모든 순열
std::sort(v.begin(), v.end());
do {
process(v);
} while (std::next_permutation(v.begin(), v.end()));
// 2. k-순열: 매번 앞 k개만 사용
do {
processFirst(v, k);
} while (std::next_permutation(v.begin(), v.end()));
// 3. 조합: selector의 순열로 "어떤 k개를 뽑을지" 표현
std::vector<bool> selector(n);
std::fill(selector.begin(), selector.begin() + k, true);
do {
processCombination(v, selector);
} while (std::prev_permutation(selector.begin(), selector.end()));실전에서 쓸 때 팁
- 반드시 정렬 먼저: 모든 순열을 돌려야 하면
std::sort(begin, end)후 루프를 돌리세요. 정렬하지 않으면 “현재 순서부터” 마지막 순열까지만 나옵니다. - 사전순 의미: “사전순 다음”이므로 문자열처럼 비교됩니다. 정수 벡터면 오름차순이 첫 순열, 내림차순이 마지막 순열입니다.
- n 크기: n이 10 이하일 때만 “전체 순열”을 도는 방식을 쓰는 것이 안전합니다. 11 이상이면 개수가 수천만~수억이 됩니다.
- 중복 원소: 같은 값이 있어도
next_permutation이 사전순으로 다음만 만들기 때문에, 동일한 수열은 한 번만 나와 별도 중복 제거가 필요 없습니다. - 커스텀 순서:
next_permutation(begin, end, comp)처럼 비교자comp를 넘기면, “사전순”을 그 비교 기준으로 적용할 수 있습니다.
FAQ
Q1: next_permutation과 prev_permutation의 차이는?
A: next_permutation은 사전순 다음 순열로 바꾸고, prev_permutation은 이전 순열로 바꿉니다. 마지막 순열에서 next_permutation을 호출하면 false가 나오고 범위는 첫 순열로 돌아갑니다.
Q2: 정렬을 꼭 해야 하나요?
A: 모든 순열을 한 번씩 돌리려면 반드시 먼저 정렬해야 합니다. 정렬하지 않으면 “현재 배치부터” 마지막 순열까지만 생성됩니다.
Q3: 중복된 원소가 있으면 같은 수열이 여러 번 나오나요?
A: 아니요. 사전순으로 “다음”만 생성하기 때문에 동일한 수열은 한 번만 나옵니다. 예: {1,1,2} → 112, 121, 211 세 가지만 생성됩니다.
Q4: n이 10보다 크면 어떻게 하나요?
A: n!이 급격히 커지므로 “전체 순열”을 도는 방식은 비현실적입니다. 부분만 필요하면 백트래킹이나 조합 생성 등 다른 방법을 고려하세요. STL 알고리즘 가이드에서 sort·partition 등과 함께 쓰는 패턴도 참고할 수 있습니다.
같이 보면 좋은 글 (내부 링크)
이 주제와 연결되는 다른 글입니다.
- C++ 알고리즘 | “STL algorithm” 핵심 정리
- C++ Algorithm Heap | “힙 알고리즘” 가이드
- C++ 범위 기반 for | “Range-based for” 가이드
실전 팁
실무에서 바로 적용할 수 있는 팁입니다.
디버깅 팁
- 문제가 발생하면 먼저 컴파일러 경고를 확인하세요
- 간단한 테스트 케이스로 문제를 재현하세요
성능 팁
- 프로파일링 없이 최적화하지 마세요
- 측정 가능한 지표를 먼저 설정하세요
코드 리뷰 팁
- 코드 리뷰에서 자주 지적받는 부분을 미리 체크하세요
- 팀의 코딩 컨벤션을 따르세요
실전 체크리스트
실무에서 이 개념을 적용할 때 확인해야 할 사항입니다.
코드 작성 전
- 이 기법이 현재 문제를 해결하는 최선의 방법인가?
- 팀원들이 이 코드를 이해하고 유지보수할 수 있는가?
- 성능 요구사항을 만족하는가?
코드 작성 중
- 컴파일러 경고를 모두 해결했는가?
- 엣지 케이스를 고려했는가?
- 에러 처리가 적절한가?
코드 리뷰 시
- 코드의 의도가 명확한가?
- 테스트 케이스가 충분한가?
- 문서화가 되어 있는가?
이 체크리스트를 활용하여 실수를 줄이고 코드 품질을 높이세요.
이 글에서 다루는 키워드 (관련 검색어)
C++, algorithm, permutation, combination, STL 등으로 검색하시면 이 글이 도움이 됩니다.
관련 글
- C++ Algorithm Copy |
- C++ Algorithm Count |
- C++ Algorithm Generate |
- C++ 알고리즘 |
- C++ Algorithm Heap |