참고
https://blog.uniony.me/cpp/next_permutation/
https://zoosso.tistory.com/1088
백준 '부분수열의 합' 문제를 풀면서 직접 조합 알고리즘을 구현하던 중 STL에서 기본적으로 제공하는 next_permutation 함수를 알게되었다.
DFS 탐색을 활용하여 직접 조합 알고리즘을 구현하는 것은 익숙 해진다면 크게 불편한 점을 없지만, 코딩테스트와 같은 실전에서 어떤 다양한 상황이 생길지 모르기 때문에 다양한 무기를 가지고 있으면 좋을 것 같아서 관련 내용을 정리하게 되었다.
-
가장 먼저 next_permutation 함수는 algorithm 헤더에 포함되어 있다.
C++ 레퍼런스 페이지를 보면 next_permutation 함수 구조에 대해 자세히 알 수 있지만, 시간 관계상 중요한 포인트만 빠르게 정리하면1) 인자로 받은 수/문자열(vector, 배열)에서 다음 순열을 구하면 true를 반환하고,
2) 다음 순열이 없거나 다음에 구한 순열이 이전 순열보다 작으면 false를 반환한다.가장 중요한 것은 2번 조건에 의해 인자로 받는 수/문자열은 항상 오름차순 정렬(=sort())되어 있어야 한다는 것이다. 이것이 지켜지지 않으면 모든 순열이 출력되지 않는 상황이 발생한다.
next_permutation 함수를 사용하는 기본적인 구조는 다음과 같다.
do {
sum = 0;
for (int i = 0; i < comb.size(); i++) {
if (comb[i] == 1) {
sum += in_num[i];
}
}
if (sum == s) {
cnt++;
}
} while (next_permutation(comb.begin(), comb.end()));위의 코드를 보면, 기본적으로 next_permutation 함수를 사용하기 위해서는 do while문 구조와 함께 사용하는 것을 알 수 있다.
while (next_permutation(comb.begin(), comb.end())); 부분을 통해 주어진 배열에 대한 순열을 매번 출력하면, do 문 내부에서 해당 순열을 통해 어떤 동작을 수행할 것인지 작성하는 구조이다.
- next_permutation 함수가 오름차순으로 순열을 출력했다면, 번외판으로 내림차순으로 순열을 출력해주는 prev_permutation 함수도 존재한다. 단, next_permutation 함수가 오름차순으로 정렬된 수/문자열을 필요로 했다면, prev_permutation 함수는 내림차순으로 미리 정렬된 수/문자열을 필요로 한다.
이외 사용법은 next_permutation 함수와 모두 동일하다.
-
C++ STL에서 기본 제공하는 next_permutation 함수를 활용해서 조합을 구현 할 수 있다.
조합은 순열과 달리 숫자 조합에서 순서를 고려하지 않기 때문에 next_permutation 함수에 인자로 주는 배열을 오직 0과 1로만 구성되게 한다. 0이면 고르지 않고, 1이면 고르는 경우로 생각할 수 있다.
이때, 0과 1로 구성된 배열 역시 오름차순 정렬이 필요하다.크기가 n인 배열에서 1이 r개이고, 나머지는 0으로 채운 배열을 정렬 후 next_permutation 함수의 인자로 주면, next_permutation 함수는 해당 배열에 대해 순열을 출력하게 된다.
하지만 배열의 성분이 0과 1로만 구성됐고, next_permutation은 중복되는 성분을 고려하기 때문에, 0과 1로만 구성된 배열을 인자로 받은 next_permutation의 출력은 조합으로 생각할 수 있다.
이후, do 문 내부에서 조합을 구하고자 하는 원래 배열의 인덱스와 mapping 하여 원하는 조합을 출력할 수 있다.
0과 1로 구성된 배열을 통해 구현한 조합 알고리즘은 다음과 같이 구성할 수 있다.
int sum;
vector<int> comb;
// comb 배열에 원하는 조합의 성분 개수만큼 1 삽입
for (int i = 0; i < n; i++) {
if (i <= n - 1 - num) {
comb.push_back(0);
}
else {
comb.push_back(1);
}
}
// comb 배열에 대해 순열에서 사용한 알고리즘 구조 그대로 사용
// do 문 내에서 조합을 구하려는 실제 수열(in_num[])의 인덱스를 mapping하여 조합 출력
do {
sum = 0;
for (int i = 0; i < comb.size(); i++) {
if (comb[i] == 1) {
sum += in_num[i];
}
}
if (sum == s) {
cnt++;
}
} while (next_permutation(comb.begin(), comb.end()));조합 알고리즘을 구현할 때, DFS 탐색을 사용하지 않고 next_permutation 함수를 통해 구현한 문제는 다음 링크에서 확인할 수 있다.
https://velog.io/@cyj2540/%EB%B6%80%EB%B6%84%EC%88%98%EC%97%B4%EC%9D%98-%ED%95%A92
