자연수의 자릿수를 구하는 3가지 방법
0. Index
1. 들어가며
오늘은 상당히 가벼운 알고리즘 주제인 자연수 숫자의 자릿수를 구하는 알고리즘을 다룬다. 문제 서술이 더 필요없을 정도로 자명한 문제인데, 이렇게 쉽지만 내 알고리즘 포스트들의 전통을 따라 서로 다른 알고리즘 세 가지를 준비했다. 하나는 매우 Pythonic한 방법으로 파이썬 유저 사이에서는 가장 대중적이다. 두 번째는 수학 지식을 조금 사용하고, 세 번째는 모든 언어에서 통용될법한 일반적인 방법을 사용한다.
그동안 보다 수준 있는, 어려운 알고리즘을 찾아다녔다. 최근 기준으로 LIS, 하노이의 탑 포스트를 작성했는데 이들이 솔직히 정말 매우 어려운 알고리즘이라고 할 수는 없지만 초심자들에게는 상당한 장벽이 될 수 있는 주제들이다. 그런데 갑자기 이렇게 간단한 주제를 가지고 온 이유는 나름의 이유가 있다. 구글 애널리틱스로 확인한 결과 내 블로그에서는 쉬운 알고리즘 주제에 대한 수요가 많다. 이번주 기준 방문자수 1, 2, 3등 포스트의 주제가 각각 팩토리얼, 배열의 수의 합, 피보나치 수열 알고리즘이다. 아마 내 블로그를 방문하는 분들 중 초심자들이 더 많은 것이 아닌가 추측하는 이유다. 냉정히 말해 지금까지 정말정말 어려운 알고리즘을 다룬 적은 없는 것 같고… 그래서 이 분들을 위한 더 많은 포스트를 기획하게 됐고 결과 이 포스트를 작성하게 됐다.
시작합니다.
2. 문제 소개
문제 이해가 너무 쉬워서 문제를 소개하는 장을 생략할까 했지만 내 철학상 그럴 수는 없었다. 코딩 테스트를 통과할 알고리즘에 대한 이해에 앞서 선행되어야 하는 과정은 언제나 문제에 대한 이해다. 이 과정없이 코드에 바로 뛰어드는 사람들이 생각보다 많아서 걱정이다. 그러면 문제에 대한 설명이 긴, 카카오 코딩 테스트 같은 수준 있는 테스트에서는 조건 한 두개씩 생략해서 고생을 하기 십상이다. 우리는 그러지 말고 문제를 항상 우리의 문장으로 정의하고 코드로 넘어가는 습관을 기르자.
\(10000\)이라는 수는 수학적으로 \(10^4\)과 같은데 우리는 어떤 숫자를 지수(\(4\))와 연관시켜 이해하려는 경향이 있다. 가령 동양에서는 십진수 단위를 사용할 때 밑수 10의 지수가 \(4\)씩 더해질 때마다 만, 억, 조 등의 표현을 쓴다. 서양에서는 지수가 \(3\)씩 더해질 때마다 thousand, million, billion 등의 표현을 쓴다. 근데 여기에 더해 어떤 영화를 보니 영어로는 저 수를 \(5\text{-digit number}\)이라고도 표현하더라. 지수로 숫자를 표현하는 것이 아니라 단순히 자연수의 길이를 가지고 수를 표현한 것이다. 확실히 어떤 값이나 개념을 표현하는 방법은 하나가 아닐 수 있다. 이때 우리가 만드는 기능은 다음과 같다:
어떤 자연수 N이 D-digit number일 때, D를 구하라
좋다. 단순하다. 조건을 몇 가지만 붙이면 자연수 N은 10진수를 기반으로 하며, 숫자가 0일 때는 D는 0이 된다.
바로 알고리즘으로 넘어가자.
3. 알고리즘!
3.1. Pythonic way
이 방법은 데이터 분석, 머신러닝 등을 위해 파이썬으로 프로그래밍을 처음 공부하는 분들이 모두 쓸만한 방법이다. 독자분들 다 아실 것 같으니 바로 코드를 보자.
a = 10000
b = 123
c = 123456789
print(len(str(a)))
print(len(str(b)))
print(len(str(c)))
5
3
9
숫자를 str 함수를 통해 문자열로 바꾸고, 여기에 len 내장함수를 통해 그 길이를 반환하면 이 기능을 완벽하게 구현할 수 있다. 파이썬에서 매우 유명한 방법이고 Pythonista 모두에게 이 기능 구현을 요구하면 백이면 백 이렇게 숫자의 길이를 구할 것이다.
이 방법은 간단하고 쉽다는 큰 장점이 있다. 단점은 없을까? 천만에, 좋기만 한 건 이 세상에 없다. 이 방법은 Pythonic하다고 했다. 그 말은 이 방법만 써본 사람은 다른 언어로는 이렇게 자연수의 길이를 구할 수 없다는 뜻이 된다. 우리가 지금 파이썬을 써도 앞으로도 평생 파이썬을 쓸 수 있다는 보장이 없기 때문에 이 기능에 대한 다른 구현 방법을 생각해보는 것은 도움이 된다. 그래서 두 알고리즘을 추가로 소개하는 것이다.
너무 쉬워서 할 말이 별로 없는데 이렇게 끝내면 시시하니 왜 이렇게 하면 길이가 구해지는지, 조금만 파이썬 안쪽의 이야기를 해보자. ‘왜 len(10000) 이렇게 하면 길이가 안 나오고 에러가 뜨는 것일까?’ 같은 위대한 질문을 하는 독자들도 있으리라고 생각한다.
파이썬의 내장 collections.abc 모듈에는 파이썬의 많은 자료구조(list, set 등)들의 원형(archetype)이 되는 추상형 자료구조(Abstract Data Type)들이 있는데 그중 Sequence라는 자료구조가 있다. 이 자료구조는 한 마디로 원소들의 순서를 매길 수 있는 1차원 배열에 대한 추상형 자료구조이고 이 조건을 만족하는 list, tuple 등은 이 원형 자료구조를 내부적으로 상속하고 있다.
from collections.abc import Sequence
print(issubclass(list, Sequence))
print(issubclass(tuple, Sequence))
True
True
Sequence 자료구조의 특징은 Indexing을 지원한다는 것이며 우리는 배열에서 이 짓을 정말 많이 해봤다. 하지만 set 같은 자료구조는 Sequence를 상속받지 않고 따라서 Indexing이 되지도 않는다. 상식적으로 집합은 원소간의 순서를 상정하지 않는 자료구조다.
그리고 파이썬 문자열 자료구조(str) 또한 내부적으로 Sequence를 상속받으며 따라서 Indexing이 가능하다.
# str은 Sequence를 상속받는다.
print(issubclass(str, Sequence))
True
# 따라서 Indexing이 가능하다.
print('abcde'[3])
d
그리고 Sequence 는 내부적으로 Sized 라는 원형 ADT 클래스를 상속받고 이 부모 클래스는 len 메소드를 지원한다. 따라서 str 또한 Sized 를 상속받는다고 할 수 있고, 그렇기 때문에 len 내장함수를 써서 그 길이를 구할 수 있는 것이다. 반면 int 자료구조는 Sized 자료구조를 상속받지 않기 때문에 str 로 변환시켜야지만 그 길이를 구할 수 있다. 그래서 int 를 str 로 변경하는 형 변환(type casting)이 필요했다.
from collections.abc import Sized
print(issubclass(str, Sized))
print(issubclass(int, Sized))
True
False
이 자료구조 상속관계를 그림으로 표현하면 다음과 같다.
설명에서는 생략했지만 Sequence 와 Sized 사이에는 상속 관계가 더 얽혀있다. 하지만 이번 내용에는 필요없어서 생략했다. 이런 내용이 궁금한 분들은 조금만 기다려주세요. 언젠가 파이썬의 ADT에 대한 내용도 꼭 다루겠다. 그리고 상속관계 화살표에서 화살표가 향하는 방향이 자신의 부모 클래스가 된다. 그 반대가 아니다. 위에서 아래로 Top-down으로 상속관계를 짠다고 화살표의 방향이 자식 클래스가 된다고 생각하기 쉬운데 그게 아니라는 것을 기억하자. 실제로 OOP에서는 클래스들의 상속관계를 이렇게 표현한다.
3.2. 로그 사용하기
다음 방법은 고교 수학의 기본인 로그를 사용하는 것이다. 내 생각에 프로그래밍을 한다고 하면 로그 정도의 수학까지는 알아야 한다. 당장 알고리즘만 봐도 \(O(logN)\)의 시간복잡도와 같은 개념을 논하니까.
여기서 논하는 로그(log)는 통나무를 말하지 않고, 대신 ‘어떤 수가 어떤 밑수의 몇 승인가’를 논하는 개념이다. 가령 \(10000\)은 10의 4승이다. 그러면 \(log_{10}10000 = log_{10}10^4\)이기 때문에 값은 4가 된다. 그대로다. 더 설명이 필요할 것 같지 않다.
다만 기억할 것은 어떤 자연수에 로그를 씌운 결과는 그 수의 길이와 깊은 관계가 있다는 것이다.
\[ \displaylines{ log_{10}10 = log_{10}10^1 = 1 \\ log_{10}1000 = log_{10}10^3 = 3 \\ log_{10}1000000 = log_{10}10^6 = 6 } \]
10, 1000, 1000000에 밑수가 10인 로그를 씌워보니 각각 1, 3, 6이 나왔는데 정확한 숫자의 길이를 표현하지는 못하지만 확실히 길이가 길어지면 로그값도 커진다. 정확히는 로그값에 1을 더하면 자연수의 길이가 나온다. 이 방법을 사용하면 될 것 같다. 또 감안할 것은 로그를 취하는 값이 정확히 밑수의 자연수 지수로 떨어지지 않는 경우인데, 가령 \(log_{10}20 \simeq 1.3010\) 같은 경우가 있겠다. 로그값에 소수점이 붙는다. 하지만 걱정하지 마라. 10과 20의 길이가 같은 것처럼, 자연수의 길이가 같으면 로그값의 소수부는 달라질지언정 정수부는 변하지 않는다. 즉, 로그값을 만든 후 그 값을 내림하면 문제없이 처리 가능하다.
로그 함수를 사용해 이 기능을 만들어보자.
import math
def digit_length(n):
return int(math.log10(n)) + 1 if n else 0
print(digit_length(10))
print(digit_length(100))
print(digit_length(12345))
2
3
5
내장 math 모듈을 통해 자연수의 길이를 반환하는 digit_length 함수를 만들었다. 먼저 각 언어에는 수학 관련 라이브러리가 있기 마련인데 파이썬도 마찬가지다. math 모듈에는 무한값, 파이값을 비롯해 심각한 불안장애를 유발하는 삼각함수 등 수많은 수학 관련 기능이 내재되어 있으며 그중에는 밑수를 10으로 두고 어떤 수의 로그값을 반환하는 log10 이라는 함수도 있다. 우리의 문제는 10진수를 바탕으로 하기 때문에 이 기능을 사용했다.
그리고 삼항 연산자를 썼는데 수가 0일 때는 밑수가 어떤 값이어도 로그값을 구할 수 없다. 이는 기본적인 로그 상식이며 함수에 0을 넣으면 에러가 발생하기 때문에 입력값이 0일 때를 따로 고려해 길이 0을 반환하도록 처리했다. 2장에서 문제의 제약조건을 설정할 때 입력의 조건에 굳이 0을 포함해서 설명한 것은 다 이유가 있었던 것이다. 문제 정의가 이렇게 중요하다.
또 n 에 따라 소수부가 발생할 수 있기 때문에 int 를 통해 그 소수부를 제거한다. 실수형 자료구조 float 을 int 로 type casting하면 타입 변환뿐 아니라 실질적으로 소수부 내림이 되기 때문에 파이썬에서는 실수 내림을 이 방법으로 많이들 한다 . 마지막으로 정수로 반환된 로그값에 1을 더해야 그 길이가 온전히 나오기 때문에 1을 더한다.
최소한의 수학적 지식을 통해 우리가 원하는 기능을 이렇게 짧게 구현할 수도 있었다. 실제로 한참 Pythonic한 기능들에 회의를 갖고 있었을 때 나는 숫자의 길이를 이 함수를 구현해서 찾고는 했다.
3.3. 가장 무난한 풀이
이 방법이 모든 언어에서 가장 무난하고 상식적인 방법이다. 알고리즘 입문자들에게 낼만한 수준이기도 하다. 바로 입력값을 10으로 나눠가며 나머지를 버리고 길이를 키우는 방법이다. 바로 코드를 보자.
def digit_length(n):
ans = 0
while n:
n //= 10
ans += 1
return ans
print(digit_length(0))
print(digit_length(10))
print(digit_length(100))
print(digit_length(12345))
0
2
3
5
이 함수에 대한 설명이 필요할 것 같다.
- while n:
- 파이썬은 숫자 자체를 조건식으로 사용하는 것을 허락한다. 이때 0(0.0 등 포함)일 때는 False, 그 외에는 정수, 실수, 음수, 복소수 할 것 없이 전부 True 가 된다. 따라서 조건식이 참일 때는 모두 n 이 0이 아니라는 뜻이 된다. 이때 우리는 10씩 나눠가며 값을 1씩 키울 수 있다.
- 이후로는
//를 통해 나머지를 버리고 몫만 남긴다. 그때마다 값을 1 키워 while 문을 나올 때는 n 은 0이 되어 있고 ans 에는 원 숫자의 길이가 담기게 된다.
확실히 모든 프로그래밍 언어는 나누기 등 사칙연산과 반복문을 지원하기 때문에 이 방법은 모든 언어에서 통용될 수 있는 함수다. 자연어로 치면 ‘영어’와 비슷하다고 할 수 있을까? 그런 의미에서 이 방법이 세 방법 중 가장 범용성이 짙은 방법이라고 평가할 수 있겠다. 특정 언어에 국한되지 않는 방법을 익히는 것은 분명 타 언어를 공부할 때 도움이 될 것이라 믿는다.
4. 마치며
이상 자연수의 길이를 구하는 세 가지 방법에 대해 알아봤다. 역시 주제가 가벼워서 300줄도 안 나왔다. 내가 지금 큰 고민이 있는데 전부터 객체지향에 대해 글을 쓰고 싶었는데 지금 대충 네 편에 걸쳐 시리즈를 쓸 각이 잡혔다. 근데 주제가 쉽지 않아서 매우 많은 시간이 소요될 것 같은데 두렵다. 할 수 있을까? 하… 모르겠다. 언젠간 꼭 해결해야 할 포스트이기는 한데… 좀더 고민해보겠다.
다음 포스트는 일단은 짧은 에세이가 될 것 같다. 개인적으로 커다란 교훈을 얻었던 경험이어서 꼭 표현하고 싶었다.
이상 포스트를 마칩니다.