현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

프로그래밍 첼린지 책 문제 풀어보신 분 =ㅁ=;

jenix의 이미지
글쓴이: jenix / 작성시간: 수, 2004/12/29 - 10:46오전

안녕하세요.

어제 책을 사서 오늘 보기 시작했는데,

1번 문제부터 난관이군요 -_-;

제가 보기엔 결과는 정상적으로 나오는데,

www.programming-challenges.com 로봇이 Wrong Answer 라고

자꾸 화를 내서 :oops:

      1 /* @JUDGE_ID: jenix 110101 C "simple loop" */
      2 /* @BEGIN_OF_SOURCE_CODE */
      3 #include <stdio.h>
      4
      5 long algorithm(long num);
      6 long check(long i, long j);
      7
      8 long algorithm(long num)
      9 {
     10     long count = 0;
     11
     12     while( num != 1 )
     13     {
     14         if(num%2 == 0)
     15             num = num / 2;
     16         else if(num%2 == 1)
     17             num = 3*num + 1;
     18
     19         count++;
     20     }
     21     count++;
     22
     23     return count;
     24 }
     25
     26 long check(long i, long j)
     27 {
     28     long max = 0;
     29     long result;
     30
     31     for(;i<=j;i++)
     32     {
     33         result = algorithm(i);
     34         if( max < result )
     35             max = result;
     36     }
     37
     38     return max;
     39 }
     40
     41 void main(void)
     42 {
     43     long i,j;
     44
     45     while(scanf("%ld %ld",&i,&j) == 2)
     46         printf("%ld %ld %ld\n",i,j,check(i,j));
     47 }
     48 /* @END_OF_SOURCE_CODE */

위와 같이 작성했습니다만..

문제는 다음과 같습니다.

어떤 정수 n에서 시작해 n 이 짝수이면 2로 나누고, 홀수이면 3을 곱하고 1을 더해서 n=1 일때 까지 반복. 
예 > n = 22 이면, 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 , 수열의 수가 16. 
입력 i, j 가 주어지면 i,j 에서 위의 수열의 최대 길이 출력
예 >
1 10 -> 1 10 20
100 200 -> 100 200 125
File attachments: 
첨부파일 크기
Image icon 도식화.JPG15.07 KB
Forums: 
프로그래밍 QnA
다즐링의 이미지

글쓴이: 다즐링 / 작성시간: 수, 2004/12/29 - 11:13오전 

#!/usr/bin/python
import sys
if len(sys.argv) != 2:
        raise SystemExit
else:
        end = int(sys.argv[1])
data = []
while end != 1:
        if end % 2 == 0:
                def func(a):
                        return a /2
        else:
                def func(a):
                        return a * 3 + 1
        data.append(end)
        end = func(end)
data.append(end)
print"LENGTH:%s DATA:%s" % ( len(data) ,  repr(data))

------------------------------------------------------------------------------------------------
Life is in 다즐링

jenix의 이미지

글쓴이: jenix / 작성시간: 수, 2004/12/29 - 11:29오전

음

java/c/c++/파스칼

중에서만 해야해서;;

결과는 나오는데;;

사이트 로봇이 인식을 못해요 =ㅁ=;

계속 틀렸다고만 ㅡ,.ㅡ;

---------------------------------------------------------------------------
http://jinhyung.org -- 방문해 보세요!! Jenix 의 블로그입니다! :D

jenix의 이미지

글쓴이: jenix / 작성시간: 수, 2004/12/29 - 11:44오전

긁적

소스가 길어서 그런가 하고

걍 메인 하나로 줄여보기도 했는데

여전히 틀렸다고..

OTL

      1 /* @JUDGE_ID: jenix 110101 C "simple loop" */
      2 /* @BEGIN_OF_SOURCE_CODE */
      3 #include <stdio.h>
      4
      5 void main(void)
      6 {
      7     long i,j;
      8     long max = 0;
      9     long result;
     10     long tmp,tmp2;
     11     int count;
     12
     13     while(scanf("%ld %ld",&i,&j) == 2)
     14     {
     15         tmp2 = i;
     16         for(;i<=j;i++)
     17         {
     18             count = 0;
     19             tmp = i;
     20             while(tmp != 1)
     21             {
     22                 if(tmp%2 == 0)
     23                     tmp = tmp / 2;
     24                 else if(tmp%2 == 1)
     25                     tmp = 3*tmp + 1;
     26                 count++;
     27             }
     28             if( tmp == 1 )
     29                 count++;
     30             if( max < count )
     31                 max = count;
     32         }
     33
     34         printf("%ld %ld %ld\n",tmp2,j,max);
     35         max = 0;
     36     }
     37 }
     38 /* @END_OF_SOURCE_CODE */

