딸기당근수박참외메론 줄 세우기
컴퓨터는 1초에 10억 번쯤 계산하니, 답을 모르면 모든 경우를 다 해 보면 될까요? 네 자리 비밀번호는 순식간에 다 넣어 보지만, 카드 30장을 늘어놓는 방법을 다 해 보려면 우주의 나이보다 오래 걸립니다. 해 보기 전에 경우가 몇 가지인지 세는 방법을 알아봅시다.
상의가 3벌, 하의가 2벌이면 옷을 입는 방법은 3 × 2 = 6가지입니다. 상의를 하나 고를 때마다 하의를 2가지로 고를 수 있기 때문입니다. 이처럼 여러 단계를 차례로 고를 때 각 단계의 가짓수를 곱하면 전체 가짓수가 됩니다. 이를 곱의 법칙(rule of product)이라 합니다.
숫자만 사용한 네 자리 비밀번호는 자리마다 10가지라 10 × 10 × 10 × 10 = 10,000가지입니다. 비트 n개도 자리마다 2가지라 2n가지입니다. 그래서 8비트는 256가지 수를 나타냅니다.
피자 재료 n가지 중 원하는 것만 골라 올리는 방법은 몇 가지일까요? 재료마다 올릴지 말지 2가지라 2n가지입니다. 하나도 안 올린 것과 전부 올린 것도 칩니다.
순서 없이 모아 놓은 것들의 묶음을 집합(set), 그중 일부를 골라 만든 집합을 부분집합(subset)이라 합니다. 고른 재료를 1, 안 고른 재료를 0으로 적으면 부분집합 하나가 n비트 하나와 짝지어집니다.
재료 수를 하나씩 늘려 봅시다. 흐린 재료는 안 올린 것입니다.
재료가 하나 늘면 모든 경우가 새 재료를 안 올린 것과 올린 것으로 나뉘어 두 배가 됩니다.
강아지, 고양이, 토끼를 한 줄로 세우는 방법은 몇 가지일까요? 맨 앞은 3가지, 둘째 자리는 남은 2가지, 마지막은 1가지라 3 × 2 × 1 = 6가지입니다. n마리면 다음과 같고, 이 수를 n 팩토리얼(factorial)이라 합니다.
동물 수를 바꿔 봅시다. 맨 앞이 같은 순서끼리 묶었습니다.
과일 다섯 가지 중 두 가지를 골라 주스를 만들어 봅시다. 줄 세우듯 첫째를 5가지, 둘째를 4가지로 고르면 5 × 4 = 20가지입니다. 그런데 사과 다음 바나나와 바나나 다음 사과는 같은 주스라 모두 두 번씩 세었으니, 2로 나눈 10가지입니다.
n개 가운데 k개를 고를 때도 같습니다. 줄 세우듯 뽑은 가짓수에서 같은 k개를 k!가지 순서로 겹쳐 세었으니 k!로 나눕니다. 이렇게 순서 없이 고르는 것을 조합(combination)이라 하고, 그 가짓수를 nCk라 씁니다.
nCk = n × (n − 1) × … × (n − k + 1) / k!
🍎🍌, 🍌🍎: 줄 세우면 2가지인 순서를 한 번으로 셉니다
비밀번호를 하나씩 다 넣어 보듯 모든 경우를 확인하는 방법을 완전 탐색(brute-force search)이라 합니다. 가장 쉽지만 경우의 수가 크면 쓸 수 없습니다. 1초에 10억 번 확인한다고 치고 시간을 비교해 봅시다.
| 무엇을 세나 | 횟수 | 1초에 10억 번이면 |
|---|---|---|
| 선형 탐색 n | 10 | 10나노초 |
| 선택 정렬의 비교 n(n − 1) / 2 | 45 | 45나노초 |
| 부분집합 모두 2n | 1,024 | 1마이크로초 |
| 줄 세우기 모두 n! | 3,628,800 | 3.6밀리초 |
n을 20으로, 다시 30으로 올려 봅시다.
n이 하나 늘 때 선택 정렬의 비교 횟수는 조금씩 늘지만, 2n은 두 배가 되고 n!은 n + 1배가 됩니다. 경우의 수를 먼저 세어 보면 완전 탐색으로 충분한지 실행해 보기 전에 가늠할 수 있습니다.
계단 10칸을 오릅니다. 한 걸음에 1칸 이상 몇 칸이든 오를 수 있고, 꼭대기에 닿으면 끝납니다. 걸음의 순서가 다르면 다른 방법으로 셉니다(1칸 뒤 2칸과 2칸 뒤 1칸은 다릅니다). 오르는 방법은 모두 몇 가지일까요? 숫자로 답하세요.