C++ Algorithm Permutation | '순열 알고리즘' 가이드
이 글의 핵심
C++ next_permutation·prev_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++)
- 컴파일러 경고를 최대로 켜고(
-Wall -Wextra등 팀 합의), Sanitizer(ASan/UBSan)로 미정의 동작을 조기에 잡습니다. - 최적화는 프로파일 결과를 본 뒤에 합니다.
- STL
<algorithm>사용 시 반복자 무효화·비교자 일관성을 함께 검토합니다.
실전 체크리스트 (C++)
- 경고·정적 분석에서 새로운 이슈가 없는가?
- 빈 범위·단일 원소 등 경계 조건을 테스트했는가?
이 글에서 다루는 키워드 (관련 검색어)
C++, algorithm, permutation, combination, STL 등으로 검색하시면 이 글이 도움이 됩니다.
관련 글
심화 부록: 구현·운영 관점
이 부록은 앞선 본문에서 다룬 주제(「C++ Algorithm Permutation | ‘순열 알고리즘’ 가이드」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.
내부 동작과 핵심 메커니즘
flowchart TD A[입력·요청·이벤트] --> B[파싱·검증·디코딩] B --> C[핵심 연산·상태 전이] C --> D[부작용: I/O·네트워크·동시성] D --> E[결과·관측·저장]
sequenceDiagram participant C as 클라이언트/호출자 participant B as 경계(런타임·게이트웨이·프로세스) participant D as 의존성(API·DB·큐·파일) C->>B: 요청/이벤트 B->>D: 조회·쓰기·RPC D-->>B: 지연·부분 실패·재시도 가능 B-->>C: 응답 또는 오류(코드·상관 ID)
- 불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
- 결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
- 경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
- 백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.
프로덕션 운영 패턴
| 영역 | 운영 관점 질문 |
|---|---|
| 관측성 | 요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가 |
| 안전성 | 입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가 |
| 신뢰성 | 재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가 |
| 성능 | 캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가 |
| 배포 | 롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가 |
| 용량 | 피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가 |
스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.
확장 예시: 엔드투엔드 미니 시나리오
앞선 본문 주제(「C++ Algorithm Permutation | ‘순열 알고리즘’ 가이드」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.
- 입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
- 핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
- 실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
- 호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
- 부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.
handle(request):
ctx = newCorrelationId()
validated = validateSchema(request)
authorize(validated, ctx)
result = domainCore(validated)
persistOrEmit(result, idempotentKey)
recordMetrics(ctx, latency, outcome)
return result문제 해결(Troubleshooting)
| 증상 | 가능 원인 | 조치 |
|---|---|---|
| 간헐적 실패 | 레이스, 타임아웃, 외부 의존성, DNS | 최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검 |
| 성능 저하 | N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스 | 프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거 |
| 메모리 증가 | 캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납 | 상한·TTL·힙/FD 스냅샷 비교 |
| 빌드·배포만 실패 | 환경 변수, 권한, 플랫폼 차이, lockfile | CI 로그와 로컬 diff, 런타임·이미지 버전 핀 |
| 설정 불일치 | 프로필·시크릿·기본값, 리전 | 스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화 |
| 데이터 불일치 | 비멱등 재시도, 부분 쓰기, 캐시 무효화 누락 | 멱등 키·아웃박스·트랜잭션 경계 재검토 |
권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.
배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.