순열과 조합
조합이란 서로 다른 n개의 원소에서 r (단, 0<r≤n) 개를 중복 없이, 순서를 고려하지 않고 선택하는 것이에요.
순열이란, 순열은 어떤 집합의 원소들을 각각 특정한 순서로 배열하는 것입니다.
간단하게 ['A', 'B', 'C']에서 2개 뽑기로 예시를 들어볼게요. 조합의 경우 AB, AC, BC로 총 3가지를 뽑을 수 있습니다. AB를 뽑았으면 BA는 같은 거니까 동일하게 보는거죠. 하지만 순열은 순서까지 따져서 2개 뽑아야 해요. AB, BA, AC, CA, BC, CB로 총 6가지 입니다. 즉 순서까지 따지냐, 안따지냐 인거에요!
조합 핵심 원리
"ABCD"에서 2개를 뽑는다면 이런식으로 나열할 수 있어요.
A를 선택 → 나머지 BCD에서 1개 더 선택 → AB, AC, AD
B를 선택 → 나머지 CD에서 1개 더 선택 → BC, BD
C를 선택 → 나머지 D에서 1개 더 선택 → CD조합의 핵심은 하나를 고정하고, 그 뒤에서만 나머지를 선택하는 것입니다.
조합 단계별로 이해하기
1단계: 가장 간단한 경우 (2개 뽑기)
function get2Combinations(arr) {
const result = [];
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
result.push([arr[i], arr[j]]);
}
}
return result;
}
// ["A", "B", "C", "D"]// → [["A","B"], ["A","C"], ["A","D"], ["B","C"], ["B","D"], ["C","D"]]2단계: 3개 뽑기도 같은 원리
function get3Combinations(arr) {
const result = [];
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
for (let k = j + 1; k < arr.length; k++) {
result.push([arr[i], arr[j], arr[k]]);
}
}
}
return result;
}3단계: 원리 분석
getCombinations(['A', 'B', 'C', 'D'], 2)
// 1번째: fixed='A', rest=['B','C','D']
// → ['B','C','D']에서 1개 뽑기 → ['B'], ['C'], ['D']
// → ['A','B'], ['A','C'], ['A','D']
// 2번째: fixed='B', rest=['C','D']
// → ['C','D']에서 1개 뽑기 → ['C'], ['D']
// → ['B','C'], ['B','D']
// 3번째: fixed='C', rest=['D']
// → ['D']에서 1개 뽑기 → ['D']
// → ['C','D']
// 4번째: fixed='D', rest=[]
// → 빈 배열이라 조합 없음
// 결과: [['A','B'], ['A','C'], ['A','D'], ['B','C'], ['B','D'], ['C','D']]조합 알고리즘 (재귀)
위 패턴을 보면 "선택 → 나머지에서 선택"이 반복되는 것을 볼 수 있어요. 바로 재귀로 만들 수 있는 거죠!
조합 함수의 핵심은 다음과 같아요
- 1.하나를 고정 (fixed)
- 2.나머지에서 (size-1)개 뽑기 (재귀)
- 3.고정한 것과 합치기
function getCombinations(arr, size) {
const result = [];
// 1개만 뽑으면 각각이 순열
if (size === 1) {
return arr.map(el => [el]);
}
// 각 원소를 고정
arr.forEach((fixed, index) => {
// 고정된 원소 뒤의 나머지 배열
const rest = arr.slice(index + 1);
// 나머지에서 (size-1)개 뽑기
const combinations = getPermutations(rest, size - 1);
// 고정된 원소와 조합
const attached = permutations.map(combo => [fixed, ...combo]);
result.push(...attached);
});
return result;
}코드로 보면 잘 이해가 안가서 예시를 자세히 들어볼게요 !
재귀 흐름 이해하기 ) ['A', 'B', 'C', 'D']에서 3개 뽑기
getCombinations(['A','B','C','D'], 3) 시작
│
├─ fixed='A', rest=['B','C','D']
│ └─ getCombinations(['B','C','D'], 2) 호출 ←─ 재귀 들어감
│ │
│ ├─ fixed='B', rest=['C','D']
│ │ └─ getCombinations(['C','D'], 1) 호출 ←─ 재귀 들어감
│ │ └─ return [['C'], ['D']] (size=1이라 바로 리턴)
│ │ ← 돌아옴
│ │ └─ ['B']와 합쳐서 [['B','C'], ['B','D']]
│ │
│ ├─ fixed='C', rest=['D']
│ │ └─ getCombinations(['D'], 1) 호출 ←─ 재귀 들어감
│ │ └─ return [['D']]
│ │ ← 돌아옴
│ │ └─ ['C']와 합쳐서 [['C','D']]
│ │
│ └─ return [['B','C'], ['B','D'], ['C','D']]
│ ← 돌아옴
│ └─ ['A']와 합쳐서 [['A','B','C'], ['A','B','D'], ['A','C','D']]
│
├─ fixed='B', rest=['C','D']
│ └─ getCombinations(['C','D'], 2) 호출
│ └─ ... (위와 비슷한 과정)
│ └─ return [['C','D']]
│ └─ ['B']와 합쳐서 [['B','C','D']]
│
├─ fixed='C', rest=['D']
│ └─ getCombinations(['D'], 2) 호출
│ └─ ['D']에서 2개를 뽑을 수 없음 → return []
│ └─ 결과 없음
│
└─ 최종 result = [['A','B','C'], ['A','B','D'], ['A','C','D'], ['B','C','D']]순열 알고리즘 (재귀)
순열 알고리즘은 조합 알고리즘과 한 줄만 달라요. 조합은 나머지 배열을 현재 이후만 사용 (순서를 고려하지 않으므로 중복 제거)하고 순열은 나머지 배열을 현재만 빼고 앞뒤 전부 사용(순서를 고려하므로)하기 때문이에요.
function getPermutations(arr, size) {
const result = [];
// 1개만 뽑으면 각각이 순열
if (size === 1) {
return arr.map(el => [el]);
}
// 각 원소를 고정
arr.forEach((fixed, index) => {
// 현재 원소만 빼고 나머지 전부 (앞뒤 다)
const rest = [...arr.slice(0, index), ...arr.slice(index + 1)];
// 나머지에서 (size-1)개 뽑기
const permutations = getPermutations(rest, size - 1);
// 고정된 원소와 조합
const attached = permutations.map(perm => [fixed, ...perm]);
result.push(...attached);
});
return result;
}마치며
알고리즘을 외우기만 했었는데 자세히 알고리즘을 뜯어 원리를 알고보니 결국은 단순한 원리의 반복이었어요. 하나를 고정하고, 나머지에서 다시 고정 후 더이상 쪼갤 수 없을때 다시 돌아와서 합치는 흐름이었습니다. 문제만 봤을때는 이해가 안됐는데 큰 흐름을 보니 그림이 그려졌습니다 🖌️