문제를 푸시면 기념품을 드립니다. ^0^/
글쓴이: 김지완 / 작성시간: 월, 2007/09/10 - 2:19오후
문제를 푸시면 사이냅소프트에서 기념품을 드립니다.
...원하신다면 입사특전도 드립니다.
피보나치 수에 대한 문제입니다. 피보나치 수는 아래와 같이 정의됩니다. f(1) = 1 f(2) = 2 f(3) = f(1) + f(2) = 1 + 2 = 3 f(4) = f(2) + f(3) = 2 + 3 = 5 f(5) = f(3) + f(4) = 3 + 5 = 8 ... f(n) = f(n-2) + f(n-1), n>=3 a와 b라는 두수가 주어져 있을때 두수사이에는 몇개의 피보나치 수가 있을까요? 예를 들어 10과 100 사이에는 총 5개(13, 21, 34, 55, 89)의 피보나치 수가 있습니다. 12345678999과 99987654321 사이에도 몇개의 피보나치 수가 있습니다. 이 구간내의 모든 피보나치수를 더한 값이 기념품을 받을 수 있는 열쇠입니다.
정답을 아시면 아래 URL로 접속하세요.
http://{정답}.synap.co.kr
PS. 댓글에 정답을 남기지는 말아주세요. 다른 사이트에 올리는 것은 환영합니다.
Forums:
커피 3잔은 금방 나오던데...
시지프스님말씀대로 왠간해도 3초정도면 나오는거같습니다. 최적화같은건 안했구요.
랭귀지 or 개발환경 차이인듯? 전 C++입니다.
참고로 2번째 문제도 3초정도... ( std::next_permutation 쓰면 매우 편해요~ )
근데 상품은 도대체 뭘 주나요?
( GIVE + ME = THE + MONEY )... 농담입니다.
펄로 커피 문제 다시
펄로 커피 문제 다시 풀어본 결과,
정말 좀 더 생각하고, 다시 해보니 30초 정도에 풀리네요.
이 문제로 프로그래밍 언어의 속도비교 하는 것도 재미있겠네요.
(개발환경과 알고리즘에 따라 속도가 다르므로 정확한 비교는 어렵겠지만)
펄은 30초 정도,
C++ 은 3초 정도, ( endorand 님 )
파이썬은 1분이내, ( lifthrasiir 님 )
자바, 루비, lisp, 또는 그 밖의 언어로 해보신 분 계신가요?
--------------------Signature--------------------
"What can change the nature of a man?"
C로 5.대 후반 나옵니다.
C로 5.대 후반 나옵니다.
뭐다시 성능이 좀 되는 곳에서 돌려 봐야 겠지만.. ㅠ_ㅠ
VIA C3 느헤미아 1G에서 돌렸을때, 5.804초 나오는 군요...
더럽게 느린 느헤미아 나름 장하다...
(나중에 집에서 가서 2.7G짜리 브리즈번 돌리면 얼마나 나올까요.. -_-?)
C로 0.8초 입니다.
집에서 긁어 봤더니... 상콤하게 0.8초나오는 군요..
역시 AMD 64 x2 브리즈번 3600+은 강력하다.!!!
해킨토시에서 XCode로 컴파일 했습니다. VC하면 좀더 나올듯 하네요
쩝... 아래 JAVA로 400대 찍은신건 혹시 콘로파워의 똥파워?
C로 0.8초 입니다.
집에서 긁어 봤더니... 상콤하게 0.8초나오는 군요..
역시 AMD 64 x2 브리즈번 3600+은 강력하다.!!!
해킨토시에서 XCode로 컴파일 했습니다. VC하면 좀더 나올듯 하네요
쩝... 아래 JAVA로 400대 찍은신건 혹시 콘로파워의 똥파워?
컴 사양도 관련이
컴 사양도 관련이 있겠지만, 일단 알고리즘이 젤 중요할듯하빈다.
전 파이썬으로 6분 나와서 -_-;;
----
자신을 이길 수 있는자는
무슨짓이든 할수있다..
즉..무서운 넘이란 말이지 ^-_-^
나? 아직 멀었지 ㅠㅠ
----
자신을 이길 수 있는자는
무슨짓이든 할수있다..
즉..무서운 넘이란 말이지 ^-_-^
나? 아직 멀었지 ㅠㅠ
FP(프리파스칼)로
FP(프리파스칼)로 끝까지 모두 확인하는 방식으로 약 5초정도 걸린듯합니다.(콘로 E6600, 우분투)
Coffee 문제 415ms 가
Coffee 문제 415ms 가 나오는군요.
말해질 수 있는 것은 분명하게 말해질 수 있다;
말할 수 없는 것에 대해서는 침묵해야한다.
논리철학논고 - 루드비히 비트겐슈타인
--
말할 수 있는 것은 분명하게 말해질 수 있다;
말해질 수 없는 것에 대해서는 침묵해야한다.
논리철학논고 - 루드비히 비트겐슈타인
상품은 반드시 드립니다. ^^
특별한 사항이 아니면 기간안에 문제를 푸시고 정답을 맞추신 모든 분께는
반드시 상품을 드립니다.
경품 이벤트 기간은 2007년 9월 14일 까지 등록해주신 분에 한해서 입니다.
현재 마지막 문제 페이지에 가보시면 문제를 등록하신 분들 리스트가 있고,
일일이 답안을 확인해서 답변 메일을 준비 하고 있습니다.
기념품을 보내드리지 않는 일은 없습니다. ^^
그리고 처음 게시글에도 말씀 드린 것 처럼 댓글로 답안을 적는
일은 자제해 주셨으면 합니다. 되도록이면 지금 있는 소스 들도 삭제를
해주시면 정말 감사하겠습니다.
Ps. 보내 주신 분들의 동의를 얻어 보내주신 소스코드의 공개도 고려하고 있습니다.
ㅎ
피보나치 문제..처음에 재귀로 구현했다가 스택이 넘치더군요..( '')
결국 '남는게 메모리다'정신으로 전부 배열에 때려넣어서 끝. ;;
send more money 문제는 '노가다를 내가하냐? 시퓨가 하지. 요즘 시퓨좋아~' 정신으로 루프 10단계 -_-;;
요즘 컴은 성능이 좋아서 금방풀리더군요. ㅋ
커피문제..아무 생각없이 순차로 돌리다가 단어 하나당 10초..계산해보면 분당 6개, 시간당 360개..단어가 9800개 정도니까..27시간 -_-;
하루정도 최적화를 고민하다 안되겠다 싶어서 바닥부터 다시 생각해보고..구하는 방식을 뒤집으니 금방 되더군요..
(빨라졌다고 해도 펜4 2.8Ghz 시퓨로 답만 찾으면 30초, 전체 다 훓으면 6분정도 걸리는군요..역시 '노가다는 시퓨가') ㅋ
마지막 문제도 다시한번 생각을 엎어야 되겠더군요. 천천히 할랍니다..( '')
----
자신을 이길 수 있는자는
무슨짓이든 할수있다..
즉..무서운 넘이란 말이지 ^-_-^
나? 아직 멀었지 ㅠㅠ
----
자신을 이길 수 있는자는
무슨짓이든 할수있다..
즉..무서운 넘이란 말이지 ^-_-^
나? 아직 멀었지 ㅠㅠ
피보나치 수열의
피보나치 수열의 정의에 따라 위 문제는 이전의 피보나치 수열 값 2개만을 저장하고 있음 됩니다.
#include <stdio.h> const long long MIN=12345678999; const long long MAX=99987654321; int main( int argc, char** argv ){ long long f[3] = { 1, 2, 0 }; long long sum = 0; int idx = 1; int p, pp; while( f[idx] <= MIN ){ p = idx; pp = (idx+2)%3; idx = (idx+1)%3; f[idx] = f[p] + f[pp]; } while( f[idx] < MAX ){ sum += f[idx]; p = idx; pp = (idx+2)%3; idx = (idx+1)%3; f[idx] = f[p] + f[pp]; } fprintf( stderr, "%lld\n", sum ); return 0; }위 코드 중 좀 비효율 적인 부분이 보이는데...
p = idx; pp = (idx+2)%3; idx = (idx+1)%3; f[idx] = f[p] + f[pp];위 코드는 아래와 같이 최적화 할 수 있을 것 같습니다.
long long tmp = f[idx]; idx = (idx+1)%3; f[idx] = f[0] + f[1] + f[2] - tmp;어찌봄 쓸데 없이 값을 백업하고 또 의미 없는 더하기 빼기가 추가된 것 같지만, 인덱스를 계산하기 위한 + 와 % 를 한번 씩 줄일 수 있으니 아래 코드가 조금 더 빠를 것 같습니다. (대체로 %보다는 빼기가 빠르므로;; )
--
오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...
http://mytears.org ~(~_~)~
나 한줄기 바람처럼..
오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...
http://mytears.org ~(~_~)~
나 한줄기 바람처럼..
피보나치 수열 문제를 생각하다가
피보나치 수열 문제를 생각하다가 알게 되었는데요.
연속된 피보나치 수열 숫자 두개를 알고 있으면 큰 피보나치 수열에 매우 빨리 접근할 수 있다는 것을 알게 되었습니다. 그래서 손으로 계산해서 풀었는데...
A, B가 연속된 피보나치 수열 숫자이면
A * A + B * B, B * A + (A+B) * B 는 연속된 피보나치 수열 숫자입니다.
A', B', C'가 다른 연속된 피보나치 수열 숫자이면
A'*A + B'*B, B'*A + C'*B 도 연속된 피보나치 수열 숫자입니다.
이 방법을 프로그램으로 만드는 것은 어떨까요?
지금은 세번째 문제에서 헤매고 있습니다.^^
OTZL
이거 coffee 문제 시지프스님이 3초대에 풀었다고 하셔서 범용적으로 작성하던걸 죄다 날린 후에
다시 완전 문제에 최적화 해서 작성한 후 다시 푸니 전 한 5초 걸리는군요 -_-
랭귀지는 java입니다.
근대 endofhope 님이 415ms에 푸셨군요 -_-; 완전 감탄입니다;;
근대 더욱 좌절인건 다음 문제에 가보니 이런말이 있군요 -_-
으흑 ㅜ_ㅜ 이거 갑자기 짜증이 확 밀려 오는대요;
새 생각 :)
새 생각 :)
직원
직원 채용하시나봐요?
ㅎㅎㅎㅎ 왠지 냄새가...
끄응.. 한 번 풀어볼까...?
기념품에 연연하고 싶지 않은데...
왠지 모를 도전의식을 느끼는 것 같습니다.
====
( - -)a 이제는 학생으로 가장한 백수가 아닌 진짜 백수가 되어야겠다.
커피3잔 최적화 시켰습니다.
커피3잔 최적화 시켜서 161밀리초 끊었습니다. ㅎㅎ
범용적인 코드를 포기하고 커피3잔 전용으로 코드를 만들었습니다.
79번까지 찾고 끝내서 입니다.
오호 그런 방법도
오호
그런 방법도 있긴 하군요..
제꺼 그렇게 해봤더니... 무려 67ms 나왔습니다.
빠르네요 효효
빠르네요 효효
coffee X 3 문제가 인기군요.
그것보단, 마지막 문제는 다들 얼마나 걸리셨는지요?
--
Deisys, in the middle of the world, being with you . . . . . .
--
http://www.deisys.net
저는 마지막 문제가
저는 마지막 문제가 약 5분36초(321625밀리초) 걸렸습니다.
커피3잔 최적화 코드작성 이전에 작성했던 범용코드를 적용했습니다.
C로 52초
C로 52초 걸렸습니다.
마지막 문제 52초 걸리더군요.
최적화 없이 나온거니까 빠른 편이죠 ^^
(아 물론 브리즈번에서 했습니다. ^^)
후덜덜.
무지 빠르네요.
마지막 문제의 핵심 포인트가 있나요?
저는 문장에 전체 필요한 숫자가 많으면 속도가 상당히 다운됩니다.
숫자가 5~6개만 있어도 될때랑 숫자10가지가 모두 필요할때의 처리속도 차이가 급격히 늘어납니다. ㅠㅠ
글쎄요 저는
글쎄요 저는 무식하게 대입하는 방식으로 풀어서...
제가 푸는 방법도 한개 늘어 날때마다 엄청나게 차이 납니다. 팩토리얼로 늘어 나죠 ㅠ_ㅠ
마지막 문제의 핵심
마지막 문제의 핵심 포인트는 숫자를 조합할때,
필요없는 경우를 가능한 모두 제외시켜야 하는 것 같습니다.
글자머리에 0이 나오는 경우랑 중복수를 체크하는 부분인데,
중복숫자 난관이더군요..ㅠㅠ 그것만 해결되면 어떻게 될 꺼 같습니다.
===================================================
중요한건 얼마나 아느냐가 아니라 그것에 대한 열정이다.
===================================================
중요한건 얼마나 아느냐가 아니라 그것에 대한 열정이다.
흑흑 ㅠㅠ
문자의 처음에 0이 오지 않도록 하는 코드를 추가했음에도 약 4분7초 걸렸습니다. OTL
1분은 단축시켰지만 중추 알고리즘 부분이 바뀌지 않는한 더 못줄일것 같습니다 ㅠㅠ
c로 16.7초내요..
마지막 문제...
c 로 16.7초 만에 나오내요..
비결은 함수호출 수를 최대한 줄이는게 .....
pentium 4 3G 에서 16.7초
pentium 3 800M 에서 52.7초
대충 cpu 클럭에 따라 비슷한 결과가 나오내요....
멋진남자...
그냥 컴파일하면
그냥 컴파일하면 25~27초 걸리고, -O2로 컴파일하면 12초 걸리네요. -O1이나 -O3이나 -Os로 컴파일해도 역시 12초 걸립니다.(gcc version 4.1.2 (Gentoo 4.1.2))
생각보다 컴파일러 성능 + 컴파일러 옵션 + 컴퓨터 성능에 따른 편차가 크네요.
begin{signature}
THIS IS SPARTA!!!!!n.
end{signature}
athlon64 2800+에서 최적화 옵션 주고 14~15s 정도 걸리는군요.
좀 더 제한 조건을 걸면 약 600ms 정도 줄어들더군요.
테스트 환경은 Windows XP입니다.
정확히 하면 Visual C++ Release Mode로 14.2s 정도 나오고 gcc 3.4.3 (MinGW) -O2 옵션에서 15.3s 나옵니다. Visual C++ Debug Mode로는 33.8s 정도 나오고 gcc 3.4.3 (MinGW) 옵션없이 하면 27.5s 정도 나오더군요.
저같은 경우에는 재귀함수로 숫자를 조합했는데 인자 전달을 생략하고 전역 변수만 썼다면 결과가 더 빨랐을지도 모르겠습니다.
P.S 시간 단위를 잘못 적어서 수정했습니다. -_-;
http://www.grandgift.co.kr/pr
http://www.grandgift.co.kr/product/product_view.php?code=1179091
선물로 이걸 주네요. 습도까지 되면 좋으련만.
큭 전자제품..
혹시 해외까지 배송을 해 주신다고 하더라도
기념품을 쓰기 위해 변압기를 장만해야 하는건 배보다 배꼽이 더 큰 듯..
이라는 핑계로 커피세잔은 포기했습니다;ㅂ;
Summa Cum Laude
저도 느리던데;
마지막 문제 인증샷 입니다.
C#으로 풀었고 ..
굉장히 느립니다 -_-;;
아주 무식-_-;;하게 모든 조합을 미리 구해서 메모리에 올려놓고
단어 대입해 가면서 풀었죠 ㅠㅠ
[url=http://kldp.org/files/synap_final.JPG]
뷁... 업체에서
뷁...
업체에서 기념품 주는 것 취소할지도 몰라요 16일부터 올려 주시면 않될까요 ?
마지막 문제는
마지막 문제는 소스코드와 실행결과를 함께 메일로 보내고, 만든 프로그램에 대해 여러가지 사항을 함께 적어서 보내야 합니다.
결과만 저렇게 올려놓는 것은 크게 상관없을 듯 합니다... 만 그래도 지우는게 좋을 듯 합니다.
마지막 문제는 메일로 소스를 보내야 합니다.
마지막 문제는 메일로 소스를 보내야 합니다.
또한 1,2 번 문제를 푸셨다면 당연히 풀 수 있는 문제입니다.
(코드 리팩토링및 여러가지 사항들을 요구하지요 ㅎㅎ)
그래서 스크린 샷만 올렸고요 ..
혹시 문제 된다면 바로 자삭 하겠습니다^^
이제서야 4문제 다풀었네요..
저는 이제야 4문제 다풀었네요.
이런식으로 문제를 접한건 처음이라, 즐거운 시간 보냈습니다.
이벤트 기간이 끝나면 다른분들이 만드신 코드를 보고싶네요. 히히..
php로 짜고 있는데 3번째 문제는 자꾸 타임아웃 뜨네요;;
소스라고 해봐도 100여줄 남짓한데;;
30초 타임아웃에 자꾸 걸리는게 ㅠㅠ
슬프네요;
한 20분 돌리면 나올꺼 같은데 ㅎㅎㅎ
흐흐, 이제 자야겠습니다~_~
두 피보나치 수
두 피보나치 수 사이에 있는 피보나치 수들의 합을 구하는 함수를 임의의 정확도를 가지도록 만들어 봤습니다.
Perl과 C 버젼이 125배 차이나네요.
0 과 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
사이고요, 갯수는 4156이고 합은 25830660833076881694052175146759154065834735494747333875345640725766822813836623036419186716386379805157584728069080288299392490715350262404053849002514900570687734130855627552542190382929822536390897444706769204265422801929941035067327583611431895343933035966921738971133949525176217936556681068491643714352414470377638218170085943212344945294205152029083864917257883372134758697515508310348217271081402313329264258103937433889707016264979286536704806462508909099050313350312371196561223031296221973485552522646598556344035042360379341723829641126670996691140863061711591646983294339648520241240531725175061265558678125055870328636890231293924170672746802866640422976178621913173985695411653473005560576261516008651392109002363257243294610224669195130858531597440761714087775991384023604078046484257209626486228132961003652819589294675462646263777654013730047874235636 였습니다.
와... 대단하시네요..
어떻게 푸셨길래... 저렇게 빨리 결과가 나오죠?
저는 재귀함수 이용해서 문제 푸는데만 1초에서 2초정도 나오던데..
어떤 식으로 짜셨는지 궁금해요~
재귀함수를 안쓰고
재귀함수를 안쓰고 그냥 while loop을 써서 iterative하게 풀면 아마 금방 답이 나올겁니다. 파이썬의 경우에도 1초 훨씬 안으로 답이 나오더군요..
간단하게 interactive shell에서 실행하면,
>>>
>>> def next_fibo():
... a = 1; b = 0
... while True:
... tmp = a; a = a+b; b = tmp
... yield a
...
>>> g = next_fibo()
>>> print g.next(), g.next(), g.next(), g.next(), g.next() + g.next() == g.next()
1 2 3 5 True
>>> while True:
... f = g.next()
... if f>12345678999: break
...
>>> f
12586269025L
>>> sum = f
>>> while True:
... f = g.next()
... if f>99987654321: break
... sum += f
...
>>> sum
205486422643L
..
아.. 이런식으로 하면 1초 안으로 나오는 군요..
방금 돌려보니 저도 1초 안으로 나오네요~
학교에서 재귀함수로 피보나치수열을 나타내는 법을 배워서 recursive하게만 생각했네요.
소스 감사합니다.
sum_{i=1}^{n} fibonacci(i) =
sum_{i=1}^{n} fibonacci(i) = fibonacci(n+2) - 1
이므로
sum_{i=n}^{m} fibonacci(i) = fibonacci(m+2) - fibonacci(n+1)
= 2*fibonacci(m) + fibonacci(m-1) - fibonacci(n+1)
이 됩니다.
보통은 fibonacci(1)=fibonacci(2)=1로 두는데, 여기서는 f(1)=1, f(2)=2라고 했으므로
sum_{i=1}^{n} f(i) = f(n+2) - 2 이 되지만 sum_{i=n}^{m} f(i) = 2*f(m) + f(m-1) - f(n+1) 인 것은 마찬가지입니다.
이렇게 하면 약간 더 빠르게 만들 수 있겠군요.^^;
begin{signature}
THIS IS SPARTA!!!!!n.
end{signature}
알고리즘 성능향샹을
알고리즘 성능향샹을 위한 좋은 예입니다.
위 식에서 m, n을 바꾸는 것이 더 좋을 것 같습니다.
레퍼런스 삼아 fib_sum()함수를 구현하였습니다. 참고하시길.
수정 1: fib2() 추가 및 방정식 설명 오류 고침
/* * Get n'th fibonacci number * fib(0) = 0 (n = 0) * fib(1) = 1 (n = 1) * fib(n) = fib(n-1) + fib(n−2) (n > 1) * * @param n'th position of fibonacci numbers * @return if success, returns n'th fibonacci number * else returns ~0ULL * @license Public Domain * @author MC (modestcode at kldp dot net) */ unsigned long long fib(unsigned long n) { if (n == 1UL || n == 2UL) return 1ULL; else if (n == 0UL) return 0ULL; unsigned long long n1 = 1ULL, n2 = 1ULL, tmp; for (; n > 2UL; n--) { tmp = n2; n2 += n1; if (n2 <= n1) /* overflow */ return ~0ULL; n1 = tmp; } return n2; } /* * Get n'th and n-1'th fibonacci number * * @param n'th fibonacci number of results: if overflow, ~0ULL * @param n-1'th fibonacci number of results: if nonexistent, ~0ULL * @param n'th position of fibonacci numbers * @license Public Domain * @author MC (modestcode at kldp dot net) */ void fib2(unsigned long long *r2, unsigned long long *r1, unsigned long n) { if (n == 0UL) { *r2 = 0ULL; *r1 = ~0ULL; /* nonexistent */ return; } else if (n == 1UL) { *r2 = 1ULL; *r1 = 0ULL; return; } else if (n == 2UL) { *r2 = 1ULL; *r1 = 1ULL; return; } unsigned long long n1 = 1ULL, n2 = 1ULL, tmp; for (; n > 2UL; n--) { tmp = n2; n2 += n1; if (n2 <= n1) { /* overflow */ *r2 = ~0ULL; *r1 = n1; return; } n1 = tmp; } *r2 = n2; *r1 = n1; } /* * Get the sum of fibonacci numbers between two fibonacii numbers(inclusive) * from following equations: * fib(0) + fib(1) + fib(2) + ... + fib(n) = fib(n+2) - 1 [1] * fib(m) + ... + fib(n) = fib(n+2) - 1 - (fib(m+1) - 1) * = fib(n+2) - fib(m+1) * = fib(n) + fib(n+1) - fib(m+1) * = fib(n) + fib(n) + fib(n-1) - fib(m+1) * = 2fib(n) + fib(n-1) - fib(m+1) * [1] <a href="http://en.wikipedia.org/wiki/Fibonacci_number " rel="nofollow">http://en.wikipedia.org/wiki/Fibonacci_number </a> * * @param m'th position of fibonaccci numbers * @param n'th position of fibonacci numbers * @return if success, returns the sum of fibonacci numbers * else returns ~0ULL * @license Public Domain * @author MC (modestcode at kldp dot net) */ unsigned long long fib_sum(unsigned long m, unsigned long n) { unsigned long long r2, r1, result, tmp; if (n == 0UL) return 0ULL; fib2(&r2, &r1, n); if (r2 == ~0ULL) /* overflow */ return r2; tmp = r2 * 2; if (tmp <= r2) /* overflow */ return ~0ULL; return tmp + (r1 - fib(m+1)); }..
저는 재귀로 이렇게 돌렸어요.
if( n == 1 || n == 2 || n == 3)
return n;
else
return fibo(n-3) + 2 * fibo(n-2);
이미 Perl, Python
이미 Perl, Python 버젼이 (수정할 여지는 있지만)나왔고 C 버젼을 올립니다.
제 컴에서는 unsigned long long 최대값이 18446744073709551615 이므로, 93번째 피보나치 수인 12200160415121876738까지 출력할 수 있습니다.
/* * Get n'th fibonacii number * * @param n'th * @return if success, returns n'th fibonacci number * else returns ~0ULL * @license Public Domain * @author MC (modestcode at kldp dot net) */ unsigned long long fib(unsigned long long n) { if (n == 1ULL || n == 2ULL) return 1ULL; else if (n == 0ULL) return 0ULL; unsigned long long n1 = 1ULL, n2 = 1ULL, tmp; for (; n > 2ULL; n--) { tmp = n2; n2 += n1; if (n2 <= n1) { /* overflow */ return ~0ULL; } n1 = tmp; } return n2; }GMP 라이브러리라면,
void fib(mpz_t result, unsigned long n) { mpz_fib_ui(result, n); }로 간단하고 마음껏? 출력할 수 있습니다.
890번째라는 군요.
890번째라는 군요.
이거 회사
이거 회사 광고인가연? 아님 사원모집 공고인가연?
회사 광고에 사원모집 공고겠지요
회사 광고에 사원모집 공고겠지요.
하지만 그렇게 부정적으로 보이지는 않네요.
즐거운 오락거리에 공부거리도 되었고 기념품을 받을 수도 있으며
회사측에서는 어느 정도 어필을 할 수 있는 기회가 되었구요.
나름대로 윈윈 게임이라고도 생각되네요.
의미없는 트롤 장단맞추기나 뱀꼬리 잡는 플레이밍보단 훨씬 바람직하지 않은가요^_^
하지만 문제가 세 개 있다는건 미리 좀 알려주셨다면..
첫번째 문제 풀고 아싸 기념품 하나 얻었다! 라고 했다가 다음 문제도 있다고 하니 당황하고
혹시나 해서 쓰레드를 쭉 읽어보니 이거 풀어도 문제가 한개 더 있다니..
Summa Cum Laude
전혀 관련 없는 것을
전혀 관련 없는 것을 말씀 드려서 죄송한데... C에 long long형도 잇었나요? 언제부터 거게 있었는지 모르겠군요. 몰랐던 건가요 저만. 제가 자료형에 대해서 공부 할 때는 short(short int), long(long int), char, struct, float, double, 포인터 타입들, 이 정도였는데... long long가 있었다니.. unsigned 처리는 익숙한데 long long는 처음 보는군요. 혹시 long(32Bit)의 2 배가 되는 건가요?
----
Lee Yeosong(이여송 사도요한)
E-Mail: yeosong@gmail.com
HomePage: http://lys.lecl.net:88/
Wiki(Read-Only): http://lys.lecl.net:88/wiki/
Blog: http://lys.lecl.net:88/blog
MSN: ysnglee2000@hotmail.com
----
절이 싫으면 중이 떠나는 것이 아니라, 절이 싫으면 중이 절을 부숴야 한다.
때때
사람천사
C99 표준에 추가되었습니다.
C99 표준에 따라 최소 64비트 정수형을 표현하기 위해 쓰는 겁니다.
오랜만에 로그인
오랜만에 로그인 했네요..
문제 심심해서 풀어봤는데
1, 2 번은 그다지 시간이 많이 안걸렸는데 3번은 버그가 자꾸 생겨서 결국 푸는데 2시간 정도 걸렸네요;;
35초 쯤 걸린다길래, 그 시간을 깨볼려고 했습니다.
처음에 짠건 답나오기까지 대충 일분 오초 정도 걸렸는데
최적화를 하고나니 1000 개 다구하는데 3초 정도 걸리더군요..
컴터는 코2듀 1.86GHz 이구요..
아래는 소스구요..
int count = 0;
int bitarr[256];
int usedNumber[10];
int preCalculatedCoffee = 0;
int CoffeeNumbers[7];
bool IsExistAnswerInnerLoop( const char *str, int depth )
{
if( depth == 7 ) {
// 다돌았다!!
int numStr = bitarr[str[0]]*1000000 + bitarr[str[1]]*100000 + bitarr[str[2]]*10000 + bitarr[str[3]]*1000 + bitarr[str[4]]*100 + bitarr[str[5]]*10 + bitarr[str[6]];
//if( preCalculatedCoffee == numStr ) {
count++;
if( count == 78 || count == 79 )
printf("%4d : %s : 3*%d = %d\n", count, str, preCalculatedCoffee/3, numStr );
return true;
//} else {
// return false;
//}
} else { // 더돌아야 한다.
if( bitarr[str[depth]] == -1 ) { // 값이 정해지지 않았으면 값을 정해준다.
if( usedNumber[CoffeeNumbers[depth]] == 1 ) // 일치해야 할 숫자가 이미 사용중이라면 그 숫자를 현재 위치에서 사용할수 없다.
{ // 고로.. 실패다..
return false;
}
usedNumber[CoffeeNumbers[depth]] = 1;
bitarr[str[depth]] = CoffeeNumbers[depth];
bool ret = IsExistAnswerInnerLoop( str, depth+1 );
usedNumber[CoffeeNumbers[depth]] = 0;
bitarr[str[depth]] = -1;
return ret;
} else { // 값이 정해졌다면.. 값이 맞는 값인지 본다.
if( bitarr[str[depth]] != CoffeeNumbers[depth] ) // 값이 안맞는다. 틀린 답이다.
{
return false;
} else { // 값이 맞으면 다음 문자도 값이 맞는지 검사한다.
return IsExistAnswerInnerLoop( str, depth+1 );
}
}
}
}
bool IsExistAnswer( const char *str )
{
// COFFEE
// COFE
memset( usedNumber, 0, 10*4 );
for( int i = 0;i < 256; i++ ) {
bitarr[i] = -1;
}
int tempCoffee;
int c,o,f,e;
for( c = 3; c <= 9; c++ ) {
bitarr['c'] = c;
usedNumber
-----------------------------------
속좀 썩이지 마라~~ 잉???
하스켈 처음 배우면서 문제들을 차례대로 풀어봤었는데,
하스켈 처음 배우면서 문제들을 차례대로 풀어봤었는데, 이젠 추억이네요. 어디 이런거 또 없나요?
205486422643
1초도 안 걸림.
결과
후기
12345678999, 99987654321 숫자가 피보나치 숫자인 줄로 착각해서 == 연산자를 쓰니 무한 루프를 돌길래,
알고리즘이 효율적이지 않아서 시간이 오래걸리는가보다 생각했었는데... 한 세월 기다려도 답이 안나오길래
낚였군... 하고 생각하다가..
fib(n)을 출력해보니까... 12345678999, 99987654321 는 피보나치 숫자가 아닌 것을 확인했음.
curr >= 12345678999 and curr <= 99987654321 해주니 1초도 안 걸려서 결과 나옴.
이렇게 쉬운 문제를 어렵게들 푸시는지 역시, 알고리즘 과목이 중요하다는 다시 한번 깨달음.
> 이렇게 쉬운 문제를 어렵게들 푸시는지 역시,
> 이렇게 쉬운 문제를 어렵게들 푸시는지 역시, 알고리즘 과목이 중요하다는 다시 한번 깨달음.
위에 푼 사람들이 첫번째 피보나치 문제 갖고 헤멘줄아나...
지금은 주소가 막힌거 같은데, 지시대로 따라가면 문제가 3~4개 정도 나오고, 나중에 가면 eval 지원 안하는 언어로는 제법 까다로워진다. (eval 있으면 엄청 쉬워짐)
저거 풀고 기념품을 타간 사람이 너무 많아서 싸이냅 담당자가 피눈물을 흘렸었는데
고작 첫문제 풀어놓고 '역시 알고리즘 과목이 중요함 엣헴'하고 잘난척이라니...
그래서 C로 함 해봤습니다. 역시 1초도 안 걸림,
그래서 C로 함 해봤습니다.
역시 1초도 안 걸림, 엣헴~
결과
이 정신병자 같은 반응은 뭐죠?
다른 사람이 헤멘건 피보나치 문제가 아니라
그 문제 풀고 링크 따라가면 나오는 다른 문제 때문에 헤멘거라니까
웬 헛소리?
누가 파보나치 C로 다시 풀어보라고 했나요?
병신같이 쉬운 문제 가지고 엣헴~ 이러고 폼잡지 말고
그 뒤에 문제나 풀어봐라
http://www.jiniya.net/tt/601
뭐 푼다고 해봤자 수많은 정답자 명단에 하나 더 추가하는거밖에 더되겠느냐마는
2단계 문제는 eval 필요없이 방정식으로 풀면
2단계 문제는 eval 필요없이 방정식으로 풀면 됨.
3단계 문제는 사전 파일 없어서 불가.
4단계 문제는 2단계 풀이법과 동일.
ㅉㅉㅉ
그건 손으로 풀때나 쓰는거고...
딱 보아하니 요 핑계 조 핑계 대고 빠질꺼 같은데
그만 때려쳐라... 그리고 어디 가서 피보나치 풀었다고 잘난척 하지말고
그렇지 않음. SYNAP SOFT WANTS
그렇지 않음.
이렇게 경우의 수 줄어가면서 풀면 됨. eval 있고 없음은 중요하지 않음.
피보나치 풀었다고 잘난 척 한 것이 아니라...
위에 보면 피보나치를 어렵게 푸는 사람들이 있어서 그런 것임.
오해 금지. 엣헴~~~ ㅋㅋㅋ
아.. 그리고 26진법 사용. 사실 어려운 문제는
아.. 그리고 26진법 사용. 사실 어려운 문제는 아님.
코드를 작성하는데에 시간이 좀 걸리니까 문제.
아 그러니까 그걸
코드로 구현해 보시라니까요? ㅉㅉㅉ
eval함수가 있고 없고가 왜 차이가 나는지는 4번 가야 정신차리지 ㄲㄲㄲ
만들긴 만들었음. 소스가 길고 개떡같아서 보여드리기가
만들긴 만들었음. 소스가 길고 개떡같아서 보여드리기가 거시기함.
답지를 보니 10진법으로 처리했길래 26진법으로 하지 않고 10진법으로 처리했음.
위에 말했던대로
위의 방법으로 연산기 파서를 만들었음.
racc(루비용 yacc)를 사용하여 코드가 길고 개떡 같음.
eval 사용하지 않았음. eval 사용하여 문자열을 루프 돌릴 생각으로 eval 강조하시나본데...
위의 방법 사용하면 eval 필요하지 않고 속도 빠름. 1문장당 수십초 이내에서 처리됨.
var 테이블을 스택으로 만들었음. 그냥 연산기라고 생각하면 됨.
경우의 수를 어떻게 줄여나가는가, 암호 푸는 것이 문제가 아니라,
이건 완전 계산기 파서 제작 문제임.
왜들 철지난 쓰레드에 담뱃불을 부치시나
왜들 철지난 쓰레드에 담뱃불을 부치시나
죄송. 어찌 하다보니까 그래되었네요. 죄송. 철이
죄송. 어찌 하다보니까 그래되었네요. 죄송.
철이 지나긴 꾀 지났네요. 인터넷으로 검색해보니 효율적인 해법이 제법 등장하는군요.
그중 FSM을 사용한 방법이 인상적이었습니다, 어느 논문에서는 유전자 알고리즘으로 해결하는 방법을 소개하더군요.
> 1초도 안 걸림. 그리고 2007년하고 지금하고
> 1초도 안 걸림.
그리고 2007년하고 지금하고 컴퓨터 성능이 같냐?
제가 사용하는 컴퓨터가 옛날 컴퓨터입니다.^^
제가 사용하는 컴퓨터가 옛날 컴퓨터입니다.^^
아 그러세요^^
그래서 고작 피보나치 아는거 갖고 어깨에 힘 주셨습니까^^
나머지 문제들도 검색해보면 나올텐데 그것도 좀 풀어보시죠^^
<code> 때문인지 페이지가 x축으로 엄청
<code> 때문인지 페이지가 x축으로 엄청 늘어났네요.
로그 되는 계산기 있으면 컴퓨터 프로그램을 만들지
로그 되는 계산기 있으면 컴퓨터 프로그램을 만들지 않더라도 풀 수 있을텐데...;;;
http://snowall.tistory.com/965
다들 복잡하게 푸셨네요...
피할 수 있을때 즐겨라! http://melotopia.net/b
페이지