3N+1Problem - Revision history

Maintenance script: Repair batch-0001 pages from live compare

2026-03-26T23:55:58Z

Repair batch-0001 pages from live compare

← Older revision		Revision as of 23:55, 26 March 2026
Line 40:		Line 40:
	\| 실행시간(i=1,j=999999 기준 4초 통과)		\| 실행시간(i=1,j=999999 기준 4초 통과)
	\|-		\|-
	\| 강희경		\| [[강희경]]
	\| Python		\| Python
	\| 1시간		\| 1시간
Line 46:		Line 46:
	\| X		\| X
	\|-		\|-
	\| 황재선		\| [[황재선]]
	\| Python		\| Python
	\| ?		\| ?
	\| 3N+1Problem/황재선		\| [[3N+1Problem/황재선]]
	\| .		\| .
	\|-		\|-
Line 58:		Line 58:
	\| .		\| .
	\|-		\|-
	\| 문보창		\| [[문보창]]
	\| C++		\| C++
	\| ?		\| ?
	\| 3N+1Problem/문보창		\| [[3N+1Problem/문보창]]
	\| X		\| X
	\|-		\|-
	\| 구자겸		\| [[구자겸]]
	\| C		\| C
	\| ?		\| ?
	\| 3N+1Problem/구자겸		\| [[3N+1Problem/구자겸]]
	\| .		\| .
	\|-		\|-
	\| 신재동		\| [[신재동]]
	\| C++		\| C++
	\| 10분		\| 10분
	\| 3N+1Problem/신재동		\| [[3N+1Problem/신재동]]
	\| .		\| .
	\|-		\|-
	\| Leonardong		\| [[Leonardong]]
	\| Python		\| Python
	\| 46분		\| 46분
	\| 3N+1Problem/Leonardong		\| [[3N+1Problem/Leonardong]]
	\| .		\| .
	\|-		\|-
	\| 곽세환		\| [[곽세환]]
	\| C++		\| C++
	\| ?		\| ?
Line 91:		Line 91:
	\| Python		\| Python
	\| 13분		\| 13분
	\| 3N+1Problem/1002		\| [[3N+1Problem/1002]]
	\| .		\| .
	\|-		\|-
Line 97:		Line 97:
	\| Python		\| Python
	\| 30분		\| 30분
	\| 3N+1Problem/1002_2		\| [[3N+1Problem/1002_2]]
	\| No-Psyco : 9.25초, With-Psyco : 3.8초		\| No-Psyco : 9.25초, With-Psyco : 3.8초
	\|-		\|-
	\| 허아영		\| [[허아영]]
	\| C++		\| C++
	\| 1시간 20분		\| 1시간 20분
	\| 3N 1Problem/허아영		\| [[3N 1Problem/허아영]]
	\| .		\| .
	\|-		\|-
Line 112:		Line 112:
	\| .		\| .
	\|-		\|-
	\| 임인택		\| [[임인택]]
	\| HaskellLanguage		\| [[HaskellLanguage]]
	\| 30분		\| 30분
	\| [http://janbyul.com/moin/moin.cgi/HaskellLanguage/3N%2B1Problem 여기]		\| [http://janbyul.com/moin/moin.cgi/HaskellLanguage/3N%2B1Problem 여기]
Line 121:		Line 121:
	\| C++		\| C++
	\| 엄청..ㅡㅜ		\| 엄청..ㅡㅜ
	\| 3N+1/김상섭		\| [[3N+1/김상섭]]
	\| .		\| .
	\|}		\|}
Line 143:		Line 143:

	=== 쓰레드 ===		=== 쓰레드 ===
	실행시간(i=1,j=1000000 기준 4초 통과)는 파이썬의 경우 가능할런지 모르겠네요. 나름대로 알고리즘을 보강했는데도 1, 100000에 빌빌 거리니...--강희경		실행시간(i=1,j=1000000 기준 4초 통과)는 파이썬의 경우 가능할런지 모르겠네요. 나름대로 알고리즘을 보강했는데도 1, 100000에 빌빌 거리니...--[[강희경]]

	----		----
	문제분류		[[문제분류]]

Maintenance script: Repair pages found by live-compare batch 0001

2026-03-26T14:46:17Z

Repair pages found by live-compare batch 0001

