로그: 10억 개에서 30번 만에 찾는 이유

친구가 1부터 1,000 사이에서 숫자 하나를 골랐다. 숫자를 부르면 친구는 "업"(더 크다), "다운"(더 작다), "정답" 셋 중 하나로만 답한다. 1부터 차례로 부르면 운이 나쁠 때 1,000번을 불러야 한다. 늘 남은 범위의 한가운데를 부르면 어떨까? 500을 불러 "업"이면 501~1,000만 남고, 이어서 750을 불러 "다운"이면 501~749만 남는다. 부를 때마다 후보가 절반으로 줄어서, 아무리 운이 나빠도 10번이면 맞힌다. 범위를 10억까지 넓혀도 30번이면 된다. 범위는 100만 배 넓어졌는데 부르는 횟수는 20번 늘었을 뿐이다. 이 10과 30은 어디서 나오고, 왜 이렇게 작을까?

이 Unit은 로그를 두 가지로 읽는 법을 다룬다. 하나는 "반으로 몇 번 접나", 다른 하나는 "몇 층인가"다. 수학 배경은 필요 없다. 나눗셈과 곱셈만 쓴다.

로그: 반으로 몇 번 접나

길이 1,024짜리 종이를 반으로 접으면 길이가 512, 또 접으면 256이 된다. 몇 번 접어야 길이 1이 될까? 이 횟수를 세는 수가 로그다. 먼저 업다운 게임의 후보 수로 세어 보자.

업다운 게임의 횟수가 여기서 나온다. 후보 1,000개는 틀린 답을 9번 들으면 하나만 남고, 남은 하나를 부르는 데 한 번이 더 들어 많아야 10번이다. 10억이면 29 + 1 = 30번이다.

이 횟수를 거꾸로 보면 곱셈이다. 1에서 시작해 2를 열 번 곱하면 1,024가 된다. 같은 수를 여러 번 곱한 것을 거듭제곱(power)이라 하고, 몇 번 곱했는지를 위에 작게 쓴 수를 지수(exponent)라고 한다. $2^{10} = 1024$는 "2를 열 번 곱하면 1,024"라고 읽는다.

로그(logarithm)는 이 질문을 거꾸로 묻는다. "2를 몇 번 곱해야 1,024가 되나?" 답은 10이고, $\log_2 1024 = 10$이라고 쓴다. "로그 2의 1,024는 10"이라고 읽는다. 아래에 작게 쓴 2가 몇으로 나누는지(곱하는지)를 정하는 수, 곧 밑(base)이다. 같은 뜻을 나눗셈으로 말하면 "1,024를 2로 열 번 나누면 1이 된다"이다. 이 책에서는 밑을 적지 않은 log를 밑이 2인 로그로 읽는다.

1,000처럼 2의 거듭제곱이 아닌 수의 로그는 소수다. $\log_2 1000 \approx 9.97$. 2를 9번 곱하면 512, 10번 곱하면 1,024라서 1,000은 그 사이, 10에 조금 못 미치는 9.97이다(≈는 "약"이라고 읽는다). 정확한 값은 Math.log2(1000)·math.log2(1000)으로 얻는다(MDN: Math.log2, Python 문서: math.log2). 반으로 나눈 횟수는 정수라서 9번이었다. 나눌 때마다 소수점 아래를 버리기 때문이다(125 ÷ 2 = 62.5에서 0.5를 버려 62). 코드로 적으면 while (n > 1) n = Math.floor(n / 2)다. Math.floor는 소수점 아래를 버리고(MDN: Math.floor), Python의 //도 나눈 뒤 내린다(Python 문서: 이항 산술 연산). 내리면 매번 조금씩 더 작아지니 9.97번이 아니라 9번 만에 1에 닿는다. 코드의 횟수와 로그 값은 이렇게 1 안쪽으로 차이 날 수 있다.

숫자로 감 잡기: 1,000배마다 10씩

log₂ n의 값을 몇 개 외워 두면 코드를 볼 때 바로 어림할 수 있다.

외우는 요령은 하나다. $2^{10} = 1024 \approx 1000$. 2를 열 번 곱하면 1,000과 거의 같다. 그래서 n이 1,000배가 될 때마다 log₂ n은 10씩 늘어난다. 1,000은 약 10, 100만(1,000 × 1,000)은 약 20, 10억(1,000 × 1,000 × 1,000)은 약 30이다. n이 두 배가 되면 log₂ n은 1 늘어난다. 반으로 한 번 더 나누면 되기 때문이다.

밑이 10인 로그도 자주 본다. $\log_{10} 1000 = 3$. 1,000을 10으로 세 번 나누면 1이 된다는 뜻이다. 10으로 한 번 나눌 때마다 10진수 자리가 하나 줄어드니, log₁₀ n은 n의 자릿수보다 1 작은 정도다. 1,000은 네 자리이고 log₁₀ 1,000은 3이다. 100만(일곱 자리)이면 6이다.

몇 층인가: 트리의 높이

로그의 두 번째 얼굴은 "몇 층인가"다. 맨 위 칸 하나에서 아래로 가지를 치며 내려가는 구조를 트리(tree)라고 한다. 회사 조직도나 토너먼트 대진표가 이런 모양이다. 칸 하나가 아래로 칸을 많아야 둘 거느리는 트리가 이진 트리(binary tree)이고, 맨 위 한 칸을 뿌리(root)라고 한다. 이진 트리를 위층부터, 한 층 안에서는 왼쪽부터 빈틈없이 채워 원소 n개를 담으면 몇 층이 될까?

