코딩 테스트 문제를 풀다 보면 이런 문장을 만나게 됩니다.
“ 순서를 고려한 경우의 수를 구하시오.” ” 순서에 상관없이 고를 수 있는 방법의 수는?”
이런 말이 나오면 순열 혹은 조합을 떠올려야 합니다. 그렇다면 어떤 상황에서 조합을 쓰고, 언제 순열을 써야 할까요?
순열이란 여러 개 중에서 일부를 골라서 줄 세우는 경우의 수 입니다. 즉, 순서까지 중요한 경우로 순서가 다르면 다른 경우로 셉니다.
오늘 풀게되는 문제와 같이, A, B 스킬로 공격을 하는 경우 AB로 하는 공격과 BA로 하는 공격은 분명히 다른 경우입니다. 즉, 순서가 다르면 다른 경우로 보는 것을 순열이라고 합니다.
function getPermutations(arr, selectNum) {
const result = [];
// 베이스 케이스: 1개만 뽑는다면 → 각 원소 자체가 하나의 순열
if (selectNum === 1) return arr.map(v => [v]);
// 배열의 각 원소를 하나씩 고정(fixed)해서 시작
arr.forEach((fixed, idx, origin) => {
// 현재 고른 원소를 제외한 나머지를 rest로 만든다
const rest = [...origin.slice(0, idx), ...origin.slice(idx + 1)];
// 나머지 원소들에서 (selectNum - 1)개를 뽑아 순열 생성 (재귀)
const perms = getPermutations(rest, selectNum - 1);
// 앞에 고정된 원소를 붙여서 전체 순열 만들기
const attached = perms.map(p => [fixed, ...p]);
// 결과에 추가
result.push(...attached);
});
return result;
}
getPermutations(['A', 'B', 'C'], 2);
// [['A', 'B'], ['A', 'C'], ['B', 'A'], ['B', 'C'], ['C', 'A'], ['C', 'B']]
조합이란 여러 개 중에서 일부를 골라만보는 경우의 수 입니다. 즉, 순서는 중요하지 않습니다.
가장 쉬운 예가 로또 번호입니다. 로또 번호를 추첨할 때 숫자의 순서와 상관없이 6개의 숫자를 뽑습니다. 12, 4, 30, 31, 7, 5 이든, 4, 5, 7, 12, 30, 31이든 순서는 중요하지 않습니다.
function getCombinations(arr, selectNum) {
const result = [];
// 베이스 케이스: 1개만 뽑는다면 → 각 원소 자체가 하나의 조합
if (selectNum === 1) return arr.map(v => [v]);
arr.forEach((fixed, idx, origin) => {
// 조합은 중복을 방지해야 하므로, 현재 원소 이후만 고려
const rest = origin.slice(idx + 1);
// 나머지 원소들에서 (selectNum - 1)개를 뽑아 조합 생성 (재귀)
const combs = getCombinations(rest, selectNum - 1);
// 고정된 원소를 앞에 붙여서 전체 조합 만들기
const attached = combs.map(c => [fixed, ...c]);
// 결과에 추가
result.push(...attached);
});
return result;
}
getCombinations(['A', 'B', 'C'], 2);
// [['A', 'B'], ['A', 'C'], ['B', 'C']]