More actions
접근
연습장에서 이것저것 적어보기 시도. 처음에는 각 결과 수 간에 무언가 수열이 있을까 해서 적어봄.
1 2 8 3 6 9 17 4 20 7 9 1 6 -5 3 3 8 -13 17 -13 2
도저히 수열스럽지 않아서 다시 숫자들 간의 관계를 이리 적어보던중, 지난번의 UglyNumber 에서의 문제접근법(DynamicProgramming)을 해봄. 혹시 앞의 계산값이 뒤의 계산에 이용되지 않을까 생각을 해보다.
n 값의 변화 1 : 1 2 : 2 -> 1 3 : 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 4 : 4 -> 2 -> 1 . .
숫자들을 주욱 나열해보면서 해당 n 값 대비 count cycle Length 의 값은 고정적일것이라는 점과, 이 값을 일종의 caching 을 하여 이용할 수 있겠다는 생각이 들다.
연습장에 의사 코딩 5분정도 한 뒤, 바로 코드로 옮기고 실행.
class CycleLength:
def __init__(self):
self._cache = {1:1}
def createTable(self,i,j):
return [self.value(each) for each in range(i,j)]
def value(self,n):
if self._cache.get(n) is not None: return self._cache.get(n)
if n % 2 == 1:
self._cache[n] = self.value(3*n+1)+1
return self._cache[n]
else:
self._cache[n] = self.value(n/2)+1
return self._cache[n]
def maxCycleLengthInRange(self,i,j):
#return max(self.createTable(i,j))
maxValue=0
for each in range(i,j):
maxValue = max(maxValue,self.value(each))
return maxValue
def testOne():
r"""
>>> c=CycleLength()
>>> [c.value(n) for n in range(1,5)]
[1, 2, 8, 3]
>>> c.maxCycleLengthInRange(1,10)
20
>>> c.maxCycleLengthInRange(100,200)
125
>>> c.maxCycleLengthInRange(201,210)
89
>>> c.maxCycleLengthInRange(900,1000)
174
"""
def main():
import doctest
doctest.testmod()
def main2():
c=CycleLength()
print c.maxCycleLengthInRange(1,999999)
if __name__=="__main__":
import time
start=time.time()
import psyco
psyco.bind(main2)
main2()
end = time.time()
print "time :", end-start
느낀점
지난번의 문제를 풀었을때 '접근법' 도 같이 생각하여 문제 해결방법을 익힌것이 추후의 문제(결과 상으로는 전혀 다른 알고리즘)의 해결법을 알아내는데 좋은 접근법을 제공해준 것이 느낌이 좋았다. 새 해결책을 떠올리는데 10분이 안걸리고, 비교적 효과적인 알고리즘이 나온 점에서 기분이 좋은 중.
--[1002]
http://gochi.pe.kr/upload/img/code/3npuls1problem.jpg ~cpp CycleLength.value
