2007년 2월 14일 수요일

Common Lisp 공부 - Google 입사 시험 문제

지난 번에 인터넷을 돌아다니다가 우연히 넥슨 입사 시험 문제를 발견하고는 이에 대해서 Common Lisp으로 재미삼아 풀어본 적이 있는데, 이번에는 Google 입사 시험 문제를 발견해버렸습니다. 문제 난이도로 보면 오히려 넥슨의 그것보다 좀 더 쉬워보이는 것 같기는 한데, 최적화를 할 수 있는 더 놀라운 방법이 함정으로 숨어 있는 것은 아닌지 의심되기도 합니다.

아래는 문제의 내용입니다. (이 문제의 출처는 http://ddingddong.egloos.com/788716입니다.)

양의 정수 n에 대해서 1과 n 사이에 1이 나오는 횟수를 나타내는 함수를 f(n)이라고 한다. 예를 들어 f(13)=6이다. f(n)=n이 되는 첫번째 양수는 1이다. 두번째 양수는 무엇인가?

이 문제에 대해서 제가 풀어본 내용은 다음과 같습니다.
(defun get-1-count-number-list (count)
  (do ((i 1 (1+ i))
       (cnt 0)
       (total 0)
       (nlist ()))
      ((= cnt count) (reverse nlist))
    (setq total
          (+ total
             (count #\1 (write-to-string i))))
    (if (= total i)
        (progn (incf cnt)
               (push total nlist)))))

문제의 출처에 Python으로 구현한 내용이 이미 있었지만, 일부러 그것을 보지 않고 Common Lisp으로 구현해보았습니다. 다 작성한 후 결과를 비교해보니 수를 문자로 바꾼 후 '1'의 개수를 세었다는 점에서 알고리즘이 거의 동일하더군요.

실행 결과는 다음 그림과 같습니다.



문제의 조건을 만족하는 수를 5개 정도 구해봤습니다만, 결국 원래 문제에서 요구하는 답은 199981이겠지요. 아무튼 답을 구해놓고 보니 처음 잠시 동안 암산으로 어찌 해보려던 제가 얼마나 무모했는지 알 수 있었습니다. :-$

제가 작성한 함수의 실행 시간과 사용된 메모리 공간을 확인해보기 위해서 일부러 time 함수를 사용했는데, Space 부분을 보시면 그 값이 엄청납니다. 결국 호기심이 발동한 저는 1의 개수를 산술적인 방법으로 세는 다른 함수를 만들어보았습니다. 모든 부분이 동일하고 단지 주어진 수에서 1의 개수를 세는 부분만 별도의 함수로 추가한 것입니다.
(defun get-1-count (num)
  (if (< num 10)
      (if (= num 1) 1 0)
      (+ (get-1-count (truncate (/ num 10)))
         (if (= (mod num 10) 1) 1 0))))

(defun get-1-count-number-list-2 (count)
  (do ((i 1 (1+ i))
       (cnt 0)
       (total 0)
       (nlist ()))
      ((= cnt count) (reverse nlist))
    (setq total
          (+ total
             (get-1-count i)))
    (if (= total i)
        (progn (incf cnt)
               (push total nlist))))

그리고, 이 함수에 대한 실행 결과입니다.



실행 시간은 좀 더 늘었지만, Space 사용량이 확연히 줄어든 것을 확인할 수 있습니다. get-1-count 함수를 recursion이 아닌 iteration 방식으로 작성했으면 더 줄었을지도 모릅니다. 하지만 귀찮아서 그만 하렵니다. 이 부분은 여러분 몫으로 남겨두죠. ;-)

댓글 7개:

  1. ㅋ 잠시 마법사책 가지고 공부했었는데

    리습 쓰는 분은 블로그 탐색하다가 처음 봤네요.

    ^^

    답글삭제
  2. 안녕하세요. 반갑습니다. ^^

    제 블로그는 워낙 방문자가 귀한데, 더군다나 댓글까지 남겨주시는 분은 거의 국보급(?)입니다. ^^;

    저는 그냥 약간의 관심으로 재미삼아 Lisp을 공부하고 있는데 그 수준이 아직 걸음마도 제대로 못 뗀 상태입니다. 겨우 tutorial 보고 있는 정도예요.

    Lisp에 대한 좋은 자료나 정보가 있으시면 많은 공유 부탁 드리겠습니다.

    좋은 하루 되세요~ :-)

    답글삭제
  3. 전 lisp 매뉴얼 번역하고 있습니다. 50%정도까지 하고 복습할 생각인데, 여기는 정말 저에게 도움이 많이 될 것 같네요. 제가 게을러서 대충 해석만 해 놓고 실제 코딩은 안 해서 실력이 터무니 없죠. 며칠 eval하기도 했는데, 주언어가 아니다 보니까 안 하게 되는 군요. 그럼 자료 공유해요.
    http://blog.naver.com/suritam9

    답글삭제
  4. 안녕하세요 ^^;
    저도 파이썬 공부하면서 자료를 찾다가 알게되었네요 그런데 lisp는 어떤 언어인지요? 설명 해 놓으신걸 보니 관심이 생기네요

    답글삭제
  5. 안녕하세요. 방문해주셔서 감사합니다.

    Lisp이 무엇인가에 대한 질문은 간단히 몇 마디로 답해 드리기에 제 내공이 심히 부족하다고 생각됩니다. ^^;

    대신 아래 링크로 가보시면 체계적으로 정리된 자료를 접하실 수 있을 것이라 생각됩니다.

    http://www.lisp.or.kr/wiki.php/%C4%BF%B8%D5%B8%AE%BD%C0

    성의 없다 생각지 마시고 부족한 제 능력을 탓해주세요~ ^^;

    답글삭제
  6. (defun count-1 (n) (count-if #'(lambda (i) (eql i #\1)) (write-to-string n)))

    (do* ((i 2 (+ i 1)) (cnt 1 (+ cnt (count-1 i))))
    ((= i cnt) i))
    댓글에 코드를 달기가 어렵군요. 문제 재밌습니다.

    답글삭제
  7. Blogger 기본 댓글 시스템이 좀 부족하긴 합니다. ^^; 근래의 글들에는 DISQUS가 적용되어 있어서 그나마 나은 편이지만, 이 글은 적용 전에 작성된 것이라 Blogger 기본 댓글 시스템을 그대로 유지하고 있어요. 암튼 댓글로 달아주신 코드가 군더더기 떨어져 나가고 깔끔하니 좋습니다. :) 방문 감사합니다.

    답글삭제