경우의 수: 모든 경우를 훑는 코드는 왜 금방 느려질까

쇼핑몰 상품에 옵션이 붙어 있다. 사이즈(S, M)와 색상(검정, 흰색)이면 고를 수 있는 조합이 4개, 사이즈 5 × 색상 8 × 소재 4면 160개다. 이 조합을 화면에 모두 깔아 주려고 하나씩 만들어 담는 코드를 짰다. 같은 코드로 "필터 체크박스 30개를 각각 켜거나 끈 모든 경우"를 만들면 몇 개일까? 답은 약 10억 개이고, 묶음을 하나씩 만들어 담는 코드는 메모리가 먼저 모자라 끝나지 못한다. 옵션 선택지는 5 + 8 + 4 = 17개, 체크박스는 30개로 둘 다 작은 수인데, 경우의 수는 왜 이렇게 차이 날까?

이 Unit은 그 수를 세는 법, 곧 경우의 수(counting)를 다룬다. 모든 경우를 하나씩 만드는 코드는 흔히 "하나 고르고 → 다음 자리로 들어가고 → 돌아오면 고른 것을 되돌리는" 모양으로 짠다. 이런 짜임을 백트래킹(backtracking)이라고 부른다(알고리즘으로는 『한입 알고리즘』 5장에서 다룬다). 이름은 몰라도 된다. 공식을 외우지 않고, 이 코드가 갈래를 몇 개 만드는지 한 줄씩 따라가며 센다. 그러면 "n이 20을 넘으면 위험하다" 같은 실무 감각이 어디서 나오는지 보인다.

곱의 법칙: 고르는 일이 이어지면 곱한다

윗옷이 3벌(흰, 검정, 파랑), 바지가 2벌(청, 면)이다. 윗옷을 하나 고른 다음 바지를 하나 고르면, 입는 방법은 몇 가지일까? 표로 그려 보면 바로 보인다.

윗옷 하나마다 바지 2가지가 붙으니 행 3개 × 열 2개, 6칸이다. 이렇게 단계별 가짓수를 곱해 세는 규칙을 곱의 법칙(rule of product)이라고 한다. 고르는 일이 차례로 이어지면(윗옷을 고르고, 그다음 바지를 고르고) 각 단계의 가짓수를 곱한다. 신발 2켤레를 더하면 6칸 하나하나에 신발 2가지가 또 붙어 3 × 2 × 2 = 12가지다.

더하기가 맞는 경우도 있다. "윗옷 3벌 중 하나 또는 바지 2벌 중 하나, 아무거나 하나만 고른다"면 3 + 2 = 5가지다. 구별하는 법은 간단하다. 둘 다 고르면(그리고) 곱하고, 둘 중 하나만 고르면(또는) 더한다.

같은 규칙이 비밀번호에도 쓰인다. 0~9 숫자 4자리 PIN은 자리마다 10가지라 10 × 10 × 10 × 10 = 10⁴ = 10,000가지다. 10⁴처럼 같은 수를 여러 번 곱한 것을 거듭제곱(power)이라 하고, 위에 작게 쓴 4는 몇 번 곱했는지를 나타내는 지수(exponent)다.

줄 세우기: 순열과 팩토리얼

A, B, C 세 명을 한 줄로 세운다. 첫 자리에는 셋 중 누구나 올 수 있다. 둘째 자리에는 첫 자리에 선 사람을 빼고 두 명이, 마지막 자리에는 남은 한 명이 온다. 곱의 법칙으로 3 × 2 × 1 = 6가지다. 고를 때마다 후보가 하나씩 준다는 점이 옷 고르기와 다르다.

1const items = ['A', 'B', 'C']2const used = [false, false, false]3const path: string[] = []4const result: string[] = []5function arrange() {6  if (path.length === items.length) {7    result.push(path.join(''))8    return9  }10  for (let i = 0; i < items.length; i++) {11    if (used[i]) continue12    used[i] = true13    path.push(items[i])14    arrange()15    path.pop()16    used[i] = false17  }18}19arrange()20console.log(result.join(' '))21console.log(`${result.length}가지`)

ABC ACB BAC BCA CAB CBA
6가지

이렇게 순서를 따져 늘어놓는 것을 순열(permutation)이라 하고, n부터 1까지 모두 곱한 수를 팩토리얼(factorial)이라 부르며 n!로 적는다.

$n! = n \times (n-1) \times \cdots \times 2 \times 1$

n부터 하나씩 줄여 가며 1까지 곱하라는 뜻이다. 가운데 점 세 개는 "그 사이 수도 다 곱한다"는 표시다. 3! = 3 × 2 × 1 = 6, 4! = 4 × 3! = 24다. 한 명이 늘 때마다 앞 답에 그 사람 수를 곱하므로 빠르게 커진다.

모두가 아니라 몇 명만 세울 수도 있다. 5명 중 1등·2등·3등을 정하면 자리가 셋뿐이라 5 × 4 × 3 = 60가지다.

${}_5P_3 = 5 \times 4 \times 3 = 60$

