13강 / 20강
세는 법 — 곱할 때와 더할 때
경우의 수의 두 가지 기본기
이산수학의 절반은 세는 일입니다. 비밀번호가 몇 가지나 가능한지, IP 주소가 몇 개나 있는지, 테스트 케이스가 몇 개나 필요한지 — 전부 세는 문제예요.
그리고 세는 법의 거의 전부는 다음 두 가지에서 나옵니다.
구별하는 방법은 간단합니다. "그리고"면 곱하고, "또는"이면 더합니다. 상의를 고르고 그리고 하의를 고르면 곱하기. 버스를 타거나 또는 지하철을 타면 더하기.
8강의 곱집합 |A × B| = |A| × |B| 가 곧 곱의 법칙입니다.
Python
브라우저에서 실행
🎮 가짓수를 나무로 펼쳐 보세요
단계마다 선택지 수를 바꿔 보세요. 가지가 몇 갈래로 뻗는지, 그리고 잎이 몇 개가 되는지가 곧 경우의 수입니다.
비밀번호는 몇 가지일까
곱의 법칙이 가장 실감 나는 곳입니다. 자리마다 쓸 수 있는 글자 수를 계속 곱하면 돼요.
- 숫자 4자리 :
10 × 10 × 10 × 10 = 10,000가지 - 소문자 8자리 :
26⁸ ≈ 2,090억가지 - 대소문자+숫자+기호 12자리 :
94¹² ≈ 4.7 × 10²³가지
글자 종류를 늘리는 것보다 길이를 늘리는 쪽이 훨씬 강력합니다.
길이는 지수에 들어가니까요 (12강의 2ⁿ과 같은 이유).
길이가 4씩 늘 때마다 자릿수가 어떻게 뛰는지 보세요.
Python
브라우저에서 실행
겹침을 한 번 빼 주면 맞습니다.
Python
브라우저에서 실행
여집합으로 세기 — '적어도 하나'의 요령
"동전 10개를 던져 적어도 하나가 앞면일 확률"을 직접 세려면 1개일 때, 2개일 때… 열 가지를 다 세야 합니다. 하지만 반대를 세면 한 번에 끝나요.
(적어도 하나) = (전체) − (하나도 없는 경우)
2¹⁰ − 1 = 1023. 전부 뒷면인 한 가지만 빼면 됩니다.
"적어도"라는 말이 보이면 여집합을 떠올리세요.
'적어도'는 여집합으로. 셈 문제의 가장 흔한 요령입니다.
Python
브라우저에서 실행
🤔 확인 문제
메뉴판에 애피타이저 3종, 메인 5종, 디저트 2종이 있습니다. 코스로 하나씩 고르면 몇 가지?
해설 단계가 이어지므로 곱합니다 —
3 × 5 × 2 = 30가지. 만약 "셋 중 하나만 고른다"였다면 갈리는 경우이므로 3 + 5 + 2 = 10가지였을 거예요.🤔 확인 문제
비밀번호를 더 안전하게 만드는 데 효과가 큰 쪽은?
해설 가짓수는
(종류)(길이) 입니다. 길이는 지수에 있어서 훨씬 세게 작용해요. 26⁸ ≈ 2천억 이지만 26¹² ≈ 9경 — 종류를 36으로 늘린 36⁸ ≈ 2.8조 보다 압도적입니다.🤔 확인 문제
주사위 2개를 던져 적어도 하나가 6인 경우의 수는?
해설 여집합으로 셉니다 — 전체
36에서 둘 다 6이 아닌 5 × 5 = 25를 빼면 11가지. 그냥 6 + 6 = 12로 세면 (6,6)을 두 번 센 것이 됩니다.