알고리즘 코딩 이벤트 2주차 문제와 1주차 1번 해설

이번 주 문제 나갑니다~

이벤트가 진행될수록 문제가 조금 까다로워지니,
잘 읽고 답해주세요~ ^^

(1주차 1번 문제의 해설은 제일 밑에 첨부하였습니다.
해설에는 저자이신 김용혁 교수님께서 수고해주셨답니다. ^^)

유의사항

1. 풀이과정이나 해답 등은 각자 블로그에 올리신 후, 트랙백 혹은 댓글로 알려주세요.
트랙백 주소 : http://www.insightbook.co.kr/post/3876/trackback
(트랙백은 조금 시간이 걸린 후 등록됩니다.)

2. 블로그 글 제목을 다음처럼 작성해주세요.
‘코딩 인터뷰 완전 분석 210쪽 17.3 변형 문제 풀이’

3. (선택사항 : 글에 『코딩 인터뷰 완전 분석』 표지를 넣어주시면 감사하겠습니다. ㅎㅎ)

 

4. 각 문제별 응모 기한은 다음 문제가 올라오기 전까지이며, 마지막 문제는 1주일간 응모받습니다.

문제

『코딩 인터뷰 완전 분석』210쪽 17.3 변형 문제

자연수 n을 입력받고, n!의 계산 결과 중 마지막에 붙은 연속된 0의 개수와 연속된 0 바로 앞에 나오는 숫자를 구하라.

[실행 예]

input n: 15
output: 3 8

[설명]

15!은 1307674368000이므로, 마지막에 연속된 0은 3개이고, 바로 앞의 숫자는 8이다.

* 조건 *

  1. n의 범위는 1 이상, 10000 이하입니다.
  2. 테스트 입력은 다음과 같습니다.
    20! = 2432902008176640000
    30! = 265252859812191058636308480000000
    40! = 815915283247897734345611269596115894272000000000
    50! = 30414093201713378043612608166064768844377641568960512000000000000
    100! = 93326215443944152681699238856266700490715968264381621468592963
    8952175999932299156089414639761565182862536979208272237582511852
    10916864000000000000000000000000
  3. 프로그래밍 언어에서 제공하는 자릿수 제한 없는 곱셈을 이용하거나, 이런 형태의 곱셈 함수를 직접 구현해도 답을 얻을 수 있지만, 문제의 의도와는 다릅니다.
  4.  정답 검토의 편의를 위해 블로그 포스팅에 2012!와 10000!의 결과를 남겨주세요.
  5. (심화 문제) 연속된 0 앞에 나오는 여러 숫자를 구하는 것도 가능하니, 심심하신 분은 도전해보세요. ^^

 

상품

3주간 진행될 『문제로 풀어보는 알고리즘』『구글러가 전하는 IT 취업 가이드』『코딩 인터뷰 완전 분석』 발간 기념 문제 풀이 이벤트에 참여해 정답을 올리신 분 중,
한 분께는 HP 프로라이언트 마이크로서버를,
다섯 분께는 요즘 가장 핫! 한 아이템 중 하나인 Raspberry Pi를 각 하나씩 선물로 드립니다.
(Raspberry PI는 구입하려는 사람이 많아 공급이 수요를 따라가지 못하고 있다니,
저희가 주문해 입수하는 대로 보내드릴 겁니다.)

 

1주차 1번 문제 해설과 모범 답안 추천

총평 : 확실히 잘못 짠 정답은 하나 밖에 보이지 않을 정도로, 다들 코드를 잘 작성해 주셨습니다.

마감 시한까지 트랙백을 25개나 걸어주셨고, 프로그래밍 언어도 델파이, 루아, 자바, c/c++, 루비, 파이썬, 펄, 커피스크립트, go 등 매우 다양했습니다.

책에서는 해답을 C로 작성했기 때문에 회전 대상과 크기가 같은 임시 배열을 하나 잡아서 배열을 복사하면 됩니다. 대부분 이렇게 잘 풀어주셨습니다.
파이썬은 역시나 강력해서, 배열 중간을 잘라서 그냥 붙이면 됩니다.

문제에서 요구한 것은 아니지만, n과 k에 상관없이 항상 상수 크기의 메모리를 쓰는 방법으로 푸신 분들도 있습니다.
원래 배열이 크지 않거나 메모리가 부족하지 않은 대부분의 경우에는 별 상관없기 때문에, 이런 걸 따지는 것이 좀 옛스럽긴 합니다만…
재미있으니까 한번 생각해보시는 것도 좋습니다.