"5명에서 3명을 골라 순서대로 세우는 수"라고 읽는다. P는 순열의 영어 첫 글자다. 5에서 시작해 하나씩 줄이며 3개만 곱한다.

팀 뽑기: 조합은 겹치는 순서로 나눈다

이번에는 5명(A~E) 중 3명으로 팀을 만든다. 팀에는 순서가 없다. A, B, C를 뽑든 C, A, B를 뽑든 같은 팀이다.

앞 절의 1등·2등·3등 60가지에서 출발해 보자. 그 60가지 안에서 팀 {A, B, C}는 ABC, ACB, BAC, BCA, CAB, CBA로 여섯 번 나온다. 세 명을 줄 세우는 순서가 3! = 6가지라서다. 다른 팀도 모두 정확히 6번씩 나온다. 그러니 팀 수는 60 ÷ 6 = 10이다.

${}_5C_3 = \frac{{}_5P_3}{3!} = \frac{5 \times 4 \times 3}{3 \times 2 \times 1} = 10$

"5명에서 3명을 고르는 조합"이라고 읽는다. 분자는 순서까지 따져 뽑은 수(60)이고, 분모는 한 팀이 몇 번씩 겹쳐 세어졌는지(6)다. 이렇게 순서를 따지지 않고 고르는 것을 조합(combination)이라고 한다.

조합은 실무에서 자주 나온다. 상품 6개 중 2개를 골라 비교하는 화면이라면 짝은 6 × 5 ÷ 2 = 15가지다. 모든 쌍을 비교하는 이중 루프가 n(n − 1) ÷ 2번 도는 것도 같은 계산이다.

부분집합: 원소마다 두 갈래, 2ⁿ

필터 체크박스가 a, b, c 세 개다. 각각 켜거나 끌 수 있으면 켜진 것들의 묶음은 몇 가지일까? 원소를 골라 만든 묶음을 부분집합(subset)이라고 한다. 아무것도 안 켠 빈 묶음 {}, 전부 켠 {a, b, c}도 센다.

체크박스 하나마다 "켠다/끈다" 두 가지이고, 세 개를 차례로 정하니 곱의 법칙으로 2 × 2 × 2 = 2³ = 8가지다. 개수를 정하지 않고 고른다는 점이 앞 절의 팀 뽑기와 다르다.

1const items = ['a', 'b', 'c']2const path: string[] = []3const result: string[] = []4const order: number[] = []5function pick(i: number) {6  order.push(i)7  if (i === items.length) {8    result.push('{' + path.join(',') + '}')9    return10  }11  path.push(items[i])12  pick(i + 1)13  path.pop()14  pick(i + 1)15}16pick(0)17console.log(result.join(' '))18console.log(`부분집합 ${result.length}개, 호출 ${order.length}번`)

{a,b,c} {a,b} {a,c} {a} {b,c} {b} {c} {}
부분집합 8개, 호출 15번

원소가 n개면 부분집합은 2를 n번 곱한 2ⁿ개다. 원소가 하나 늘 때마다 두 배가 되는 이 증가 속도(growth rate)를 Big-O 표기법(Big-O notation)으로 적으면 O(2ⁿ)이다(Unit 3 표의 2ⁿ 줄, 빅오 표기법 노트). 호출 수 2ⁿ⁺¹ − 1(2를 n + 1번 곱한 수에서 1을 뺀 것. 원소 3개면 2⁴ − 1 = 15, 앞에서 센 호출 수)도 2ⁿ의 약 두 배라 모양은 같다.

부분집합은 조합을 크기별로 모은 것이기도 하다. 원소 4개라면 0개를 고르는 법 1, 1개 4, 2개 6, 3개 4, 4개 1을 모두 더해 16 = 2⁴이다.

숫자 감각: n이 20을 넘으면

세 가지 경우의 수가 n에 따라 어떻게 자라는지 나란히 놓으면 이렇다.

표의 "약 2.4 × 10¹⁸" 같은 표기는 2.4 뒤에 0이 18개쯤 붙는 수라는 뜻이다(약 a × 10ᵏ은 a 뒤에 0이 k개쯤 붙는 수). 2¹⁰ = 1,024는 약 1,000이다. 그래서 2²⁰은 1,000 × 1,000 = 약 100만, 2³⁰은 약 10억, 2⁴⁰은 약 1조로 어림할 수 있다. 10이 늘 때마다 1,000배다.

시간으로 바꿔 보자. Unit 3처럼 연산 한 번에 1나노초, 곧 1초에 10억 번 계산한다고 친다. 잰 값이 아니라 어림이다. 기기·언어마다 다르고, 묶음을 하나씩 만들어 담는 백트래킹은 경우 하나에 연산을 여러 번 하니 이보다 느리다. 그러면 이렇게 정리된다.

