[알고리듬] #70 3N+1 문제(1)

[key word] 콜라츠 추측, 우박수, 타임 모듈, 에포크 타임

파이썬 실습창을 열 수 있습니다.실습창 열기

3N+1의 변화도

 

3N+1 문제

[배경]

3N+1 문제(The 3n+1 problem)는 알고리듬을 공부하는 사람들이 통과의례처럼 해결해야 하는 문제로 알려져 있다.

우리도 이 문제를 해결하고 알고인(algo人)이 되자.

 

[문제]

수열을 만드는 다음과 같은 방법을 생각하여 보자.

정수 n으로 시작한다. n이 짝수이면 2로 나누고, n이 홀수이면 3을 곱하고 1을 더한다.

새로운 n이 1이 될 때까지 이 과정을 반복한다.

 

예를 들어, 다음 수열은 n=22인 경우이다.

        22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

이 방법은 모든 정수 n에 대하여 n=1에서 종료될 것으로 예상(아직 증명되지 않았지만)된다. 하지만, 적어도 1,000,000까지의 모든 정수에 대해서는 예상대로이다. 입력한 n에 대해서, n의 반복회수(cycle-length)는 생성된 숫자의 개수인데 1도 포함한다.

위의 예에서 보듯이 22의 반복회수는 16이다.

 

당신이 해야 할 일은 임의의 2개의 수 i와 j가 주어지면, i와 j 사이의 모든 수들에 대하여 최대 반복회수를 구하는 것이다.

i와 j도 포함한다.

 

입력

입력은 각 줄마다 있는 정수 i와 j 사이의 수열이다.

모든 정수는 1,000,000보다 작고 0보다 크다.

 

출력

입력된 정수 i와 j에 대하여, 출력은 입력된 순서대로 i와 j를 적고, 이어서 i, j를 포함한 i와 j 사이의 정수에 대한 최대 반복회수를 적는다. 이러한 3개의 숫자는 입력의 한 줄이 출력의 한 줄이 되도록 하여, 한 줄에 3개씩, 한 칸씩 띄어서 출력한다.

 

입력의 예

1 10

100 200

201 210

900 1000

1000 900

999999 1

 

출력의 예

1 10 20

100 200 125

201 210 89

900 1000 174

1000 900 174

999999 1 525

 

1. 문제 분석

1-1 cycle-length

전체 문제를 해결하기 전에 정수 n의 cycle-length를 구하여 봅시다.

n=22
cycle=0
while n!=1:
    if n%2==0: n//=2
    else: n=n*3+1
    cycle+=1
print(cycle)

 

결과가 15입니다. 문제에서는 16으로 설명하였는데 무엇이 잘못되었지요?

잘못을 찾아서 바르게 수정한 다음에 아래를 보세요.

cycle-length에 자신도 포함되어야 하는데 자신은 헤아리지 않았다.

즉, 22는 헤아리지 않았다.

해결방법은?

length=0을 length=1로 바꾸어야 한다.

 1-2 방법 개선

홀수 n에 대하여 3n+1을 하면 반드시 짝수가 됩니다.

이 사실을 적용하면 실행시간을 단축할 수 있을 것 같습니다.

다시 코딩하여 보세요.

n=22
cycle=1
while n!=1:
    if n%2==0:
        n//=2
        cycle+=1
    else:
        n=n*3+1     # 새로운 n은 반드시 짝수이므로
        n//=2        # n을 2로 나눈다
        cycle+=2    # 사이클은 2개가 증가한다.
print(cycle)

1-3 최대 사이클 길이

임의의 정수 a에서 b까지의 수에서 최대 cycle-length를 구하여 보세요.

a,b=100,200                 # 임의의 수
max=0
for n in range(a,b+1):
    cycle=1                 # 자기 자신
    while n!=1:
        if n%2==0:          
            n//=2
            cycle+=1
        else:
            n=n*3+1
            n//=2
            cycle+=2
    if max<cycle:max=cycle
print(max)

'''
경과는 125 입니다.

a가 b보다 큰 경우에는 a와 b를 바꾸어야 합니다.
다음과 같이 교환하는 문장을 삽입하면 됩니다.
a,b=100,200
if a>b:a,b=b,a
max=0
:
:

다음과 같이 코딩할 수도 있습니다.
a,b=100,200                 # 임의의 수
max=0
for n in range(a,b+1):
    cycle=1                 # 자기 자신
    while n!=1:
        if n%2==1:
            n=n*3+1
            cycle+=1
        n//=2
        cycle+=1        
    if max<cycle:max=cycle
print(max)
'''

 

1-4  전체 문제 해결

입력 data가 많은 전체 문제를 해결하였습니다.

import time                       # 처리 시간 체크
data=list((iter(input,'')))       # 데이터 키보드 입력, Null까지 반복(마지막에 엔터키)
start=time.time()                 # 입력 시간 제외하고 처리시간 구함
for x in data:                    # data--> ['1 10','100 200', ...]
    ta,tb=map(int,x.split())      # ta, tb는 출력에 사용
    a,b=ta,tb
    if a>b:a,b=b,a                # 크기 순으로 바꿈
    max=0
    for n in range(a,b+1):
        cycle=1
        while n!=1:
            if n%2==0:
                n//=2
                cycle+=1
            else:
                n=n*3+1
                n//=2
                cycle+=2
        if max<cycle:max=cycle
    print(ta,tb,max)               # 출력형식에 맞게 출력
    
end=time.time()
run=end-start                      # 실핸시간(wall-clock time)
print(run)

'''
바른 결과가 출력됩니다.
처리 시간은 나의 컴퓨터에서 31.1224205493927 초입니다.
'''

31초 정도가 걸렸지만 잘 실행됩니다.

그런데 이 문제에는 제한 시간이 있습니다.

         Time limit: 3.000 seconds

즉, 3초 이내에 해결해야 합니다.

과연 3초 이내에 실행시킬 방법이 있을까요?

다음 시간에는 이 방법을 찾아봅시다.

 

[참고] time module(타임 모듈)

●

time()함수는 그리니치 표준시(GMT) 1970년 1월 1일 00:00:00부터 현재까지의 경과 시간(elapsed time)을 초 단위로 반환한다. 윤초(leap second)는 반영하지 않는다. 기준 시각(epoch time, 에퍼크 타임)이 1970년인 것은 UNIX os에서 처음 이렇게 사용하였기 때문이다. 이러한 시간을 UNIX time이라고도 하는 이유이기도 하다.

 

●

epoch time(기준 시각)은 다음 프로그램으로 확인할 수 있다.

import time

a=time.gmtime(0)

print(a)

 

●

실행시간을 측정하는 다른 방법도 있다.

from timeit import timeit

t=timeit('sqrt(2.0)', 'from math import sqrt')

print(t)

벤치마크 코드를 100만 번 실행한 시간이 출력된다.

벤치마크 코드(benchmark code)란 테스트할 코드인데 위의 예에서는 2의 제곱근을 구하는 sqrt(2.0)이다.

실행시간은 0.10166270000001987초이었다.

컴퓨터에 따라 달라진다.

수고하셨습니다.

안녕!