여기서는 두 가지 방법을 소개합니다.

첫 번째는 배열을 두 번 뒤집는 것입니다.
123456을 오른쪽으로 두 칸 회전시키는 것은 1234와 56을 바꾸는 것과 같습니다.

두 개의 sequence(문자열, 배열 등)를 바꿀 때 많이 쓰는, 각 부분을 뒤집은 다음 전체를 뒤집는 트릭을 여기에도 적용할 수 있습니다.
123456에서 reverse(1~4), reverse(5~6), reverse(전체)를 하는 것입니다.
이렇게 하면 배열이 123456 > 432156 > 432165 > 561234의 순서로 바뀝니다.
아래 두 포스팅을 참고하십시오.

Sunghwan 님

Abraham 님

두 번째 방법은 배열을 휘젓고 다니면서, 원소를 하나씩 적절한 위치로 옮겨주는 방법입니다.
생각하는 프로그래밍』에서는 이 방법을 ‘저글링(juggling)’이라고 부릅니다.
다음 두 분이 이렇게 풀어주셨습니다.
(이 방법으로 짜면 코드가 좀 읽기 어렵게 되는 것 같긴 합니다.)

Jin Kim 님

xgate 님

같은 원소가 두 번 옮겨지는 것을 방지하기 위해서는 고민을 좀 해야하는데, 두 분 모두 문제가 생기지 않게 잘 처리해주신 것 같습니다.
이렇게 메모리를 아끼면서 배열을 회전하는 주제에 대해서 『생각하는 프로그래밍』 컬럼2에 잘 정리되어 있습니다.

모두 수고하셨습니다. ^^

 

관련 도서

구글러가 전하는 IT 취업 가이드

구글러가 전하는 IT 취업 가이드

구글러가 전하는 IT 취업 가이드 지은이 : 게일 맥도웰 / 옮긴이 : 강은진 정가 : 16,000원   344쪽 / 판형 : 145*227 / 판 출간일 : 2012년 7월 15일 ISBN-13 : 978-89-6626-042-3 지은이 소개 게일 맥도웰(Gayle McDowell) 구글에서 3년간 일하면서 채용 위원회에서 1000명이 넘는 지원자의 면접 결정 과정에 참여했다....
문제로 풀어보는 알고리즘 : 프로그래밍 트레이닝 Q&A

문제로 풀어보는 알고리즘 : 프로그래밍 트레이닝 Q&A

  소스코드   지은이 : 황인욱, 김용혁 정가 : 25,000원   408쪽 / 1판 출간일 : 2012년 8월 1일 ISBN-13 : 978-89-6626-046-1     저자소개 황인욱 서울대학교 컴퓨터공학부에서 학사와 석사 학위를 취득하였다. 티맥스소프트 연구소에서 검색엔진과 웹 크롤러를 개발하였고, 삼성전자 생산기술연구소...
생각하는 프로그래밍(신판_무선)

생각하는 프로그래밍(신판_무선)

생각하는 프로그래밍 (Programming Pearls )       지은이 : 존 벤틀리 / 옮긴이 : 윤성준, 조상민 정가 : 22,000원   424쪽 / 판형 : A5 / 신판 1쇄 출간일 : 2013년 12월 24일 ISBN-10 : 978-89-6626-099-7 ISBN-13 : 978-89-6626-101-7   ...
TrackBack URL : http://www.insightbook.co.kr/post/3876/trackback
Leave a comment

36 Comments.

  1. 아웃풋이 3 8 이렇게 되어 있네요. 3은 0의 개수인 것 같은데 이것도 출력해야되나요?

    • 네~ 맞습니다. ^^
      (오해가 없도록 문제를 살짝 다듬었습니다.)

  2. 문제 풀이 입니다.
    https://gist.github.com/3668153

    문제 풀이 기한이 있었네요. 풀어 놓고 안 올리고 있었는데…

  3. 다른 일로 인사이트 책을 찾다가 이벤트를 발견하고
    오밤중에 급히 풀어보게 되었네요~
    (내일 휴가라는 것이 다행! 중요한 일이 있다는 것이 함정! :mrgreen: )
    http://artintel.tistory.com/entry/insightproblem

  4. http://artintel.tistory.com/entry/insightproblem
    모처럼 다른 책 때문에 들어왔다가, 이벤트 발견하고 급히 풀어보고 남깁니다.
    트랙백을 보내기는 했는데, 제대로 날라갔는지 모르겠네요 :mrgreen:

Leave a Reply


[ Ctrl + Enter ]

Trackbacks and Pingbacks: