2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2^1000?
[출처 - projecteuler.net/]
이번에는 문제가 엄청 짧습니다. 문제만 본다면 단순하게 그냥 2에 대해서 거듭제곱을 계속하여 원하는 만큼 수행했을때, 결과값에 대해서 각 자리수에 대한 단순합을 구하는 문제입니다. 하지만 15번 거듭제곱을 수행하면, 누구는 그냥 머리도로 구할 수 있을 것 입니다.
2^10 * 2^5 = 1,024 * 32 = 32,768 이 되겠죠. 그럼 문제와 같이 각 자리수를 더해서 26을 바로 도출해 낼 수 있습니다. 하지만 1,000번이나 거듭제곱을 한다면... 이건 머리로는 불가능하고 프로그래밍을 통해서 구현을 한다고 해도 얼마나 큰 자리수가 될 지... 얼마나 연산을 수행할지... 그 연산이 가능할지도 두렵습니다. 하지만 가능한 여러가지 방법에 대해서 한번 구현해 보겠습니다.
이 문제를 구현하려면, 여러가지 고려할 점이 있습니다.
- 해당 언어에서 제공하는 숫자형 변수가, 2^1000으로 예상되는 값을 저장이 가능한지??
- 불가능하다면, 어떤방법으로 구현할지??
뭐 가볍게 생각하면 2개정도 이겠네요?? 그럼 2가지에 대해서 구현해 보겠습니다. 해당 방식들에 대해서 동작 시간도 함게 알아보겠습니다.
1. 특정 자료형을 통한 해결
모든 프로그램언어는 각기 다양한 (그래도 대부분은 거의 동일한) 자료형을 가지고 있습니다. 그 중에서 해당 문제를 해결하기 위해서는 숫자 자료형에 대해서 알아야 합니다.
[C++]
- bool (정수형) : 1 byte (0 ~ 1)
- signed short (정수형) : 2 byte (-32,768 ~ 32,767)
- unsigned short (정수형) : 2 byte (0 ~ 65,535)
- signed int (정수형) : 4 byte (-2,147,483,648 ~ 2,147,483,647)
- unsigned int (정수형) : 4 byte (0 ~ 4,294,967,295)
- long long (정수형) : 8 byte (-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807)
- unsigned long long (정수형) : 8 byte (0 ~ 18,446,744,073,70,551,615)
[JAVA]
- boolean (정수형) : 1 byte (0 ~ 1)
- short (정수형) : 2 byte (-32,768 ~ 32,767)
- int (정수형) : 4 byte (-2,147,483,648 ~ 2,147,483,647)
- long (정수형) : 8 byte (-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807)
- BigInteger : long을 초과하는 큰 수를 다루기 위한 문자열 구성
[Python]
일단 이 언어는 참으로 특이합니다. 해당 언어는 동적 타입핑 (Dynamic Typing)언어로 즉 변수에 대한 자료형 선언없이 그냥 입력되는 상황에 맞게 알아서 그 객체를 생성합니다. 따라서 고민없이 사용하면 되지만 타 언어에 비해서 성능이 떨어 질 수 밖에 없습니다. 하지만 알고리즘에 입각하여 효율성 측면을 생각한다면 매우 편하고, 안전한 언어임에 틀림이 없습니다.
다시 문제로 돌아오자면, 2^1000의 자리수만 생각해 보면...
2^10이 1,024이니 10^3이라고 생각하고,
2^1000 = 2^10^100 = 10^3^100 = 10^300 이 됩니다.
따라서 10의 300승이면 총 301자리의 숫자를 담을 변수 공간이 필요하게 됩니다. 따라서, JAVA의 경우에도 BigInteger를 사용해야하고, C++의 경우도 뭔가 고민을 해야겠죠. 하지만!!! 우리의 Python은 그냥 하나의 변수에 뿅하고 들어가게 됩니다.
코드로 구현해서 확인해 보면 다음과 같습니다.
[소스코드]
import time
def preCalc():
mem = []
for i in range(10001):
mem.append(2 ** i)
return mem
if __name__ == '__main__':
# 목표치까지 거듭제곱 수 선 진행 및 결과저장
start = time.time()
mem = preCalc()
end = time.time()
print("선진행 소요시간 : ", end - start)
print(type(mem[10000]))
print(mem[10000])
tc = int(input())
for t in range(tc):
target = int(input())
start = time.time()
pickMem = str(mem[target])
res = 0
for i in range(len(pickMem)):
res += int(pickMem[i])
print(res)
end = time.time()
print("개별결과연산 소요시간 : ", end - start)
우선 요즘 자주 사용하는 Memoization을 선 진행했습니다. 보통 뭔가 부하를 위해서는 다량의 데이터를 집어넣고 해당결과가 얼마나 빨리나오게 하는지가 중요하기 때문에 살짝 고민을 해 본 것이지요. Python을 사용한다는 이유로... 아무생각없이 그냥 거듭제곱을 구해서 저장했습니다.
고민은 했지만, 별 복잡한 코드없이 구한 값이 과연 어떤 형태인지 그 결과는 무엇인지 확인해 보겠습니다.
<class 'int'>
107150860718626732094842504906000181056140481170553360744375038837035105112493612249
319837881569585812759467291755314682518714528569231404359845775746985748039345677748
242309854210746050623711418779541821530464749835819412673987675591655439460770629145
71196477686542167660429831652624386837205668069376
총 자리수 : 302무려 302자리로 구성된 2^1000은 int 형이며... 저렇게 긴 아이가 숫자형입니다. 일단 결과를 확인해 보겠습니다.
[결과]
선진행 소요시간 : 0.4070000648498535
<class 'int'>
302
1
1000
결과 : 1366
개별결과연산 소요시간 : 0.02^10000까지 Memoization을 수행하면, 0.4초 가 소요됩니다. 또한, 2^1000에 대한 결과 및 소요시간을 위와 같습니다. 이렇게 문제는 해결이 되었지만, 다른 방법으로도 한번 구현해 보겠습니다.
2. 문자열 방식으로 구현
이번에도 동일하게 2^10000까지 Memoization을 수행합니다. 대신 방식을 기본 숫자자료형을 사용하는 것이 아니고, 문자형을 가지고 조작하여 구현을 해보겠습니다.
- string을 담을 list를 생성하고, 0의 위치를 '1'로 초기화 수행
- 1 ~ 10000까지 순회를 구성하고, 그 시작은 직전위치의 string list를 꺼내서 임시 변수에 저장
- 임시변수에 저장된 string을 다시 내부 순회를 하여 각 자리수 별로 2를 곱해주고 그 결과를 저장
- remains를 이용해서 올림수를 계산하고, 최종 순회를 마치고 0이 아닐경우 string끝에 값을 추가
- string을 담는 list에 저장
이걸 10000번 반복하면 2의 승수에 대한 10000까지의 값이 string으로 저장이 됩니다. 그리고 내가 원하는 값을 뽑아서 계산만 해주면 됩니다. 과연 이 방법은 얼마나 걸릴까요??
[소스코드]
import time
def preCalc():
mem = []
mem.append('1')
for i in range(1, 10001):
temp = mem[i-1]
remains = 0
input_temp = ''
for j in range(len(temp)):
remains += int(temp[j])*2
input_temp += str(remains % 10)
remains //= 10
if remains != 0: input_temp += str(remains)
mem.append(input_temp)
return mem
if __name__ == '__main__':
start = time.time()
mem = preCalc()
end = time.time()
print("선진행 소요시간 : ", end - start)
tc = int(input())
for i in range(tc):
case = int(input())
start = time.time()
res = 0
target = mem[case]
for j in range(len(target)):
res += int(target[j])
print(res)
end = time.time()
print("개별결과연산 소요시간 : ", end - start)[결과]
1
1000
선진행 소요시간 : 11.570000171661377
1366
개별결과연산 소요시간 : 0.0무려 11.5초에 해당하는 시간동안 연산을 수행합니다. 물론 그 뒤로는 연산에 추가 시간이 소요되지는 않겠지만 초기 구성에 대한 시간이 너무 걸리네요. 우선 해당 문제는 1번의 방식으로 구현해야겠습니다.
- Ayotera Lab -
댓글