yeolyi.com성열의 컴퓨터공학

딸기당근수박참외메론 줄 세우기

경우의 수

컴퓨터는 1초에 10억 번쯤 계산하니, 답을 모르면 모든 경우를 다 해 보면 될까요? 네 자리 비밀번호는 순식간에 다 넣어 보지만, 카드 30장을 늘어놓는 방법을 다 해 보려면 우주의 나이보다 오래 걸립니다. 해 보기 전에 경우가 몇 가지인지 세는 방법을 알아봅시다.

곱의 법칙

상의가 3벌, 하의가 2벌이면 옷을 입는 방법은 3 × 2 = 6가지입니다. 상의를 하나 고를 때마다 하의를 2가지로 고를 수 있기 때문입니다. 이처럼 여러 단계를 차례로 고를 때 각 단계의 가짓수를 곱하면 전체 가짓수가 됩니다. 이를 곱의 법칙(rule of product)이라 합니다.

상의 3
하의 2
입는 방법 3 × 2 = 6가지

숫자만 사용한 네 자리 비밀번호는 자리마다 10가지라 10 × 10 × 10 × 10 = 10,000가지입니다. 비트 n개도 자리마다 2가지라 2n가지입니다. 그래서 8비트는 256가지 수를 나타냅니다.

부분집합

피자 재료 n가지 중 원하는 것만 골라 올리는 방법은 몇 가지일까요? 재료마다 올릴지 말지 2가지라 2n가지입니다. 하나도 안 올린 것과 전부 올린 것도 칩니다.

순서 없이 모아 놓은 것들의 묶음을 집합(set), 그중 일부를 골라 만든 집합을 부분집합(subset)이라 합니다. 고른 재료를 1, 안 고른 재료를 0으로 적으면 부분집합 하나가 n비트 하나와 짝지어집니다.

재료 수 3
고를 수 있는 모든 경우 2 × 2 × 2 = 8가지

재료 수를 하나씩 늘려 봅시다. 흐린 재료는 안 올린 것입니다.

재료가 하나 늘면 모든 경우가 새 재료를 안 올린 것과 올린 것으로 나뉘어 두 배가 됩니다.

줄 세우기

강아지, 고양이, 토끼를 한 줄로 세우는 방법은 몇 가지일까요? 맨 앞은 3가지, 둘째 자리는 남은 2가지, 마지막은 1가지라 3 × 2 × 1 = 6가지입니다. n마리면 다음과 같고, 이 수를 n 팩토리얼(factorial)이라 합니다.

n! = n × (n − 1) × … × 1
동물 3
세우는 방법 3 × 2 × 1 = 6가지
🐶🐱🐰🐶🐰🐱
🐱🐶🐰🐱🐰🐶
🐰🐶🐱🐰🐱🐶

동물 수를 바꿔 봅시다. 맨 앞이 같은 순서끼리 묶었습니다.

골라내기

과일 다섯 가지 중 두 가지를 골라 주스를 만들어 봅시다. 줄 세우듯 첫째를 5가지, 둘째를 4가지로 고르면 5 × 4 = 20가지입니다. 그런데 사과 다음 바나나와 바나나 다음 사과는 같은 주스라 모두 두 번씩 세었으니, 2로 나눈 10가지입니다.

n개 가운데 k개를 고를 때도 같습니다. 줄 세우듯 뽑은 가짓수에서 같은 k개를 k!가지 순서로 겹쳐 세었으니 k!로 나눕니다. 이렇게 순서 없이 고르는 것을 조합(combination)이라 하고, 그 가짓수를 nCk라 씁니다.

nCk = n × (n − 1) × … × (n − k + 1) / k!

과일 5
고를 과일 2
만드는 주스 5 × 4 / 2! = 10가지

🍎🍌, 🍌🍎: 줄 세우면 2가지인 순서를 한 번으로 셉니다

  1. 칸을 눌러 봅시다.
  2. 과일 수와 고를 과일 수를 바꿔 봅시다.

완전 탐색

비밀번호를 하나씩 다 넣어 보듯 모든 경우를 확인하는 방법을 완전 탐색(brute-force search)이라 합니다. 가장 쉽지만 경우의 수가 크면 쓸 수 없습니다. 1초에 10억 번 확인한다고 치고 시간을 비교해 봅시다.

n 10
무엇을 세나횟수1초에 10억 번이면
선형 탐색 n1010나노초
선택 정렬의 비교 n(n − 1) / 24545나노초
부분집합 모두 2n1,0241마이크로초
줄 세우기 모두 n!3,628,8003.6밀리초

n을 20으로, 다시 30으로 올려 봅시다.

n이 하나 늘 때 선택 정렬의 비교 횟수는 조금씩 늘지만, 2n은 두 배가 되고 n!은 n + 1배가 됩니다. 경우의 수를 먼저 세어 보면 완전 탐색으로 충분한지 실행해 보기 전에 가늠할 수 있습니다.

도전 문제

계단 10칸을 오릅니다. 한 걸음에 1칸 이상 몇 칸이든 오를 수 있고, 꼭대기에 닿으면 끝납니다. 걸음의 순서가 다르면 다른 방법으로 셉니다(1칸 뒤 2칸과 2칸 뒤 1칸은 다릅니다). 오르는 방법은 모두 몇 가지일까요? 숫자로 답하세요.