에궁.

---------------------------------------------------------------------------
http://jinhyung.org -- 방문해 보세요!! Jenix 의 블로그입니다! :D

Bini의 이미지

글쓴이: Bini / 작성시간: 수, 2004/12/29 - 11:55오전

저도 같은 답이 나오는데
간단히 Clean 으로 짜봤읍니다.

module ex

import StdEnv

fun :: !Int !Int -> Int
fun l r = fun` l r 0
where
	fun` :: !Int !Int !Int -> Int
	fun` l r c
		| l > r           = c
		| otherwise       = if (re > c) (fun` (l+1) r re) (fun` (l+1) r c)
	where
		re = fun`` l 1
	
	fun`` :: !Int !Int -> Int
	fun`` v c
		| v == 1	     = c
		| isEven v	   = fun`` (v / 2) (c + 1)
		| otherwise     = fun`` (v * 3 + 1) (c + 1)

Start = (fun 1 10, fun 100 200, fun 1 113382) // result (20, 125, 354)

그런데 이게 무슨문제인가요?
1 부터 113382 까지는 잘나가다가 (354 여러번 연속으로 나오네요)113383에서 갑자기 시간이...

halloo의 이미지

글쓴이: halloo / 작성시간: 수, 2004/12/29 - 12:04오후

1번 문제만 풀고 좀 많이 쉬고 있습니다만,
그때 어렴풋한 기억을 되살려 보면 출력같은 형식이 조금만 틀려도 잘못된 것으로 인식해서 삽질한 적이 있습니다.

해당 사이트 포럼에서 비슷한 사람의 글을 열심히 찾아서 읽고 해결했던 문제가 나네요~ (예전이라서 어떤 문제였는지는 기억이... 대충 STDIN으로 받고 STDOUT으로 결과는 내는 과정을 수정했던것 같습니다...)

일단 제출되면, 수행 속도를 올려서 순위권!에 넣어보고자 하는데, 다른 사람들은 뭘로 짰는지 도저히 상상할 수 없는 시간으로 수행했더군요.

sodomau의 이미지

글쓴이: sodomau / 작성시간: 수, 2004/12/29 - 12:13오후

between i and j 에 있는 값이므로
i < j 라는 가정이 없습니다;
j > i 일 경우도 처리해 주시면 될껍니다;

http://home.postech.ac.kr/~sodomau

doldori의 이미지

글쓴이: doldori / 작성시간: 수, 2004/12/29 - 1:06오후

혹시 void main(void) 때문에 그러는 거 아닐까요? :)
농담이고...
혹시 계산 과정에서 오버플로우가 생기는 거 아닙니까?
LONG_MAX가 21억이면 그럴지도 모른다는 생각이 드는군요.

오호라의 이미지

글쓴이: 오호라 / 작성시간: 수, 2004/12/29 - 1:22오후

오호 방가운 질문이군요.

이게 ACM의 1번문제죠. 일명 [(Collatz)콜라츠의 문제]라고 합니다. 또는, [3n+1]라고 칭하고 하는것 같더군요.

수학적으로 증명이 안된 NP문제중 하나입니다.

실제로 구현하기는 문제가 쉽습니다. 물론. 숫자가 한정되어 있는 가정하에 입니다.

저도 몇번 시도하다 귀찮아서 안하고 있었는데 방갑네요.

잠깐 소스를 보니까.

실제로 ACM순위권안에 들려면 실행시간이 문제입니다.

되도록이면 Macro함수를 이용해서 함수호출을 줄이고, Loop문 안쪽도 최소하고,

[num = num / 2] 같은 경우는 우선
[num /= 2] 라고 줄여야겠고, 좀더.
[num >>= 1] 이라고 줄여야겠죠. 물론 unsigned 입니다.

컴파일라거 최적화라 해준다고 하지만. 이런 식으로 최대한 소스를 줄여야 합니다. 컴퓨터구조, 에셈블리어책을 참고하세요.

컴파일시 옵션으로 최적화도 해주어야하고, 쉬운문제이면서도 성능의 차이가 나는 문제입니다. 쉽게 생각하면 안돼죠.^^

두가지 팁을 드리자면 값이 2의 N승이 되면 빠른 속도로 값이 줄어 들죠. ^^
다른 한가지는 짝수와 홀수입니다. ^^

그럼...^^

P.S 이 문제는 결과가 중요한게 아닙니다. 방법이 매우 중요합니다.

Hello World.

jenix의 이미지

글쓴이: jenix / 작성시간: 수, 2004/12/29 - 2:41오후

sodomau wrote:
between i and j 에 있는 값이므로
i < j 라는 가정이 없습니다;
j > i 일 경우도 처리해 주시면 될껍니다;

아 Sovled 떳습니다.

그렇군요 OTL

그런 곳에 문제점이..

아.. 에고 3시간이나 삽질을.. ㅠ_ㅠ

답변 감사..! 그런 점도 다 신경을 써야하는군요

꼼꼼히 봐야겠어요 ㅠ0ㅠ

---------------------------------------------------------------------------
http://jinhyung.org -- 방문해 보세요!! Jenix 의 블로그입니다! :D

Bini의 이미지

글쓴이: Bini / 작성시간: 목, 2004/12/30 - 10:20오전

1-113383에서 왜 갑자기 결과가 안나오나 싶었더니 내부계산이
정수범위를 쉽게 넘어가 버리는군요 ^^;
다른 정수타입을 사용해서 계산하니 354
1~10000000 까지는 한참있다 686
다른언어로 똑같이 코딩해서 간단한 벤치마킹용코드로 사용해도
될것같군요...
저도 그책 한번사서 봐야겠읍니다. 재미있을것 같은데...

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 목, 2004/12/30 - 10:30오전

컴파일러 최적화 보다는 dynamic programming 을 쓰는게 속도가 더 빠를거 같네요

ironiris의 이미지

글쓴이: ironiris / 작성시간: 목, 2004/12/30 - 10:37오전

최적화하는 팁으로 

     22                 if(tmp%2 == 0) 
     23                     tmp = tmp / 2; 
     24                 else if(tmp%2 == 1) 
     25                     tmp = 3*tmp + 1; 
     26                 count++;
에서 나머지연산 대신에 1과 and 연산을 해서 그 값이 1이면 홀수고 0이면 짝수로 계산하는 것이 훨씬 빠르고 위에 언급해주신 것처럼 tmp=tmp/2 대신에 쉬프트연산을 해주는 것이 더 빠를것 같습니다.
Bini의 이미지

글쓴이: Bini / 작성시간: 목, 2004/12/30 - 11:41오전

ironiris wrote:
최적화하는 팁으로 
     22                 if(tmp%2 == 0) 
     23                     tmp = tmp / 2; 
     24                 else if(tmp%2 == 1) 
     25                     tmp = 3*tmp + 1; 
     26                 count++;
에서 나머지연산 대신에 1과 and 연산을 해서 그 값이 1이면 홀수고 0이면 짝수로 계산하는 것이 훨씬 빠르고 위에 언급해주신 것처럼 tmp=tmp/2 대신에 쉬프트연산을 해주는 것이 더 빠를것 같습니다.

님의 말씀대로 하로 C뿐만 아니라 Clean에서도 상당히 효과가 있군요...

fun2 :: !Int !Int -> Int 
fun2 l r = fun` l r 0
where 
	fun` :: !Int !Int !Int -> Int 
	fun` l r c 
		| l > r		= c 
		| otherwise	= if (re > c) (fun` (l+1) r re) (fun` (l+1) r c) 
	where 
		re = fun`` l 1
    
	fun`` :: !Int !Int -> Int 
	fun`` v c 
		| v == 1	= c 
		| iseven	= fun`` (v >> 1) (c + 1) 
		| otherwise	= fun`` (v * 3 + 1) (c + 1)
	where
		iseven = v bitand 1 == 0

예전함수와 새로짠함수를
1~113382까지 500회 수행해서 타임프로파일러로 비교하니
예전코드 => 54.361792
새로짠코드 => 31.72282
거의 20초가량 빠르네요...
다른팁은 없나요? ^^;

sodomau의 이미지

글쓴이: sodomau / 작성시간: 목, 2004/12/30 - 12:56오후

꿀랄랄f wrote:
컴파일러 최적화 보다는 dynamic programming 을 쓰는게 속도가 더 빠를거 같네요

그러게요. 자잘한 최적화가 그리 문제 푸는데 큰 영향을 미치지 못하는데..
ACM 문제에서 time limit exceed 등 떴을 때 일반적으로 생각해야 될 문제가 대부분 알고리즘 수준의 최적화라고 봐야 되는데 쓰레드 방향은 약간 안 맞네요. ㅎㅎ

http://home.postech.ac.kr/~sodomau

오호라의 이미지

글쓴이: 오호라 / 작성시간: 목, 2004/12/30 - 7:08오후

Bini wrote:
1-113383에서 왜 갑자기 결과가 안나오나 싶었더니 내부계산이
정수범위를 쉽게 넘어가 버리는군요 ^^;
다른 정수타입을 사용해서 계산하니 354
1~10000000 까지는 한참있다 686
다른언어로 똑같이 코딩해서 간단한 벤치마킹용코드로 사용해도
될것같군요...
저도 그책 한번사서 봐야겠읍니다. 재미있을것 같은데...

제가 위에서 설명했듯이 [NP문제]입니다. 벤치마킹해도 소용없습니다. ㅡㅡ;;

자릿수가 무한대라면 모를까? 또는 양자컴퓨터라던지??
슈퍼컴으로 돌려도 안됩니다. ㅡㅡ;

아마 문제자체에서도 주워지는 수는 제한되어 있습니다.

그림을 보면 알수 있겠지만. 전체적으로 보면 수는 중가와 감소를 반복하면서 점차 줄어듭니다.
2의 N승이 될 경우는 빠른 속도로 감소하고, 증가는 없습니다.
그러나, 수가 2의 N이 될 경우는 그리 크지 않은 수입니다. 기껏 256 ~ 64정도. 이보다 클 경우는 적고, 작을 경우는 많습니다.

또한, 수가 커지면 커질수로 평균적으로 1일 될때까지의 횃수는 늘어납니다. 물론 전체적인 평균입니다. ^^;

지역(local)적으로 보면 수가 점차 증가를 보이는 것같지만.
전체(grobal)적으로는 감소를 합니다.

컴퓨터로 돌려보면 웬만하면 답이 나옵니다. 거의 모든 수가 1이 되지요. 2의 128까지 돌려 봤습니다. 몇일걸렸습니다. ㅡㅡ;;

역시나 콜라츠의 문제는...
메르센느랑 똑같습니다. ㅡㅡ;;

이 문제자체가 C언어 몇달만 배워도 풀수 있는 문제이지만...
담고 있는 내용은 매우 까다로운 성격인지라...
알로리즘, 자료구조의 성격이 매우 강하죠...
그리고, 이 문제는 여기 분들하고 취지가 맞지 않는것 같네요.
답글 올라온 글들을 봐도 글쓰신 분이 원하는 답을 해드릴만한 분은 없는 것같습니다. ^^;

책하나 추천해드리겠습니다.

[컴퓨터 알고리듬 사전, 조동욱님 우효섭님, 대신기술사, 1990]

정말정말 구하기 힘드실겁니다. 서점에서 구한긴 NP문제 깨기보다 힘들고, 유명도서관이나 대학도서관쯤이면 찾으실 겁니다. 그런 면에서 전 NP문제를 깬네요. ㅡㅡ; 한번 읽고 이리저리 찾다 교보문고 강남점에서 찾았습니다.
아!~ 그리고, pascal로 되어 있습니다. 설명은 거의 없는거나 마찬가지고 소스만 있습니다. 소스는 대부분 간결해서 보시면 금방 아실겁니다.

[해밍의 문제]도 있습니다.

댓글 첨부 파일: 
첨부파일 크기
Image icon 0바이트

Hello World.

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.