Programming Challenges (프로그래밍 챌린지, 프챌) 첫번째 문제인 the 3n+1 problem을 같이 고민해 보는 시간을 가져보겠습니다.


the 3n+1은 굉장히 쉬운 문제 같지만 몇몇 해결해야 문제들이 있고, 

또 성능부분에서도 이슈를 가지고 있는 문제입니다. 


문제 요약


1. 어떤 숫자 n(1 ~ 1,000,000)을 준다.

2. n이 짝수면 n = n / 2. n이 홀수면 n = 3*n + 1을 한다. 

3. 이런 식으로 n = 1이 될 때까지 계속한다. 

4. 결국 n=1이 된다는 건 1 ~ 1,000,000 까지는 검증되었다. 

5. 이렇게 어떤 숫자를 주어지고 그게 1이 될때가지 숫자들이 쭉 나열된다. 예를 들어 n=4라면

4, 2, 1 

이렇게 될거고 전체 숫자의 갯수, 3을 cycle-length라고 한다. 


6. 이제 숫자 2개를 주자. 만약 1 10 이렇게 입력하면 1~10까지의 모든 자연수를 대상으로 위 프로세스를 반복해서 1일때 cycle-lenghth, 2일때 cycle-length, 3일때, 4, 5, 6... 10까지의 cycle-length를 계산해서 가장 긴 cycle-length를 화면에 출력하면 된다. 


입력값을 1 10 이라고 하면 결과는 20이다. 


원문 : 

http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110101&format=html


소스코드는 네이버 개발자센터

http://dev.naver.com/projects/panprogchal/

에서 받으실 수 있습니다. 


네이버 개발자센터에서는 서브버전을 이용해 프로젝트를 관리하고 있습니다. 

사용법은 서브버전 홈페이지나 기타 블로그 등을 참조해 주세요.


여기에 바로 소스를 올려놓지 않는 이유는 앞으로 성능개선을 위해 수정할 수도 있고 그 히스토리를 정리하기 위해서입니다. 서브버전은 이렇게 소스코드의 히스토리를 관리하고, 동시에 여러 개발자가 하나의 파일을 수정하기 위해 만들어진 버전관리 툴입니다. 


성능에 관한 이슈는 다음에 시간될 때 더 수정해서 네이버 개발자센터에 올려놓겠습니다. 


이 3n+1 문제를 해결하는 과정을 동영상으로 제작해서 올려놨습니다. 

C언어를 배우시는 분들에게 도움이 되시기라 생각합니다. 


* 동영상 녹화는 캠타시아(camtasia) 8을 이용했습니다. 


프로그래밍 챌린지는 영어로 되어 있고, 프로그래밍에 관한 꽤 수준높은 문제까지 제시하고 있어 스스로 고민하고 공부하는데 도움이 되는 사이트입니다. 시중에 책도 나와 있습니다. 전체 문제를 한글로 설명해주고 해결방법도 보여줍니다. (책에서는 제 문제해결방식과는 또 다른 방식으로 문제를 해결하고 있습니다.)



Programming Challenges - 알고리즘 트레이닝 북
국내도서
저자 : 미구엘 A. 레비야,스티븐S.스키에나 / 서환수역
출판 : 한빛미디어 2004.07.16
상세보기

The C Programming Language : ANSI C Version (Paperback / 2nd Ed.)
외국도서
저자 : Brian W. Kernighan
출판 : Prentice Hall 1994.07.24
상세보기
(팬소년의 C언어 추천도서: 저자들이 C언어 만든 사람임. 하얀책. 영문판으로 추천)



맨날 회사에서 똑같은 것만 해서 식상하고 재미없다는 분들께 추천합니다. 

사람들이 뭐 재밌는 거 없냐 할 때 이 책을 추천해 주고 싶은데, 그랬다간... (한대 맞을지도)


저는 이런 거 하면 넘 재밌어서 한때 대학생들 숙제하는 거도 많이 풀어주고 했었는데, 

4가지없는 분들이 많아서 이제는 좀 접었네요. ㅋ. 



암튼,

프로그래밍 챌린지로 삶의 자그마한 활력이 되시길 바랍니다. ^^;





저작자 표시 비영리 변경 금지
신고


follow us in feedly







댓글을 달아 주세요

  1. yonfhee 2015.06.15 09:09 신고  댓글주소  수정/삭제  댓글쓰기

    짝수일때는 2로 나누는거죠?

  2. 질문 2016.03.28 15:43 신고  댓글주소  수정/삭제  댓글쓰기

    좋은 글 감사합니다.

    다른 문제풀이의 경우
    scanf 했을 때 입력받은 변수 값을 다른 변수에
    복사해서 넣던데 왜 그런지 알 수 있을까요?

    while(scanf("%d %d", &n1, &n2) == 2) {
    buf1 = n1;
    buf2 = n2;

    이런식으로요...

    저같은 경우는 이 문장을 빼면 wrong answer가 나오는데
    팬소년님 풀이는 solved가 나와서 뭐가 다른지 궁금합니다.

    • 팬소년 2016.04.21 12:49 신고  댓글주소  수정/삭제

      음.. 글쎄요.
      단순히 buf1에 같은 값을 복사해서 넣느냐 아니야의 차이가 아닐 거 같아요. 이렇게 한 경우와 안한 경우, 2가지 상황에 대한 전체 소스를 보여주시면 상황을 더 잘 파악할 수 있을 거 같아요.



 

티스토리 툴바