The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.
[출처 - projecteuler.net/]
이 문제는 무언가 규칙적인 로직을 부여하고 임의의 수가 들어왔을때, 그 로직을 반복하여 수행하는 문제입니다. 단, 이 문제의 규칙을 따라가다보면 언젠가는 해당 로직의 끝은 1이 되게 됩니다. 그 이유는 짝수일 경우 계속 그 수를 반감하기 때문이고, 홀수일때는 억지로 짝수를 만들어 내기 때문입니다.
본문으로 돌아가서 13을 예로 들어 설명했지만, 이해를 돕기위해서 한가지 더 예시를 가정하여 알아보도록 하겠습니다.
3이라는 수가 들어왔을때,
- 3은 홀수이기 때문에 3n + 1을 수행하여 : 10 이 됩니다.
- 10을 짝수이기 때문에 n/2를 수행하여 : 5 가 됩니다.
- 5는 홀수이기 때문에 3n + 1을 수행하여 : 16 이 됩니다.
- 16은 짝수이기 때문에 n/2를 수행하여 : 8 이 됩니다.
- 8은 짝수이기 때문에 n/2를 수행하여 : 4 가 됩니다.
- 4는 짝수이기 때문에 n/2를 수행하여 : 2 가 됩니다.
- 2는 짝수이기 때문에 n/2를 수행하여 : 1 이 되어 종료 되게 됩니다.
결국 3 contains 8 terms 가 됩니다. ( 3 - 10 - 5 - 16 - 8 - 4 - 2 - 1 ) 그렇다면, 문제는 백만까지의 수를 쭉 살펴보았을때 가장 긴 길이의 terms를 가진수는 무엇인가?? 입니다. 뭔가 백만을 구한다고 한다면... 그냥 순회만 한다고 해도 10^6 인데... 그 안에서 엄청난 연산을 한다고 한다면...;; 답이 안보입니다.
그리고 추가적으로, 여기서 의문은 왜 홀수일 때 꼭 3을 곱한다음에 1을 더해서 짝수를 만들까 입니다. 문제가 내포하는 의도가 있겠지만 저는 아직 찾아내지는 못했습니다. 그래서 주어진 로직에서 가장 연산을 효율적으로 할 수 있는 방법을 찾아보았습니다.
1. Basic
저는 일단 규칙적인 홀/짝에 대한 로직이 왜 그렇게 구성을 했는지 간파하지 못한 상태에서, 가장 시간을 줄일 수 있는 방법은 무엇일까?? 고민을 했고... 그 결론은 Memoization으로 귀결되었습니다.
[Memoization이란??]
단순하게 컴퓨터가 반복적인 연산을 수행해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 향후 동일한 계산을 반복해서 계산하지 않고 메모리에서 바로 꺼내 사용할 수 있도록 하는 방식으로... 프로그램의 속도의 엄청난 차이를 불러 올 수 있는 방법입니다.
효율적인 메모리의 추가적인 사용으로 프로그램의 속도를 진짜 어마어마하게 빠르게 만들 수도 있는 기술입니다.
그렇다면 어느 부분에서 Memoization을 사용할 것일까요?? 몇가지의 수를 가지로 해당 로직에 적용해 보면 한가지 효율화 할 방법이 보입니다.
위에서 확인한 3과 문제에서 제공한 13의 결과만 봐도 바로 알 수 있습니다.
3 - 10 - 5 - 16 - 8 - 4 - 2 - 1
13 - 40 - 20 - 10 - 5 - 16 - 8 - 4 - 2 - 1
뭔가 느껴지시는 것이 있으신가요?? 네 맞습니다. 16 - 8 - 4 - 2 - 1 이 부분이 반복 된다는 것을 알 수 있습니다. 그렇다면 16이 가지게 되는 terms를 미리 메모리에 저장하면 어떤 결과가 있을까요?? 13을 진행할때 13 - 40 - 20 - 10 - 5 까지만 계산하고 16에서는 메모리에 저장된 값을 리턴해서 그 값에 13 - 40 - 20 - 10 - 5의 갯수인 5를 더해주면 됩니다.
자 그렇다면, 해당 로직은 어떻게 구현해야 할까요?? 저는 아래의 4단계로 구현했습니다.
- memoization용으로, 0으로 초기화된 list를 우선 특정개수 만큼 생성 (저는 100만개를 생성했습니다.)
- list에서 1에 해당하는 위치에 1의 값을 할당
- 메모리에 값이 없는 경우, temp로 list를 만들어서 순서대로 값을 임시저장 (단, 메모리에 있는경우 반복 종료)
- 해당 temp를 역으로 꺼내면서 메모리값에 +1을 하면서 해당 값이 100만보다 작으면 메모리에 결과 저장
이렇게 되면, 100만까지의 결과는 모두 메모리에 저장이 되고 지속적으로 입력되는 1 ~ 100만의 로직 연산중에 메모리에 해당되는 값이 있다면 로직을 종료하고 결과를 출력하게 됩니다.
[소스코드]
import time
if __name__ == '__main__':
start = time.time()
res = [0] * 1000000
res[1] = 1
answer = 0
max_point = 0
for i in range(2, 1000001):
temp = []
target = i
chk = 0
while target != 1:
if target < 1000000 and res[target] != 0:
chk = res[target]
break
temp.append(target)
if target % 2 == 0:
target //= 2
else:
target = target * 3 + 1
# 일부 Memoization 수행
for j in range(len(temp)):
if temp[len(temp)-j-1] < 1000000:
res[temp[len(temp)-j-1]] = chk + j + 1
if max_point < chk + len(temp):
max_point = chk + len(temp)
answer = i
print("정답 : ", answer)
end = time.time()
print("소요시간 : ", end - start)
해당 소스의 로직은 우선 chain의 시작이 되는 수를 구하고자 하는 범위인 100만까지 순차적으로 loop를 돌립니다.
그리고 그 시작점을 target이라고 하고 로직을 반복하여 1일 될때까지 while로 반복합니다. 이때, 로직의 단계별 수가 memoization되어있는 수면 결과를 리턴하고 반복을 종료합니다.
그리고 도중에 memoization이 안되있는 chain의 구성원은 memoization을 수행해 줍니다. 그리고 진행하면서 최대값을 구해서 그 위치를 리던하면 모든 로직이 종료되게 됩니다.
[결과]
정답 : 837799
소요시간 : 2.689000129699707다음과 같습니다. 그래도 약 3초 이내에 100만까지의 연산이 종료됩니다. 이제는 부하가 주어지는 경우에 대해서는 어떻게 동작하는지 알아보고... 혹시나 코드의 변경이 필요하다면 Advance를 진행해 보겠습니다. 아니라면... 조건과 그 결과를 공유해 보겠습니다.
- Ayotera Lab -
댓글