코딩테스트 공부를 하면서 두 개념을 복습하고자 정리하려고 한다.
순열과 조합은 보통 부분집합, 경우의 수 구하기 등 다양한 알고리즘 문제에 많이 나온다.
먼저 코드를 구현해보자.
모든 경우는 3C2로 가정했다.
1. 순열
n개의 값이 있고 이중 r개의 값의 순열을 구하고싶다.
우선 n개의 값이 있는 배열과, 이 배열을 방문했는지 여부를 체크할 bool 배열
그리고 r개를 담을 배열이 필요하다.
재귀함수를 이용하며, 탈출 조건을 depth == r로 설정한다. (내가 r개 만큼 뽑았다! 의미)
r개만큼 뽑는 방법은 n만큼 반복문을 통해 탐색한다.
이 때 현재 인덱스에 대해 방문하지 않았다면 방문 여부 체크 후
r개만큼 담을 배열에 값을 추가한다. (이때 depth를 인덱스로 해야한다. n개가 아닌 r개이기 때문!)
그 후 다시 재귀함수를 들어간다.
탈출 조건을 수행하고 원하는 함수(기능)을 실행한 후 제일 최근 방문한 방문 여부를 해제한다.
즉, 재귀함수가 실행되는 순서는
(1,2) -> print -> 함수 종료 -> 2 방문 여부 false -> (1,3) -> print -> 함수 종료 -> 3 방문 여부 false -> (2,1) ....이다.
// 순열
#include <iostream>
using namespace std;
int arr[3];
int save[2];
bool check[3];
void print() {
for (auto p : save) {
cout << p << " ";
}
cout << "\n";
}
void permutation(int depth) {
// 탈출 조건
if (depth == 2) {
print();
return;
}
for (int i = 0; i < 3; i++) {
if (!check[i]) {
check[i] = true;
save[depth] = arr[i];
permutation(depth + 1);
check[i] = false;
}
}
}
int main() {
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
permutation(0);
return 0;
}출력 : (1,2), (1,3), (2,1), (2,3), (3,1), (3,2)
2. 중복 순열
순열에서 중복을 피하기 위해 방문 여부를 확인했다.
그러면 중복을 원한다면 방문 여부를 하지 않으면 된다.
// 중복 순열
#include <iostream>
using namespace std;
int arr[3];
int save[2];
void print() {
for (auto p : save) {
cout << p << " ";
}
cout << "\n";
}
void permutation(int depth) {
// 탈출 조건
if (depth == 2) {
print();
return;
}
for (int i = 0; i < 3; i++) {
save[depth] = arr[i];
permutation(depth + 1);
}
}
int main() {
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
permutation(0);
return 0;
}출력 : (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)
3. 조합
조합은 순서를 고려하지 않고 뽑는 경우의 수다.
이전 순열에서는 depth 라는 매개변수 하나만 입력받아 재귀함수 안에서 사용하였다.
하지만 조합은 함수 combination에서
depth는 현재까지 선택된 원소의 수를 나타내고 cur는 현재 원소의 인덱스를 나타낸다.
즉, cur를 사용하여 이전에 선택한 원소 이후의 원소만 선택할 수 있도록 조합을 생성한다.
이것은 선택한 원소의 순서를 무시하고 원소의 개수만을 고려하는 조합의 특성을 반영한다.
// 조합
#include <iostream>
using namespace std;
int arr[3];
int save[2];
void print() {
for (auto p : save) {
cout << p << " ";
}
cout << "\n";
}
void combination(int depth,int cur) {
// 탈출 조건
if (depth == 2) {
print();
return;
}
for (int i = cur; i < 3; i++) {
save[depth] = arr[i];
combination(depth + 1, i + 1);
}
}
int main() {
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
combination(0,0);
return 0;
}출력 : (1,2), (1,3), (2,3)
4. 중복 조합
위에서 설명한 중복 순열과 비슷하다.
조합을 구현한 코드에서 방문 여부 상관하지 않고 시작 인덱스를 이전에 방문한 인덱스 그대로 들어가면 된다.
// 중복 조합
#include <iostream>
using namespace std;
int arr[3];
int save[2];
void print() {
for (auto p : save) {
cout << p << " ";
}
cout << "\n";
}
void combination(int depth, int cur) {
// 탈출 조건
if (depth == 2) {
print();
return;
}
for (int i = cur; i < 3; i++) {
save[depth] = arr[i];
combination(depth + 1, i);
}
}
int main() {
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
combination(0, 0);
return 0;
}