DISCRETE MATH · CHAPTER 03
중급 · 50분경우의 수와 조합
알고리즘의 선택지를 세는 법
곱셈 법칙·순열·조합을 구분하고 작은 탐색 공간을 계산한다.
한 줄 정의
nCr = n! / (r!(n-r)!)CONCEPTS
개념을 문장으로 설명하기
곱셈 법칙
단계 A의 선택 수와 단계 B의 선택 수를 곱해 전체 경우의 수를 구하는 원리입니다.
예시
셔츠 3개와 바지 2개는 3×2=6가지 조합입니다.
CHECK각 단계가 순서대로 모두 일어날 때 곱한다.
순열
서로 다른 n개 중 r개를 순서 있게 고르는 경우의 수입니다.
예시
금·은·동 3명을 5명 중에서 뽑는 것은 순서가 중요합니다.
CHECKnPr = n!/(n-r)!
조합
서로 다른 n개 중 r개를 순서 없이 고르는 경우의 수입니다.
예시
팀원 5명 중 2명을 뽑는 경우는 {A,B}와 {B,A}가 같습니다.
CHECKnCr = nC(n-r)
GUIDED PRACTICE
비밀번호 경우의 수
영문 대문자 26개로 길이 4 비밀번호를 만들고 문자는 중복 가능합니다.
- 각 자리마다 26개 선택이 있습니다.
- 자리가 4개이므로 26×26×26×26입니다.
- 순서가 다른 문자열은 다른 비밀번호이므로 곱셈 법칙을 적용합니다.
결론
총 26⁴가지입니다. 경우의 수는 보안에서 무차별 대입 난이도와 연결됩니다.
ACTIVE RECALL · 4 STEPS
가리고, 말하고, 확인하기
읽기만 하지 말고 답을 떠올린 뒤 펼쳐 보세요.
01 · 정의 회상
“곱셈 법칙”을(를) 보지 않고 한 문장으로 정의해 보세요.
02 · 비교 설명
“순열”이(가) 필요한 상황을 예시와 함께 설명해 보세요.
03 · 핵심 점검
nCr = nC(n-r)
04 · 풀이 재현
“비밀번호 경우의 수”의 결론을 보기 전에 풀이 순서를 3단계로 다시 적어 보세요.
WORKBOOK · STEP BY STEP
개념 확인 문제
정답을 고르고 해설로 사고 과정을 확인하세요.
01
5명 중 순서 없이 2명을 뽑는 경우의 수는?
02
A,B,C 세 글자를 모두 한 번씩 사용해 만드는 순서 있는 문자열 수는?
03
조합을 쓰는 가장 적절한 상황은?
SPEAK IT OUT
면접 1분 답변 연습
순열과 조합의 차이를 서비스·알고리즘의 실제 상황 하나씩으로 설명해 보세요.
답변할 때는 정의 → 이유 → 짧은 예시 순서로 말해 보세요.공식·표준 자료로 더 읽기
Python docs · itertools원문 열기 ↗permutations와 combinations로 경우의 수를 코드로 실험할 수 있습니다.