• 2ⁿ 탐색: n이 20이면 약 100만이라 1밀리초쯤, 순식간이다. 30이면 약 10억이라 경우 하나에 연산 한 번씩만 해도 1초가 넘고, 10억 개 묶음을 실제로 만들어 담으면 메모리가 먼저 모자란다. 40이면 약 1.1조라 18분이 넘는다. n이 20을 넘으면 모든 부분집합을 훑는 코드는 위험하다고 보고, 가지치기(pruning, 답이 될 수 없는 갈래를 미리 자르기)나 다른 방법을 찾는다.
• n! 탐색: 10!이 약 363만이라 4밀리초쯤, n이 10 안팎이면 괜찮다. 12!(약 4.8억)은 0.5초쯤이지만 13!은 약 62억이라 6초, 15!은 약 1.3조라 20분이 넘는다. n이 12를 넘으면 모든 순서를 훑기 어렵다.
• n²(모든 쌍의 어림): n이 1만이어도 1억이라 0.1초다.

수가 이렇게 커지면 다른 문제도 생긴다. JavaScript의 number는 2⁵³(약 9천조)까지는 모든 정수를 정확히 담지만, 2⁵³ + 1은 담을 수 없어 2⁵³으로 반올림된다. 그래서 바로 옆 정수와 구별된다고 보장되는 안전한 정수(safe integer)는 Number.MAX_SAFE_INTEGER, 곧 2⁵³ − 1 = 9007199254740991까지다(MDN). 18!은 약 6.4 × 10¹⁵라 그 안에 있지만, 19!은 약 1.2 × 10¹⁷로 넘는다.

1const n = 202let f = 13for (let i = 1; i <= n; i++) {4  f *= i5  if (i >= 17) console.log(`${i}! = ${f}, +1 하면 ${f + 1 === f ? '그대로' : '달라짐'}`)6}

17! = 355687428096000, +1 하면 달라짐
18! = 6402373705728000, +1 하면 달라짐
19! = 121645100408832000, +1 하면 그대로
20! = 2432902008176640000, +1 하면 그대로

2⁵³을 넘으면 number가 담을 수 있는 정수 사이에 빈틈이 생겨서, 19! + 1이 가장 가까운 담을 수 있는 수인 19!로 반올림된다. 그래서 19!과 19! + 1을 구별하지 못한다(number는 수를 담는 자리가 53비트라 2진수 54자리부터는 끝자리가 잘린다. 『한입 CS』 0장). 그렇다고 19!~22!의 저장된 값이 근삿값인 것은 아니다. 2⁵³ 위에서는 담을 수 있는 수 사이 간격이 2, 4, …로 벌어질 뿐, 간격 위에 놓인 수는 정확히 저장된다. 22!은 1부터 22까지 곱하는 동안 2가 19번 곱해진 수(1~22에 2의 배수 11개, 그중 4의 배수 5개, 8의 배수 2개, 16의 배수 1개라 11 + 5 + 2 + 1 = 19번)라, 2¹⁹를 묶어 내면 남는 수가 53비트 안에 들어가 간격 위에 정확히 놓인다. 23!은 23이 홀수라 2가 더 늘지 않는데 수는 23배 커져서, 남는 수가 53비트를 넘는다. 그래서 23!부터는 저장된 값 자체도 정확하지 않다.

Python의 정수(int)는 크기 제한 없이 정확하다(Python 문서). JavaScript에서 큰 정수를 정확히 세려면 BigInt를 쓴다. 숫자 뒤에 n을 붙여(1n) 만들고, BigInt끼리만 계산한다(f *= BigInt(i)). number와 섞어 쓰면 TypeError가 난다(MDN: BigInt). BigInt로 곱하면 25!도 두 언어가 같은 값을 낸다.

실무 코드에서 찾아보기

경우의 수 코드는 "순서를 따지나?"(3절)와 "n이 최대일 때 이 수가 number가 정확히 담는 2⁵³ 안인가?"(5절)를 먼저 묻는다. 비트 연산이 보이면 32비트 한계(Unit 1 6절)도 확인한다.

이 Unit이 쓰이는 곳

• 『한입 알고리즘』 5장 DFS와 백트래킹: 옵션 조합 수가 "그룹별 선택지 수의 곱"(사이즈 5 × 색상 8 × 소재 4 = 160)이라는 문장이 곱의 법칙이다. 가지치기 절의 "경우의 수는 그룹이 늘수록 곱으로 커진다"도 같은 계산이다.
• 『한입 알고리즘』 10장 동적 계획법: 줄이 1,000개인 두 파일에서 공통으로 남길 줄을 고르는 조합이 "2의 1,000제곱에 가깝다"는 문장이 부분집합 2ⁿ이다. 줄마다 남긴다/뺀다 두 갈래다.
• 『한입 CS』 0장 숫자는 비트다: "안전한 정수는 2⁵³까지" 절이 이 Unit 5절의 19!과 같은 한계를 다룬다. 큰 id에 BigInt나 문자열을 쓰는 이유다.
• 『한입 CS』 10장 해시, 암호화, 인코딩: 보너스 문제에서 16진수 서명 L글자의 모든 조합이 16ᴸ가지(16을 L번 곱한 수)라는 것이 곱의 법칙이다. 한 자리씩 맞히면 16을 L번 곱하던 것(16ᴸ)이 16을 L번 더한 것(16 × L)으로 바뀐다. 곱이 합으로 바뀐 것이다.

comb(5, 3) → 10
comb(30, 15) → 155117520