Maintenance script: Repair MoniWiki formatting after migration

2026-03-26T14:01:35Z

Repair MoniWiki formatting after migration

← Older revision		Revision as of 14:01, 26 March 2026
Line 72:		Line 72:

	--[1002]		--[1002]
	http://gochi.pe.kr/upload/img/code/3npuls1problem.jpg		http://gochi.pe.kr/upload/img/code/3npuls1problem.jpg <br />
	''		''
	~cpp CycleLength.value		~cpp CycleLength.value
	와 거의 비슷한 의사코드가 [[이덕준]]의 연습장에도... 무척 반가움. --[[이덕준]]''		와 거의 비슷한 의사코드가 [[이덕준]]의 연습장에도... 무척 반가움. --[[이덕준]]''

imported>Unknown at 05:22, 7 February 2021

2021-02-07T05:22:15Z

New page

=== 접근 ===
연습장에서 이것저것 적어보기 시도. 처음에는 각 결과 수 간에 무언가 수열이 있을까 해서 적어봄.
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
와 거의 비슷한 의사코드가 [[이덕준]]의 연습장에도... 무척 반가움. --[[이덕준]]''

3N+1Problem/1002 2 - Revision history

Maintenance script: Repair MoniWiki formatting after migration

imported>Unknown at 05:22, 7 February 2021