← Older revision		Revision as of 14:46, 26 March 2026
Line 32:		Line 32:

	=== 풀이 ===		=== 풀이 ===
	{\| class="wikitable"		{\| class="wikitable" style="width:100%;"
	\|-		\|-
	\| 작성자		\| 작성자
Line 40:		Line 40:
	\| 실행시간(i=1,j=999999 기준 4초 통과)		\| 실행시간(i=1,j=999999 기준 4초 통과)
	\|-		\|-
	\| [[강희경]]		\| 강희경
	\| Python		\| Python
	\| 1시간		\| 1시간
Line 46:		Line 46:
	\| X		\| X
	\|-		\|-
	\| [[황재선]]		\| 황재선
	\| Python		\| Python
	\| ?		\| ?
	\| [[3N+1Problem/황재선]]		\| 3N+1Problem/황재선
	\| .		\| .
	\|-		\|-
	\| [[김회영]]		\| 김회영
	\| C++		\| C++
	\| ?		\| ?
Line 58:		Line 58:
	\| .		\| .
	\|-		\|-
	\| [[문보창]]		\| 문보창
	\| C++		\| C++
	\| ?		\| ?
	\| [[3N+1Problem/문보창]]		\| 3N+1Problem/문보창
	\| X		\| X
	\|-		\|-
	\| [[구자겸]]		\| 구자겸
	\| C		\| C
	\| ?		\| ?
	\| [[3N+1Problem/구자겸]]		\| 3N+1Problem/구자겸
	\| .		\| .
	\|-		\|-
	\| [[신재동]]		\| 신재동
	\| C++		\| C++
	\| 10분		\| 10분
	\| [[3N+1Problem/신재동]]		\| 3N+1Problem/신재동
	\| .		\| .
	\|-		\|-
	\| [[Leonardong]]		\| Leonardong
	\| Python		\| Python
	\| 46분		\| 46분
	\| [[3N+1Problem/Leonardong]]		\| 3N+1Problem/Leonardong
	\| .		\| .
	\|-		\|-
	\| [[곽세환]]		\| 곽세환
	\| C++		\| C++
	\| ?		\| ?
Line 91:		Line 91:
	\| Python		\| Python
	\| 13분		\| 13분
	\| [[3N+1Problem/1002]]		\| 3N+1Problem/1002
	\| .		\| .
	\|-		\|-
Line 97:		Line 97:
	\| Python		\| Python
	\| 30분		\| 30분
	\| [[3N+1Problem/1002_2]]		\| 3N+1Problem/1002_2
	\| No-Psyco : 9.25초, With-Psyco : 3.8초		\| No-Psyco : 9.25초, With-Psyco : 3.8초
	\|-		\|-
	\| [[허아영]]		\| 허아영
	\| C++		\| C++
	\| 1시간 20분		\| 1시간 20분
	\| [[3N 1Problem/허아영]]		\| 3N 1Problem/허아영
	\| .		\| .
	\|-		\|-
	\| [[이도현]]		\| 이도현
	\| C++		\| C++
	\| 1시간		\| 1시간
	\| [[3n+1/이도현]]		\| 3n+1/이도현
	\| .		\| .
	\|-		\|-
	\| [[임인택]]		\| 임인택
	\| [[HaskellLanguage]]		\| HaskellLanguage
	\| 30분		\| 30분
	\| [http://janbyul.com/moin/moin.cgi/HaskellLanguage/3N%2B1Problem 여기]		\| [http://janbyul.com/moin/moin.cgi/HaskellLanguage/3N%2B1Problem 여기]
	\| .		\| .
	\|-		\|-
	\| [[김상섭]]		\| 김상섭
	\| C++		\| C++
	\| 엄청..ㅡㅜ		\| 엄청..ㅡㅜ
	\| [[3N+1/김상섭]]		\| 3N+1/김상섭
	\| .		\| .
	\|}		\|}
Line 129:		Line 129:

	* 기존의 코드를 수정해서 가장 큰 Cycle Length 가 아닌 3번째로 큰 Cycle Length 를 구해보세요.		* 기존의 코드를 수정해서 가장 큰 Cycle Length 가 아닌 3번째로 큰 Cycle Length 를 구해보세요.
	{\| class="wikitable"		{\| class="wikitable" style="width:100%;"
	\|-		\|-
	\| 작성자		\| 작성자
Line 143:		Line 143:

	=== 쓰레드 ===		=== 쓰레드 ===
	실행시간(i=1,j=1000000 기준 4초 통과)는 파이썬의 경우 가능할런지 모르겠네요. 나름대로 알고리즘을 보강했는데도 1, 100000에 빌빌 거리니...--[[강희경]]		실행시간(i=1,j=1000000 기준 4초 통과)는 파이썬의 경우 가능할런지 모르겠네요. 나름대로 알고리즘을 보강했는데도 1, 100000에 빌빌 거리니...--강희경

	----		----
	[[문제분류]]		문제분류

imported>qa22ahj at 06:25, 17 November 2013

2013-11-17T06:25:26Z

← Older revision	Revision as of 06:25, 17 November 2013
(No difference)

imported>qa22ahj at 06:17, 17 November 2013

2013-11-17T06:17:41Z

← Older revision		Revision as of 06:17, 17 November 2013
Line 19:		Line 19:

	정수 i와 j 에 대해 두 수 사이에 존재하는 cycle-length 값들중의 최대값을 구할 것이다. 입력은 아래와 같이 한 줄에 한 쌍의 정수로 이루어져 있다. 출력값은 이 두 정수 사이의 cycle-length 중에서 최대값을 구하는 것이다.		정수 i와 j 에 대해 두 수 사이에 존재하는 cycle-length 값들중의 최대값을 구할 것이다. 입력은 아래와 같이 한 줄에 한 쌍의 정수로 이루어져 있다. 출력값은 이 두 정수 사이의 cycle-length 중에서 최대값을 구하는 것이다.
	~~만약 입력이 다음과 같다면,~~		=== 입력 ===
	~~{{\|~~		1 10
	1 10		100 200
	100 200		201 210
	201 210		900 1000
	900 1000
	~~\|}}~~

	~~출력은 아래와 같아야 할 것이다.~~		=== 출력 ===
	~~{{\|~~		1 10 20
	1 10 20		100 200 125
	100 200 125		201 210 89
	201 210 89		900 1000 174
	900 1000 174
	~~\|}}~~

	=== 풀이 ===		=== 풀이 ===

imported>linflus at 07:07, 22 May 2011

2011-05-22T07:07:59Z

New page

학교에서 무료함을 달래기 위해 acm programming contest 기출문제를 풀어보는데, ToyProblems 에서도 다룰만한 쉬운 문제가 있기에 이렇게 소개합니다. [http://acm.uva.es/p/v1/100.html 원문보기]
----
=== 이 문제는 ===
인기도:A(A,B,C), 성공률:낮음(낮음,보통,높음), 레벨:1(1~4)

CS에서 등장하는 문제의 종류는 여러가지가 있는데 (예를 들어, NP, Unsolvable, Recursive...) 이 문제는 '입력에 대해 출력이 어떻게 나올지 모르는' 이라고 분류할만한 것에 대한 분석을 하는 것이다. (해석이 애매하군요; )

다음과 같은 알고리즘이 있다
1. input n
2. print n
3. if n == 1 then STOP
4. if n is odd then n = 3n + 1
5. else n = n/2
6. GOTO 2

만약 입력으로 22가 주어졌을때 출력값은 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 가 될 것이다. 이 알고리즘은 간단해 보이지만 n의 값이 1로 되어 알고리즘이 종료될지는 모르는 일이다. 하지만 이는 0과 1000000 사이의 숫자, 아니 이보다 더 큰 숫자에 대해서도 n의 값이 1이 된다고 증명되었다.

입력으로 22가 주어졌을때, 출력되는 값의 수 n(22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1) 는 22 16이다. 이를 n에 대한 cycle-length 라고 한다.

정수 i와 j 에 대해 두 수 사이에 존재하는 cycle-length 값들중의 최대값을 구할 것이다. 입력은 아래와 같이 한 줄에 한 쌍의 정수로 이루어져 있다. 출력값은 이 두 정수 사이의 cycle-length 중에서 최대값을 구하는 것이다.
만약 입력이 다음과 같다면,
{{|
1 10
100 200
201 210
900 1000
|}}

출력은 아래와 같아야 할 것이다.
{{|
1 10 20
100 200 125
201 210 89
900 1000 174
|}}

=== 풀이 ===
{| class="wikitable"
|-
| 작성자
| 사용언어
| 개발시간
| 코드
| 실행시간(i=1,j=999999 기준 4초 통과)
|-
| [[강희경]]
| Python
| 1시간
| [[3N+1Problem/강희경]]
| X
|-
| [[황재선]]
| Python
| ?
| [[3N+1Problem/황재선]]
| .
|-
| [[김회영]]
| C++
| ?
| [[3N+1Problem/김회영]]
| .
|-
| [[문보창]]
| C++
| ?
| [[3N+1Problem/문보창]]
| X
|-
| [[구자겸]]
| C
| ?
| [[3N+1Problem/구자겸]]
| .
|-
| [[신재동]]
| C++
| 10분
| [[3N+1Problem/신재동]]
| .
|-
| [[Leonardong]]
| Python
| 46분
| [[3N+1Problem/Leonardong]]
| .
|-
| [[곽세환]]
| C++
| ?
| [[3N+1Problem/곽세환]]
| .
|-
| [1002]
| Python
| 13분
| [[3N+1Problem/1002]]
| .
|-
| [1002]
| Python
| 30분
| [[3N+1Problem/1002_2]]
| No-Psyco : 9.25초, With-Psyco : 3.8초
|-
| [[허아영]]
| C++
| 1시간 20분
| [[3N 1Problem/허아영]]
| .
|-
| [[이도현]]
| C++
| 1시간
| [[3n+1/이도현]]
| .
|-
| [[임인택]]
| [[HaskellLanguage]]
| 30분
| [http://janbyul.com/moin/moin.cgi/HaskellLanguage/3N%2B1Problem 여기]
| .
|-
| [[김상섭]]
| C++
| 엄청..ㅡㅜ
| [[3N+1/김상섭]]
| .
|}

See also BioinfoWiki:AlgorithmQuiz/3Plus1
=== 문제 2탄 ===

* 기존의 코드를 수정해서 가장 큰 Cycle Length 가 아닌 3번째로 큰 Cycle Length 를 구해보세요.
{| class="wikitable"
|-
| 작성자
| 사용언어
| 개발(수정)시간
| 코드
|-
| [1002]
| Python
| 16분(3분)
| .
|}

=== 쓰레드 ===
실행시간(i=1,j=1000000 기준 4초 통과)는 파이썬의 경우 가능할런지 모르겠네요. 나름대로 알고리즘을 보강했는데도 1, 100000에 빌빌 거리니...--[[강희경]]

----
[[문제분류]]