순열, 조합 문제를 풀다가 막혀서 혼자 공부하다가
이 참에 제대로 정리 해놓자 해서 작성한 글입니다.
순열?
이름 그대로 순서대로 뽑아서 줄을 세우는 걸 순열이라고 하지요. 순열을 기호로 나타낼 때는 순열을 뜻하는 영어 Permutation의 첫 글자 P를 이용해요. n개 중에서 r개를 뽑아서 줄을 세우는 걸 nPr이라고 합니다.
위는 순열을 구글링 했을 때 나오는 문장입니다.
줄을 세우는 걸 순열이라고 하는데 간단한 예시를 들어보겠습니다!
🥝 🍓 🍋
요기 키위, 딸기, 레몬이 있습니다.
세 가지 과일을 장바구니에 넣는 순서의 경우의 수를 모두 구해봅시다!
단, 과일은 하나씩 존재합니다.
이 경우에는 순열을 묻는 것입니다.
1. 🥝 🍓 🍋
2. 🍓 🥝 🍋1번과 2번은 순열을 구할 때 다른 경우에 해당합니다.
1번에는 키위가 첫 번째에 장바구니에 들어갔고,
2번에는 키위가 두 번째에 장바구니에 들어갔으니 당연히 다른 경우입니다.
이렇게 순서에 따라 다른 경우가 되는 상황에는 순열을 떠올리면 됩니다.
중복 순열?
그럼 중복 순열은 무엇일까요?
말 그대로 순열인데, 중복을 허용한다는 것입니다.
위의 과일을 예로 들자면 아까전의 예시는 과일들이 하나 씩만 있는 (중복 X) 경우 였다면,
중복 순열 같은 경우는 🥝 🍓 🍋 과일들중에서 3개를 뽑을 때,
과일들이 넉넉하게 3개씩 있다고 생각하면 됩니다.
🥝🥝🥝 🍓🍓🍓 🍋🍋🍋
그러면 요기서 3개만 장바구니에 넣는다 라고 생각하면 그 경우에는 중복 순열입니다.
1. 🥝 🍓 🍋
2. 🥝 🥝 🍓
3. 🥝 🥝 🍋
4. 🥝 🥝 🥝
5. 🥝 🍓 🍓
6. 🥝 🍓 🥝
...이렇게 과일이 하나가 아니라 여러 개가 있고, 장바구니에 들어간 순서에 따라 다른 경우가 된다면 중복 순열을 말하는 겁니다.
조합?
조합은 순열과 다른 개념으로 순서 차이가 중요하지 않습니다. 순열을 기호로 나타낼 때는 순열을 뜻하는 영어 Combination 첫 글자 C를 이용해요. n개 중에서 r개를 뽑아서 줄을 세우는 걸 nCr이라고 합니다.
순서 차이가 중요하지 않다. 라는 말은 순서가 달라도 똑같이 보겠다. 라는 말과 같은 말입니다.
🥝 🍓 🍋
역시 과일로 조합을 따지면 이해가 쉽습니다.
역시나 3개의 과일을 장바구니에 넣는데,
이번에는 들어간 순서를 따지는게 아니라 장바구니에 들어간 결과에 집중해봅시다.
이런 문제는 조합을 생각하시면 됩니다.
- 🥝 🍓 🍋
- 🍋 🥝 🍓
이런 경우에는 1번 장바구니와 2번 장바구니는
키위🥝, 딸기🍓, 레몬🍋이 똑같이 하나 씩 들어있는 같은 장바구니입니다.
장바구니에 들어간 순서를 따지면(순열) 다른 경우가 되겠지만,
장바구니에 넣은 결과만 따지자면(조합) 같은 경우입니다.
중복 조합?
중복 조합은 역시 중복을 허용한 조합이라는 얘기입니다.
🥝🥝🥝 🍓🍓🍓 🍋🍋🍋
장바구니에 3개의 과일을 넣는다고 생각할 때,
과일들이 넉넉히 3개씩 있다고 생각하면 됩니다.
1. 🥝 🥝 🍓
2. 🥝 🍓 🥝 1번 장바구니와 2번 장바구니는
키위🥝 2개, 딸기🍓 1개가 들어가있는 같은 장바구니입니다.
그래서 같은 경우로 봅니다.
코드로 짜봅시다.
이제 이론은 알았는데 코드로는 어떻게 짜면 될까요?
코드는 Javascript로 작성되었습니다!
각각에 대한 같은 문제들을 링크로 달아놓았으니 한번 씩 풀어보세요
순열과 조합에 대한 코드는 DFS를 이용했습니다.
순열 to Code
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
N = 3, M = 3일 때
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1위와 같이 순열을 뽑고자 할 때는 아래와 같이 작성하면 됩니다.
const N = 3;
const M = 3;
// 출력을 담아줄 변수
let result = '';
// 수를 담을 장바구니
const output = [];
// 중복을 허용하지 않기 때문에 이미 담긴 숫자인지 판단하기 위한 배열
const visited = new Array(N).fill(false);
function DFS(count) {
// 장바구니에 하나씩 담길 때마다 count가 늘어서
// M과 장바구니의 크기가 같아지면 리턴합니다.
if (count === M) {
result += `${output.join(' ')}\n`;
return;
}
for (let i = 0; i < N; i++) {
// 이미 들어간 수라면 넘어갑니다.
if (visited[i] === true) continue;
// 넣어줄 수를 들어갔다고 표시해줍니다.
visited[i] = true;
// 장바구니에 수를 넣습니다. (인덱스는 0부터니까 +1을 넣어줌)
output.push(i + 1);
// 위의 장바구니를 들고, 다른 수를 넣으러 다시 재귀 호출합니다.
dfs(count + 1);
// 재귀 호출이 끝났으니, 장바구니에서 수를 빼줍니다.
output.pop();
// 들어갔다고 표시한 것도 다시 돌려줍니다.
visited[i] = false;
}
}
DFS(0);해당 코드에 대한 자세한 설명은 링크에서 확인 할 수 있습니다.
중복 순열 to Code
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
그리고 중복을 허용합니다.
N = 3, M = 3일 때
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3위와 같이 중복 순열을 뽑고자 할 때는 아래와 같이 작성하면 됩니다.
const N = 3;
const M = 3;
let result = '';
const output = [];
// 중복 순열은 같은 수를 여러 개 넣어도 상관없으니,
// 중복됐는지 확인하는 visited 배열은 필요없습니다.
// 순열에서 visited 관련 로직을 뺀 로직이 중복 순열입니다.
function dfs(count) {
if (count === M) {
result += `${output.join(' ')}\n`;
return;
}
for (let i = 0; i < N; i++) {
output.push(i + 1);
dfs(count + 1);
output.pop();
}
}
DFS(0);조합 to Code
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
N = 3, M = 3일 때
1 2 3위와 같이 조합을 뽑고자 할 때는 아래와 같이 작성하면 됩니다.
const N = 3;
const M = 3;
let result = '';
const output = [];
const visited = new Array(N).fill(false);
function DFS(count, start) {
if (count === M) {
result += `${output.join(' ')}\n`;
return;
}
for (let i = start; i < N; i++) {
if (visited[i]) continue;
visited[i] = true;
output.push(i + 1);
dfs(count + 1, i);
output.pop();
visited[i] = false;
}
}
DFS(0, 0);순열과 다른 점은 재귀 함수에 매개 변수가 하나가 추가가 되었습니다.
start 라는 매개 변수의 역할은 for문이 어디서부터 시작되냐를 결정합니다.
해당 매개 변수가 필요한 이유는 조합은 순서를 따지는 게 아니기 때문에 이미 거쳐 온 수에 대해서는 다시 돌아갈 필요가 없습니다.
해당 코드에 대한 자세한 설명은 링크를 참고해주세요
중복 조합 to Code
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
그리고 중복을 허용합니다.
N = 3, M = 3일 때
1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3위와 같이 중복 조합을 뽑고자 할 때는 아래와 같이 작성하면 됩니다.
const N = 3;
const M = 3;
let result = '';
const output = [];
function DFS(count, start) {
if (count === M) {
result += `${output.join(' ')}\n`;
return;
}
for (let i = start; i < N; i++) {
output.push(i + 1);
dfs(count + 1, i);
output.pop();
}
}
DFS(0, 0);중복 순열과 같이, 중복을 따지는 visited 배열이 없는 중복 코드를 짜면
중복 조합이 됩니다.
출처
https://mathbang.net/545 (순열과 조합)
고등학교 확률과 통계에 나오는 것들이네요. 처음 배우는거라 잘 몰랐는데 글 덕분에 쉽게 이해했습니다!