층마다 칸 수는 1, 2, 4, 8, …로 두 배씩 는다. k층까지 다 채우면 칸은 $2^k - 1$개다. "2를 k번 곱한 수에서 1을 뺀 만큼"이라고 읽는다. 4층이면 1 + 2 + 4 + 8 = 15 = 2⁴ − 1개다(이 합이 왜 늘 2ᵏ − 1인지는 Unit 4에서 식으로 본다). 그러니 원소 n개를 담는 데 필요한 층 수는 "2를 몇 번 곱해야 n을 넘나", 곧 약 log₂ n이다. 원소가 두 배가 되면 층은 한 층 는다.

업다운 게임도 같은 그림이다. 첫 질문으로 후보 n개가 반으로, 다음 질문으로 다시 반으로 줄어드는 과정을 위에서 아래로 그리면, 질문 한 번이 한 층이다(1절의 나눗셈 한 번이 한 층). 그래서 "반으로 몇 번 접나"와 "몇 층인가"는 같은 수, log₂ n을 센다.

이 두 얼굴은 나중에 알고리즘 이름으로 다시 만난다. 정렬된 배열에서 값을 찾는 이분 탐색(binary search)은 업다운 게임을 코드로 옮긴 것이고, 위층부터 빈틈없이 채운 이진 트리에 값을 담는 힙(heap)은 값을 넣고 꺼낼 때 뿌리에서 맨 아래층까지 한 줄기만 고친다. 둘 다 일이 log₂ n에 비례해서 O(log n)이라고 적는다(O(…)는 입력이 커질 때 일이 늘어나는 모양만 적는 Big-O 표기법이고, Unit 3에서 자세히 본다). 알고리즘 자체는 『한입 알고리즘』 6장과 8장이 다룬다(개념 정리는 이분 탐색·이진 힙 노트). 지금은 "반으로 줄이거나 층을 내려가면 로그"만 기억하면 된다.

밑이 달라도 같은 log

데이터베이스는 행을 빨리 찾으려고 인덱스(index)를 두는데, 그 인덱스가 대개 B-트리(B-tree)다. B-트리의 칸 하나는 3절 이진 트리처럼 원소 하나가 아니라 디스크 페이지(page) 하나이고, 페이지 하나에 키가 수백 개 들어가 아래로 둘이 아니라 수백 개를 거느린다. 페이지 하나에 키가 300개 들어간다고 치면 층마다 300배씩 넓어진다. 페이지 수가 1 → 300 → 9만으로 늘어 셋째 층이 9만 페이지이고, 그 9만 × 300 = 2,700만 개 키로 2,700만 행을 3층에 담는다. $\log_{300} 27000000 = 3$, 곧 2,700만을 300으로 세 번 나누면 1이 된다는 뜻이다.

같은 2,700만 행을 이진 트리에 담으면 약 25층이다($\log_2 27000000 \approx 24.7$). 3층과 25층은 꽤 달라 보인다. 그런데 300으로 한 번 나누는 것은 2로 약 8.2번 나누는 것과 같다($\log_2 300 \approx 8.2$, 2를 8.2번쯤 곱하면 300). 300으로 한 번 나누기 = 2로 8.2번 나누기이니, 300으로 세 번 나누면 2로 8.2 × 3 ≈ 24.7번 나눈 것이다. 그래서 밑이 300인 로그는 밑이 2인 로그를 늘 8.2로 나눈 값이다. 24.7 ÷ 8.2 ≈ 3이다.

밑을 바꾸면 값이 일정한 수로 나뉠 뿐이다. 데이터가 1,000배 늘면 이진 트리는 10층, B-트리는 약 1.2층 늘어난다. 늘어나는 모양은 같고 크기만 다르다. Big-O는 이런 일정한 배수를 버리고 모양만 남기므로, 밑이 2든 300이든 10이든 모두 O(log n)이다. 그래서 Big-O에서는 밑을 적지 않는다. 다만 디스크 페이지를 읽는 횟수가 3번이냐 25번이냐는 실제 속도에서는 큰 차이라서, 데이터베이스는 넓은 B-트리를 쓴다.

이 Unit이 쓰이는 곳

• 『한입 알고리즘』 0장: 2절 Big-O 표의 O(log n) 줄. "정렬된 배열에서 이분 탐색", n이 10배가 되면 "조금 늘어남"이다. 10배면 log₂ n은 약 3.3 는다.
• 『한입 알고리즘』 6장: 1절 "절반씩 버리기". 1만 개는 14번, 100만 개는 20번(2²⁰ = 1,048,576)이면 후보가 하나로 줄어 비교 횟수가 log₂ n이다.
• 『한입 알고리즘』 8장: 2절 넣기와 꺼내기. 원소가 n개인 힙의 높이는 약 log₂ n이라 넣기·꺼내기가 O(log n)이고, 100만 개여도 층은 20개다.
• 『한입 CS』 8장: 2절 B-트리 높이. 페이지에 키 300개면 3층에 2,700만 행을 담고, "몇 층인가"를 세는 수가 log n이다.

n = 1,023 → ?자리
n = 1,024 → ?자리