핵심 답 먼저
순서나 역할이 달라지면 다른 결과인 문제는 순열, 선택된 구성원만 중요하면 조합을 사용합니다. 여러 단계를 모두 거치면 곱의 법칙, 서로 겹치지 않는 선택지 중 하나를 고르면 합의 법칙이 출발점입니다. 중복 허용·같은 원소·원형 배치·제약 조건은 기본 공식에 바로 넣지 말고 무엇을 같은 결과로 볼지 먼저 정해야 합니다.
합의 법칙과 곱의 법칙에서 시작하기
MIT Mathematics for Computer Science 공개 강의는 순열·조합, 계수 원리, 이산확률을 컴퓨터과학의 핵심 이산수학 주제로 다룹니다. 공식보다 먼저 전체 경우를 겹치지 않는 부분으로 나눌지, 연속된 선택 단계로 나눌지 결정해야 합니다.
| 질문 | 법칙 | 예시 |
|---|---|---|
| A 또는 B 중 하나이며 두 경우가 겹치지 않는가 | 합의 법칙 | 버스 3개 노선 또는 지하철 2개 노선 → 5가지 |
| 첫 선택 뒤 두 번째 선택을 모두 거치는가 | 곱의 법칙 | 상의 3벌 × 바지 2벌 × 신발 2켤레 → 12가지 |
선택지가 겹치면 단순히 더하면 안 된다
A와 B가 겹칠 수 있다면 |A ∪ B| = |A| + |B| - |A ∩ B|처럼 중복 집계를 빼야 합니다. 예를 들어 1부터 100까지 2의 배수 또는 5의 배수의 개수는 50 + 20 – 10 = 60개입니다. 10의 배수 10개를 두 번 셌기 때문에 한 번 빼는 것입니다.
순열과 조합은 순서가 결과를 바꾸는지로 고른다
| 상황 | 표현 | 공식 |
|---|---|---|
| n개를 모두 순서 있게 배열 | n! |
n × (n-1) × ... × 1 |
| n개 중 r개를 순서 있게 선택 | nPr |
n! / (n-r)! |
| n개 중 r개를 순서 없이 선택 | nCr |
n! / (r!(n-r)!) |
5명 중 회장·부회장·총무를 정한다
→ 역할이 바뀌면 다른 결과
→ 5P3 = 5 × 4 × 3 = 60
5명 중 프로젝트 팀원 3명만 뽑는다
→ 뽑힌 세 사람의 나열 순서는 같은 결과
→ 5C3 = 10문제에 ‘배열’이나 ‘선택’이라는 단어가 있는지만 보면 부족합니다. 좌석 번호, 등수, 역할, 비밀번호 자리처럼 위치가 의미를 가지면 순열입니다. 위원회 구성처럼 선택된 집합만 중요하면 조합입니다.
중복·같은 원소·원순열·제약 조건 구분하기
| 유형 | 핵심 질문 | 대표 계산 |
|---|---|---|
| 중복순열 | 각 자리에 같은 선택지를 다시 쓸 수 있는가 | n개 선택지로 r자리 → nʳ |
| 같은 원소가 있는 순열 | 서로 구별되지 않는 원소가 몇 개씩 있는가 | n!/(n₁!n₂!...) |
| 원순열 | 회전만 같은 배치로 보는가 | 서로 다른 n명 → (n-1)! |
| 중복조합 | 종류는 같아도 여러 개 고를 수 있는가 | n종류에서 r개 → C(n+r-1,r) |
A, A, B, C를 일렬로 배열
→ 4! / 2! = 12
숫자 0~9로 길이 3의 비밀번호 작성
→ 첫 자리에 0을 허용하면 10³ = 1000
→ 세 자리 자연수라면 첫 자리는 1~9이므로 9 × 10 × 10 = 900
서로 다른 5명을 원탁에 앉힘
→ 회전만 같은 배치로 보면 (5-1)! = 24합이 정해진 정수해는 0 허용 여부를 먼저 본다
x + y + z = 5
x, y, z ≥ 0인 정수
→ C(5 + 3 - 1, 3 - 1) = C(7, 2) = 21
x, y, z ≥ 1인 정수
→ x'=x-1, y'=y-1, z'=z-1
→ x' + y' + z' = 2
→ C(2 + 3 - 1, 3 - 1) = C(4, 2) = 6이항계수와 확률을 경우의 수로 연결하기
이항정리의 계수는 n개 위치 중 x를 고를 위치를 선택하는 조합입니다. 따라서 (x+y)ⁿ에서 xⁿ⁻ʳyʳ의 계수는 nCr입니다. 이 관점을 알면 파스칼 삼각형과 조합의 점화식도 자연스럽게 연결됩니다.
(x + y)³
= x³ + 3x²y + 3xy² + y³
계수: C(3,0), C(3,1), C(3,2), C(3,3)
= 1, 3, 3, 1고전적 확률 P(A)=|A|/|S|는 표본공간 S의 각 결과가 같은 가능성을 가질 때 사용할 수 있습니다. 결과가 균등하지 않다면 경우의 수만 세어 나눈 값은 실제 확률이 아닙니다. 조건부확률은 A가 일어났다는 정보로 표본공간을 좁힌 뒤 P(B|A)=P(A∩B)/P(A)로 계산합니다.
점화식과 비둘기집 원리까지 연결하기
조합은 이전 크기의 문제로 나눌 수 있어 점화식과 잘 연결됩니다. 특정 원소를 포함하는 경우와 포함하지 않는 경우로 나누면 C(n,r)=C(n-1,r-1)+C(n-1,r)입니다. 두 경우는 겹치지 않고 전체를 빠짐없이 덮습니다.
C(6,2)
= C(5,1) + C(5,2)
= 5 + 10
= 15비둘기집 원리는 n개 물건을 k개 상자에 나누면 어떤 상자에는 적어도 ⌈n/k⌉개가 들어간다는 보장입니다. 25명을 7개 요일로 분류하면 어떤 요일에는 적어도 4명이 있습니다. 이 원리는 어느 상자인지는 알려주지 않지만 겹침이 반드시 존재한다는 사실을 증명합니다.
JavaScript BigInt로 큰 조합 값을 안전하게 계산하기
JavaScript Number는 안전한 정수 범위가 제한되므로 큰 팩토리얼과 조합을 정확히 계산할 때는 BigInt를 사용합니다. 중요한 경계는 Number로 바꾼 뒤 BigInt로 변환하면 이미 잃은 정밀도를 복구할 수 없다는 점입니다. 예를 들어 숫자 리터럴 9007199254740993은 BigInt 변환 전에 반올림될 수 있습니다. 따라서 폼·URL·JSON에서 받은 십진 정수 문자열을 그대로 검증한 뒤 BigInt(string)으로 파싱합니다. ECMAScript의 BigInt 명세처럼 BigInt는 Number와 별도 숫자 타입이므로 산술식에서도 두 타입을 섞지 않습니다.
function parseNonNegativeInteger(value, name) {
if (typeof value !== 'string' || !/^(0|[1-9]\d*)$/.test(value)) {
throw new TypeError(`${name} must be a non-negative decimal string`);
}
return BigInt(value);
}
function nCr(nText, rText) {
const n = parseNonNegativeInteger(nText, 'n');
let r = parseNonNegativeInteger(rText, 'r');
if (r > n) return 0n;
r = r < n - r ? r : n - r;
let result = 1n;
for (let i = 1n; i <= r; i += 1n) {
result = (result * (n - r + i)) / i;
}
return result;
}
function nPr(nText, rText) {
const n = parseNonNegativeInteger(nText, 'n');
const r = parseNonNegativeInteger(rText, 'r');
if (r > n) return 0n;
let result = 1n;
for (let i = 0n; i < r; i += 1n) {
result *= n - i;
}
return result;
}
console.log(nCr('6', '2').toString()); // 15
console.log(nPr('5', '3').toString()); // 60
console.log(nCr('100', '50').toString());
// 100891344545564193334812497256
console.log(nCr('9007199254740993', '1').toString());
// 9007199254740993 — Number를 거치지 않아 정확함함수는 문자열만 받으며 Number 입력, 음수, 지수 표기, 소수, 앞자리 0이 붙은 문자열을 거부합니다. 나눗셈 순서를 바꾸면 중간에 정수가 아닌 값이 생길 수 있으므로 위 코드는 매 단계에서 정확히 나누어지는 곱셈 순서를 사용합니다. 검증할 때는 C(n,0)=1, C(n,n)=1, C(n,r)=C(n,n-r), Number.MAX_SAFE_INTEGER보다 큰 문자열과 작은 손계산 값을 함께 비교합니다.
공식을 적용하기 전에 확인할 예외
- 첫 자리 0: 비밀번호와 자연수는 같은 숫자 배열이어도 허용 조건이 다릅니다.
- 원형 대칭: 회전만 같은지, 뒤집기까지 같은지에 따라 단순
(n-1)!을 쓸 수 없는 경우가 있습니다. - 중복 사건: ‘또는’이라고 무조건 더하지 말고 교집합이 있는지 확인합니다.
- 적어도 하나: 직접 여러 경우를 더하기보다 전체에서 하나도 없는 경우를 빼는 여사건이 간단할 수 있습니다.
- 확률의 균등성: 표본공간 원소가 같은 확률인지 확인한 뒤 경우의 수 비율을 사용합니다.
- 수치 범위: 큰 정수는 Number의 반올림을 피하고 BigInt 또는 임의정밀도 도구로 검증합니다.
결론과 내부 학습 경로
결론: 경우의 수 문제는 결과의 동일성 정의 → 합 또는 곱으로 분해 → 순서·중복·제약 확인 → 작은 사례와 대칭성으로 검산하는 순서가 안정적입니다. 공식을 먼저 고르면 같은 원소, 첫 자리 0, 원형 대칭 같은 예외를 놓치기 쉽습니다.
- 이산수학 집합과 부분집합에서 표본공간과 원소 수를 먼저 익힙니다.
- 곱집합과 동치관계로 같은 결과를 묶는 기준을 확장합니다.
- 직접증명과 귀납법으로 점화식과 계수 항등식을 검증합니다.
- 그래프 이론 기본 개념에서 경로와 트리의 경우의 수로 응용합니다.