-
[C++] 순열(Permutation) 조합(Combination) 알고리즘전공 공부/Algorithm 2020. 1. 28. 17:10728x90
백준에서 완전 탐색 문제를 풀다가
항상 조합과 순열을 만들 때 헷갈려서
아예 시간을 내어 정리하였다.
이 네 가지 알고리즘의 뼈대를 이해하면, 여러 방면에 쓰여서 좋은 거 같다.
이후 나오는 모든 코드의 n과 r은 다음과 같다. (n개 중에서 r개 선택)
#define n 4 #define r 3
1) 순열
순서를 따지고, 중복을 허용하지 않는다. (순서O, 중복X)
중복을 검사하기 위한 check 배열을 사용한다.
depth 를 하나씩 늘려가며, 배열에 하나씩 채우는 방법으로 재귀를 수행한다.
int pArr[r] = { 0, }; bool check[n + 1] = { false, }; void permutation(int depth){ if(depth == r){ printArray(pArr); return; } for(int i = 1; i <= n; i++){ if(!check[i]){ check[i] = true; pArr[depth] = i; permutation(depth + 1); check[i] = false; } } } int main(void){ cout << "순열 (순서o, 중복x)" << endl; permutation(0); return 0; }
(base) yunhongchan-ui-MacBook-Pro:week5 hongchanyun$ g++ permutation.cpp -o main.out (base) yunhongchan-ui-MacBook-Pro:week5 hongchanyun$ ./main.out 순열 (순서o, 중복x) 1 2 3 1 2 4 1 3 2 1 3 4 1 4 2 1 4 3 2 1 3 2 1 4 2 3 1 2 3 4 2 4 1 2 4 3 3 1 2 3 1 4 3 2 1 3 2 4 3 4 1 3 4 2 4 1 2 4 1 3 4 2 1 4 2 3 4 3 1 4 3 2
2) 중복 순열
순서를 따지고, 중복을 허용한다. (순서O, 중복O)
중복 검사를 제외하면 위의 순열 코드와 동일하다.
int dpArr[r] = { 0, }; void duplicatePermutation(int depth){ if(depth == r){ printArray(dpArr); return; } for(int i = 1; i <= n; i++){ dpArr[depth] = i; duplicatePermutation(depth + 1); } } int main(void){ cout << "중복 순열 (순서o, 중복o)" << endl; duplicatePermutation(0); return 0; }
(base) yunhongchan-ui-MacBook-Pro:week5 hongchanyun$ g++ permutation.cpp -o main.out (base) yunhongchan-ui-MacBook-Pro:week5 hongchanyun$ ./main.out 중복 순열 (순서o, 중복o) 1 1 1 1 1 2 1 1 3 1 1 4 1 2 1 1 2 2 1 2 3 1 2 4 1 3 1 1 3 2 1 3 3 1 3 4 1 4 1 1 4 2 1 4 3 1 4 4 2 1 1 2 1 2 2 1 3 2 1 4 2 2 1 2 2 2 2 2 3 2 2 4 2 3 1 2 3 2 2 3 3 2 3 4 2 4 1 2 4 2 2 4 3 2 4 4 3 1 1 3 1 2 3 1 3 3 1 4 3 2 1 3 2 2 3 2 3 3 2 4 3 3 1 3 3 2 3 3 3 3 3 4 3 4 1 3 4 2 3 4 3 3 4 4 4 1 1 4 1 2 4 1 3 4 1 4 4 2 1 4 2 2 4 2 3 4 2 4 4 3 1 4 3 2 4 3 3 4 3 4 4 4 1 4 4 2 4 4 3 4 4 4
728x903) 조합
순서를 따지지 않고, 중복을 허용하지 않는다. (순서X, 중복X)
반복문을 돌며, 모든 경우에 대해 선택하는 것은 위의 경우들과 같다.
그러나, 반복문의 시작 값은 이전에 선택한 값 + 1이 된다.
int cArr[r] = { 0, }; void combination(int depth, int next){ if(depth == r){ printArray(cArr); return; } for(int i = next; i <= n; i++){ cArr[depth] = i; combination(depth + 1, i + 1); } } int main(void){ cout << "조합 (순서x, 중복x)" << endl; combination(0, 1); return 0; }
(base) yunhongchan-ui-MacBook-Pro:week5 hongchanyun$ g++ combination.cpp -o main.out (base) yunhongchan-ui-MacBook-Pro:week5 hongchanyun$ ./main.out 조합 (순서x, 중복x) 1 2 3 1 2 4 1 3 4 2 3 4
4) 중복 조합
순서를 따지지 않고, 중복을 허용한다. (순서X, 중복O)
조합과 구현이 비슷하나,
반복문의 시작 값은 이전에 선택한 값이 된다.
int dcArr[r] = { 0, }; void duplicateCombination(int depth, int next){ if(depth == r){ printArray(dcArr); return; } for(int i = next; i <= n; i++){ dcArr[depth] = i; duplicateCombination(depth + 1, i); } } int main(void){ cout << "조합 (순서x, 중복o)" << endl; duplicateCombination(0, 1); return 0; }
(base) yunhongchan-ui-MacBook-Pro:week5 hongchanyun$ g++ permutation.cpp -o main.out (base) yunhongchan-ui-MacBook-Pro:week5 hongchanyun$ ./main.out 조합 (순서x, 중복o) 1 1 1 1 1 2 1 1 3 1 1 4 1 2 2 1 2 3 1 2 4 1 3 3 1 3 4 1 4 4 2 2 2 2 2 3 2 2 4 2 3 3 2 3 4 2 4 4 3 3 3 3 3 4 3 4 4 4 4 4
익숙해졌다면, 아래의 문제들을 풀어보며 완전히 자기 것으로 만들어보자.
https://www.acmicpc.net/workbook/view/2052
문제집: N과 M (baekjoon)
www.acmicpc.net
728x90