Project Euler

프로젝트 오일러 013

프로젝트 오일러 13번, 50자리 숫자 100개의 합에서 처음 10자리를 구하는 문제입니다. 파이썬의 큰 정수 연산 기능을 활용한 간단한 풀이와 함께, 큰 수의 덧셈을 직접 구현하는 방법을 자세히 설명합니다. 다항식의 덧셈 원리를 이용한 구현 과정을 보여줍니다.

3분
#project euler #python

큰 수의 덧셈

50자리 10진수 중에서 가장 큰 수는 모든 자리가 9로 되어 있는 9999…9999 (9가 50개)이고, 이 수는 2진수로 표현하면 166자리가 됩니다.(2를 밑으로 하는 로그를 통해서 알 수 있죠). 166자리 이진수 하나를 저장하기 위한 메모리는 166비트이고, 바이트로는 21바이트 가량이 됩니다. 일반적인 프로그래밍 언어들의 정수는 4바이트나 8바이트라는 점에서 이 문제는 사실 일반적인 문제는 아니라고 할 수 있습니다. 그렇다고 적절한 정수의 계산만 컴퓨터에 맡기고 큰 정수는 사람이 계산할 수는 없죠. 큰 정수의 계산은 사실 상당히 일반적인 환경에서 요구되기 때문에 많은 언어들이 큰 정수를 계산할 수 있는 기능을 제공하거나 관련한 라이브러리가 준비되어 있는 경우가 많습니다.

파이썬은 기본적으로 자리 수에 제한이 없는 큰 정수를 지원합니다. 개인적으로 C언어 다음으로 파이썬을 공부했었기 때문에 솔직히 파이썬과 비슷한 시기나 그 이후에 나온 언어들은 대부분 정수 크기의 제약에서 자유로울줄 알았는데, 그건 아니더라고요.

어쨌거나 이 문제는 주어지는 수들을 정수로 변환하여 합산하고 다시 문자열로 만들어서 앞 열자리를 출력하면 되는 간단한 문제입니다. 문제의 샘플 값은 사이냅 소프트의 프로젝트 오일러 문제 페이지에서 직접 스크랩해오는 방식으로 구현해보겠습니다.

import re
import requests

url = 'https://euler.synap.co.kr/problem=13'
res = requests.get(url)
html = res.text
mx = [int(x) for x in re.findall(r'\d{50}', html)]
print(str(sum(mx))[:10])

큰 수의 덧셈 구현해보기

큰 정수의 계산 기능을 사용하는 것이 좀 반칙같기도 하고, 문제가 요구하는 본질을 외면하는 것 같은 기분이 든다면 (네, 그건 기분 탓인게 맞습니다.) 직접 구현해볼 수도 있습니다. 최소한 덧셈, 곱셈 및 거듭제곱은 아주 많이 복잡하지는 않습니다. 덧셈, 곱셈은 손으로 계산하는 방식을 그대로 구현하기만 하면 됩니다.

우리는 십진수를 이야기할 때 1의 자리 숫자가 3이라든지, 100의 자리 숫자가 6이라든지 하는 이야기를 합니다. 이는 1이 몇 개, 10이 몇 개, 100이 몇 개이고 이를 합한 것이 그 숫자가 나타내는 정수라는 아이디어로 정리됩니다. 즉, 정수는 0~9의 계수를 가지는 10의 거듭제곱항들의 합인 다항식으로 표현할 수 있습니다.

다항식의 덧셈의 방법을 찾아보면,

  1. 같은 항의 계수끼리 더합니다.
  2. 그 항의 최대값을 벗어나면 해당 항의 단위로 나누고 그 나머지만 취합니다. 몫은 상위 항으로 올려줍니다. (올림)
  3. 최상위 항의 윗항에서도 올림값이 있는지 확인해봅니다.

이 때 우리는 관습적으로 숫자를 왼쪽부터 쓰고 덧셈할 때에는 오른쪽 맞춤으로 식을 씁니다. 다만 이것을 굳이 그대로 표현할 이유는 없기 때문에 왼쪽(앞쪽)이 낮은 자리인 배열로 표현합니다.

3개 이상의 수를 덧셈할 때에는 순차적으로 더하는 것보다, 한 번에 더해도 됩니다. 따라서 가장 긴 숫자의 자릿수에 맞춘 ‘격자’에 숫자들을 넣고 열끼리 더하는 식으로 계산하면 됩니다.

실제 구현은 다음과 같은 세 가지 함수를 만드는 것으로 진행합니다.

  1. 문자열로 표현된 숫자를 정수의 배열로 파싱합니다.
  2. 파싱된 배열들을 다항식의 덧셈 기법으로 더합니다. 그 결과 역시 정수 배열입니다.
  3. 정수배열을 다시 문자열로 덤프합니다.
def parse(s: str) -> list[int]:
    return [int(c) for c in s[::-1]]


def dump(xs: list[int]) -> str:
    return "".join(f"{x}" for x in xs[::-1])

def __add(*args: list[int]) -> list[int]:
    w = max(map(len, args))
    grid = [0] * (w * len(args))
    res = []
    for i, row in enumerate(args):
        grid[i * w : i * w + len(row)] = row
    f = 0
    for i in range(w):
        f, e = divmod(sum(grid[i::w]) + f, 10)
        res.append(e)
    if f > 0:
        res.append(f)
    return res

def add(*args: str) -> str:
    xs = [parse(x) for x in args]
    return dump(__add(*xs))

Julia

Julia에서는 BigInt 라는 타입이 있어서 큰 수의 계산을 할 수 있습니다.

  1. big() 함수를 사용하면 일반 정수 타입 값을 큰 정수로 변환한 후 계산합니다. 그러면 오버플로우 없이 안전하게 큰 정수가 됩니다.
  2. parse(BigInt, x)로 문자열을 큰 정수로 파싱할 수 있습니다.