레이블이 programming인 게시물을 표시합니다. 모든 게시물 표시
레이블이 programming인 게시물을 표시합니다. 모든 게시물 표시

2009년 4월 1일 수요일

LispIDE - 가볍게 쓸 수 있는 Windows 용 Lisp editor

Windows 환경에서 Lisp으로 간단한 코드를 작성하고 간편하게 실행해볼 수 있는 프로그램을 소개해드립니다. 물론 Emacs + SLIME 궁합이 상당히 강력하긴 하지만, 몇 줄 안되는 짧은 코드를 작성하고 실행해보는 데 그 무거운 Emacs를 실행하기는 좀 부담스러울 때가 있습니다.(저만 그런가요?) 그래서 뭔가 대체할 만한 것이 없을까 찾아보다가 발견하게 된 것이 바로 LispIDE입니다. 아마도 Common Lisp이나 Scheme 공부를 막 시작하시는 분들에게 특히 유용할 것 같네요.


LispIDE 특징을 살펴보면,
  • Lisp과 Scheme 소스에 대한 구문 강조(Syntax Highlighting) 지원
  • SBCL, CLISP, Corman Lisp 등 대부분의 commandline Lisp과 Scheme 구현체 지원
  • 편집창에 다중 탭 지원
  • 간편한 REPL 기능 제공 (Lisp 표현식을 손쉽게 전송)
  • 커서 키로 제어 가능한 편리한 history 기능 제공
  • CHM 형식의 HyperSpec, CLtL2 포함
  • Lisp 재시작 버튼 제공
LispIDE는 무료로 사용 가능한 freeware이고 소스도 함께 공개되어 있습니다. 홈페이지에 darcs 저장소에서 내려받을 수 있는 방법을 친절하게 알려주고 있습니다. :)

잡담.
최근 Windows 상에서 Emacs 23 CVS + SLIME CVS 궁합으로 SBCL을 연결해 사용해보면 약간의 문제가 있더군요. REPL buffer 상에서 입력한 표현식에 에러가 발생하면 그 다음부터 SBCL과 Emacs 사이의 pipeline에 문제가 생겨 더 이상 표현식이 전달되지 않는 현상이 생깁니다. CLISP은 별 문제가 없어서 당분간은 CLISP을 사용하려고 하는데, 속도면에서 월등한 SBCL을 쓰지 못하는 게 좀 아쉽습니다. 좋은 해결 방법 아시는 분 안계세요? :-$

2009년 3월 31일 화요일

[Common Lisp] 로또(Lotto) 번호 생성기

먹고 살기 점점 힘들어져서 이래저래 한숨만 나오는 요즘입니다. 그래서, 혹시나 하는 기대로 로또를 해보기도 하는데, 이건 그때 쓸려고 Common Lisp으로 만든 로또 번호 생성 장난감 코드입니다. 번호를 하나씩 뽑을 때마다 난수 발생 방식으로 수 배열을 섞어줍니다.
(defun random-comp (a b)
(if (= (random 2) 1) t nil))

(defun take-random (lst n mixcnt)
(cond ((null lst) ())
((<= n 0) ())
(t
(let ((nlst
(dotimes (cnt mixcnt lst)
(setq lst (sort lst #'random-comp)))))
(cons (car nlst) (take-random (cdr nlst) (1- n) mixcnt))))))

(defun gen-lotto-seq (mixcnt)
(let ((lst (loop for i from 1 to 45 collect i)))
(take-random lst 6 mixcnt)))

(defun gen-lotto-helper (try mixcnt)
(if (<= try 0)
nil
(cons
(let ((lst (gen-lotto-seq mixcnt)))
(print lst)
(print (apply #'+ lst))
(finish-output)
(sort lst #'<))
(gen-lotto-helper (1- try) mixcnt))))

(defun gen-lotto (try &optional (mixcnt 1000))
(setq *random-state* (make-random-state t))
(gen-lotto-helper try mixcnt))

실행 방법)
(gen-lotto <시도할 게임 수 번호> <하나를 뽑을 때마다 수열을 섞는 회수, 기본값 1000>)

예)
(gen-lotto 5 500) ; 총 5 게임을 시도하고, 각 번호를 뽑을 때마다 500 번씩 섞음
(gen-lotto 3) ; 총 3 게임을 시도하고, 각 번호를 뽑을 때마다 1000 번씩 섞음


아래는 실제로 실행해본 스크린샷입니다.



주의.
이 코드로 인해 발생할 수 있는 정신적 스트레스 및 물질적 궁핍 또는 결여에 대해 저는 어떠한 책임도 지지 않습니다. 단, 이 코드로 인해 발생한 물질적 형태의 이익에 대해 사례를 하시겠다면 마다 하지는 않겠습니다. ;-)

2008년 8월 6일 수요일

Source Insight에서 Symbian Build Log Parsing으로 Error Link 만들기

Source Insight에서 Symbian Build Log Parsing으로 Error Link 만들기

Source Insight에서 Symbian Build Log Parsing으로 Error Link 만들기

Parse Source Links 기능이란?

  • Source Insight에서 build 등의 결과물로 생성된 log를 분석하여 error나 warning 같은 항목에 대해 link를 만들어주는 기능입니다.
  • 만들어진 link를 사용하여 error 또는 warning이 발생한 source 위치로 즉시 이동이 가능합니다.

Build script for Symbian

  • 먼저, Source Insight에서 간편하게 build할 수 있도록 도와주는 batch script가 필요합니다.
  • 첨부된 mybuild.bat.rar 파일을 download한 후 압축을 풀고 PATH 환경 변수에 지정되어 있는 적절한 위치에 복사해둡니다.
    혹은 파일이 복사된 위치를 PATH 환경 변수에 추가해줍니다.
  • 이 batch script는 다음과 같은 방식으로 동작합니다.
    1. 현재 편집 중인 소스와 동일한 경로에서 bld.inf 파일을 찾아 그 파일이 존재하면 build를 수행합니다.
    2. 없다면, 현재 편집 중인 소스와 동일한 경로에서 group\bld.inf 파일을 찾아 그 파일이 존재하면 build를 수행합니다.
    3. 역시 없다면, 현재 편집 중인 소스와 동일한 경로에서 bld\bld.inf 파일을 찾아 그 파일이 존재하면 build를 수행합니다.
    4. 그래도 없다면, 한 단계 상위 폴더로 이동한 후 1 번부터 반복합니다.
      ※ 무한 반복을 막기 위해 최대 3 단계까지만 상위 폴더를 살피도록 되어 있습니다.

Parsing Build Logs

이제 mybuild.bat를 사용해 Custom Command에 설정을 추가하면 됩니다.
  1. Options 메뉴 -> Custom Commands... 항목을 실행합니다.


  2. Command 콤보박스에서 Build Project 항목을 선택합니다.


  3. 그림에서 보이는 것과 같이 설정 내용을 입력합니다.
    1. mybuild.bat script를 사용하여 'build armv5' 옵션으로 build 수행하는 설정입니다.
    2. script 실행 경로를 현재 편집 중인 파일의 경로로 지정합니다.
    3. 편집 중이던 파일을 저장하고 build 실행하면서 출력 결과를 capture하는 설정입니다.
    4. capture한 출력 결과를 parsing 하도록 설정합니다.
    5. parsing pattern이 File, Line 순임을 지정합니다.
    6. parsing pattern을 설정합니다.
      • Error와 Warning 포함: ^"\(.+\)", line \([^:]+\): [EW].*
      • Error만 포함: ^"\(.+\)", line \([^:]+\): E.*
    7. 반드시 Close 버튼을 눌러 설정한 내용을 저장합니다.


  4. 앞서 설정했던 Build Project와 마찬가지로 Clean Build 항목도 설정합니다.


  5. 마지막으로 Compile File 항목도 설정합니다.


Toolbar 설정 및 Key 할당

  • Toolbar 설정 - Source Insight에서는 build와 관련된 toolbar를 별도로 제공하고 있습니다.
    1. View 메뉴 -> Toolbars -> Build 항목을 실행합니다.


    2. 그러면 toolbar 영역에 다음과 같은 toolbar가 추가됩니다.


  • Key 할당
    1. Options 메뉴 -> Key Assignments... 항목을 실행합니다.


    2. 그림과 같이 Build 항목들에 대해 적절한 key를 할당해줍니다.
      1. build라고 입력하면 아래 콤보박스에 build와 관련된 항목들만 추려서 보여줍니다.
      2. 새로운 key를 할당할 항목을 선택하고 Assign New Key... 버튼을 누른 후 할당할 키조합을 눌려줍니다.
      3. OK 버튼을 눌러 설정한 내용을 저장합니다.


실행 관련 Screenshot

  • build를 실행한 모습입니다.


  • build 중 error가 발생했을 때 해당 source 위치에 대한 link를 생성해준 모습입니다.


2008년 8월 5일 화요일

Source Insight에서 Custom Token Macro 활용하기

Source Insight에서 Custom Token Macro 활용하기

이 내용은 제 springnote에 정리한 내용을 옮겨온 것입니다.


Token Macro란?

  • Token Macro는 소스에 삽입되어 있는 특정 macro 문구를 Source Insight가 올바로 해석할 수 있도록 원문으로 풀어서 기술해주는 기능입니다.
  • Source Insight가 지원하는 token macro 파일은 다음과 같습니다.
Language File Name
C and C++ C.tom - default 파일이 Source Insight에 포함되어 있음
HTML Html.tom
Java Java.tom
Resource Files Rc.tom
X86 Assembly Language X86.tom
Perl Perl.tom
  • 내 문서/Source Insight 폴더 아래에 두면 모든 프로젝트에 공통 적용됩니다.
  • 각 프로젝트의 root 폴더에 tom 파일을 두면 그 프로젝트에 대해 공통 tom 파일보다 우선합니다.

Symbian 개발 소스를 위한 설정

  • Symbian 개발 소스에도 특별히 알려주지 않으면 소스의 parsing이 제대로 되지 않아 참조가 꼬이는 문제가 발생합니다.
  • 이 문제를 해결하기 위해 e32def.h 파일 등의 내용을 가져와 C.tom 파일에 적절히 추가해주면 됩니다.
  • Symbian SDK 3.2를 기준으로 미리 작성해둔 C.tom 파일을 첨부하였습니다.
    1. 첨부된 C.tom 파일을 내 문서/Source Insight 폴더에 복사해넣습니다. 원래 있던 원본 파일은 백업을 해두시는 것이 좋습니다.
    2. Project를 rebuild 합니다.
      Project 메뉴 -> Rebuild Project 항목 선택
      ※ Project를 rebuild 하지 않아도 상수 정의 등과 같은 단순한 macro의 경우 즉시 정상적으로 보이게 됩니다. 하지만 정확한 참조 DB 생성을 위해서는 rebuild 해주는 것이 좋습니다.
  • 스크린샷
    • C.tom 파일을 적용하기 전
      _LIT로 정의된 문자열 상수가 제대로 parsing되지 못하고 엉뚱한 ID로 해석됩니다.

    • C.tom 파일을 적용한 후
      _LIT로 정의된 문자열 상수에 대한 참조가 정상적으로 잘 표시됩니다.



      rss 또는 rls에 정의된 resource 참조도 정상적으로 잘 찾아줍니다.

2008년 8월 4일 월요일

Source Insight에서 Custom Language 추가하기

Source Insight에서 Custom Language 추가하기

이 내용은 제 springnote에 정리해둔 것을 가져온 것입니다.


Custom Language란?

  • Source Insight에서 기본적으로 제공하는 프로그래밍 언어 외에 사용자가 새로운 언어 타입을 재정의하거나 추가할 수 있는 기능을 말합니다.
  • 가장 일반적으로 많이 사용되는 C/C++, Java 등의 언어에 대한 Language Definition은 이미 Source Insight에 포함되어 있는데, 이것들 외에 사용자가 별도로 더 추가하고 싶은 언어가 있을 수 있습니다. 이럴 때 사용하는 것이 Custom Language 기능입니다.
  • 또는 Symbian C++ 등과 같이 별도의 추가적인 파일 확장자나 parsing 규칙을 일부 사용하는 경우에 기존 Language Definition을 상속/재정의 해서 사용할 수도 있습니다.

Custom Language File 구하기

  • 기본적으로 Source Insight 공식 홈페이지에서 제공하는 Custom Language File(이하 CLF)을 사용할 수 있습니다.
  • 인터넷 검색을 통해서 몇몇 CLF 파일을 구할 수 있기도 하지만, 의외로 드뭅니다. :(
  • 사용자가 직접 CLF를 만드는 것도 가능합니다. 이 작업은 좀 번거롭고 시간이 걸릴 수 있습니다.

Custom Language 추가하기

Custom Language를 추가하는 데에는 두 가지 작업을 필요합니다. 하나는 Language 자체에 대한 parsing 정보를 등록하는 것이고, 나머지는 등록한 Language를 Project에 적용할 수 있도록 Document Option에 추가해주는 것입니다.
  1. 새로운 Language 추가하기 
    1. Options 메뉴 -> Preferences 메뉴 -> Languages 탭으로 이동합니다.



    2. Import 버튼을 눌러 원하는 CLF 파일을 가져옵니다.
      Add 버튼을 눌러서 새로운 Language를 추가하고 직접 keyword 편집이나 symbol parsing 규칙 등록 등의 작업을 해줄 수도 있습니다.



    3. 이제 Languages 탭에서 새로운 Language가 추가된 것을 확인할 수 있습니다.
      ※ 사용자가 추가한 Custom Language는 아이콘이 약간 다릅니다.



  2. 추가한 Language에 대한 Document Option 추가하기 
    1. Options 메뉴 -> Document Options 메뉴를 실행한 다음 다이얼로그에서 Add Type 버튼을 눌러 새로운 타입을 추가합니다.



    2. 추가된 타입에 대한 상세 설정을 해줍니다.



      1. 이 Language Type이 적용될 확장자를 지정해줍니다.
      2. Include when adding to projects 항목을 체크해주어야 프로젝트 생성 시 해당 확장자 파일이 자동으로 추가됩니다.
      3. 위 첫 번째 단계에서 추가한 Custom Language를 지정해줍니다.

Symbian C++ 개발을 위한 추천 설정

Symbian 관련 개발 상에서는 일반 C++ 개발 상에서와 달리 추가되는 파일들이 몇 가지 더 있습니다. 그렇기 때문에 이 파일들을 별도의 Language Type으로 등록해주면 소스 분석에 더욱 도움이 됩니다.
  • 가장 먼저 Symbian C++ 관련 C.tom 파일을 적용해두셔야 합니다.
  • Symbian C++ 관련 source 파일 등록
    • 추가해야 할 확장자들: *.hrh;*.pan;*.inl;*.rsg;*.rh;*.loc;*.mbg;*.rss;*.rls
      주의: C++ Language Type에 Symbian C++ 관련 확장자를 등록해두신 분은 C++ Language Type 쪽에서 그 확장자를 제거해주실 필요가 있습니다.



  • Symbian C++ 관련 build script 파일 등록
    • 추가해야 할 확장자들: *.mmp;*.midef;*.inf;*.iby



2007년 8월 22일 수요일

Erlang 공부 - Tail Recursion으로 구현한 피보나치 수열

느리지만 지속적으로 Erlang 공부를 이어가고 있습니다. 이번에는 Tail Recursion(우리 말로는 '끝 재귀' 또는 '꼬리 재귀'라고 부르더군요.)에 대해 더욱 깊이 공부를 하면서 피보나치 수열(Fibonacci Sequence)을 tail recursion으로 구현해보았습니다.

우선, 피보나치 수열 구현으로 들어가기에 앞서 tail recursion이 무엇인지 간단하게 이해하고 넘어갈 필요가 있겠습니다. Tail recursion은 재귀 호출의 특수한 형태로서, 다음 재귀 호출이 끝난 이후 현재 함수 블럭 내에서 추가 연산을 할 필요가 없도록 구현하는 형태를 말합니다. 말이 좀 복잡한데, 예를 들어서 설명을 해보죠. (이해가 쉽도록 C 코드로 작성을 해봤습니다.)
int sum(int n)
{
if(n == 1)
return 1;
return n + sum(n-1);
}

이 코드에서 sum 함수는 1 부터 n까지의 합을 구하는 재귀 함수입니다. 'sum(3)'을 호출했다고 가정하고 그 수행 과정을 살펴보면 다음과 같습니다.
sum(3) =>
3 + sum(2) <-- (1)
3 + (2 + sum(1))
3 + (2 + (1))
3 + (3) <-- (2)
6
함수 호출의 깊이를 들여쓰기로 나타내었는데, (1) 에서 보이는 것처럼 'sum(2)'를 호출하기 전에 '3 + '라는 추가 연산의 여지를 남겨두고 있습니다. 그렇기 때문에 'sum(2)' 호출 전에 현재 함수 블럭의 상태를 stack에 저장해야 할 필요가 있고, 이렇게 저장된 상태는 다시 거슬러 올라오면서 (2)에서 복원되어 최종 연산으로 이어지게 됩니다.

똑같은 일을 하는 함수를 tail recursion으로 구현해봅시다.
int sum(int n, int acc)
{
if(n == 1)
return (acc+1);
return sum(n-1, acc+n);
}

이번 구현에서는 위에서는 없었던 acc라는 변수가 하나 더 추가되었습니다. Tail recursion에서는 이것을 Accumulator라고 부르는데, 현재 함수 블럭에 추가 연산의 여지를 남겨두지 않기 위해서 저장해야 할 데이터를 보관하는 용도로 사용됩니다. 이 sum 함수에서는 각 호출 단계별 합을 저장하게 되죠. 실행되는 결과를 보면 좀더 쉽게 이해가 됩니다.
sum(3, 0) =>
sum(2, 3) <-- (3)
sum(1, 5)
6 <-- (4)
6
6
위 결과에서 (3)을 보면 다음 'sum(2, 3)'을 호출하기 전에 저장해야할 상태가 없습니다. 그래서 (4) 이후에는 계속 동일한 값을 반환하는 것으로 호출이 마무리 됩니다. 이게 무슨 의미가 있냐구요? Tail Recursion Optimization, 즉 tail recursion 형태에 대한 최적화가 적용될 경우 실제 실행 결과는 다음과 같아집니다.
sum(3, 0)
sum(2, 3)
sum(1, 5)
6

이 결과에서 보시는 바와 같이 다음 재귀 호출을 수행한 뒤 그 반환값으로 추가 연산을 하지 않기 때문에 stack에 현재 함수 블럭의 상태를 저장하지 않고 그 상태를 바로 바꾼 뒤에 함수 블럭 처음부터 다시 실행을 하는 것입니다. 즉, 함수 호출(call)이 아닌 분기(jump)가 사용된 것과 같다는 말이죠. 이것은 결국 for 또는 while과 같은 loop가 실행되는 구조와 유사하게 변한다는 말이 됩니다.

주변에서 흔히 사용하고 있는 주요 C/C++ compiler를 비롯해서 다른 많은 프로그래밍 언어에서 tail recursion optimization을 지원하고 있습니다. Erlang 역시 지원해주고 있지요.

최적화가 적용된 tail recursion 구현의 특징은 stack-overflow가 발생하지 않는다는 것과 실행 속도가 non-tail recursion(끝 재귀가 아닌 일반 재귀)에 비해 빠르다는 것입니다. 재귀 함수의 알고리즘 구조에 따라서 그 차이가 극명하게 나타날 수도 있습니다. 아래에서 보게 될 피보나치 수열이 바로 그런 예입니다.

자, 그럼 본론으로 들어갑시다.
피보나치 수열의 정의는 다음과 같습니다.
f(x) = f(x - 1) + f(x - 2)
단, f(0) = 0, f(1) = 1

수열을 구하는 함수의 정의 자체가 재귀로 되어 있습니다. 그 모양 그대로 Erlang에서 재귀 함수 형태로 구현할 수 있습니다. Tail recursion 방식을 사용하지 않고 구현해보면 다음과 같겠지요.
-module(fibo).
-export([fibo/1]).

%% Fibonacci sequence - Recursion version
fibo(0) ->
0;
fibo(1) ->
1;
fibo(N) when N > 1 ->
fibo(N - 2) + fibo(N - 1).

그런데, 이 구현은 원칙적인 측면에서는 매우 직관적이고 바람직한 형태라고 할 수 있겠지만, 효율 측면에서는 매우 그렇지 못합니다.(제가 사용하는 HP nc8000 노트북에서 'fibo:fibo(100)'을 실행했더니 stack-overflow는 발생하지 않는데, 아무리 기다려도 답이 나오지 않더군요.)

자, 그러면 tail recursion을 적용해서 다시 한번 구현해봅시다.
-module(fibo2).
-export([fibo/1]).

%% Fibonacci sequence - Tail-recursion version
fibo(0) ->
0;
fibo(1) ->
1;
fibo(N) when N > 1 ->
fibo(N, 1, 1, 1).

fibo(N, I, Acc1, Acc2) when (N > 1) and (I < N) ->
fibo(N, I + 1, Acc2, Acc1 + Acc2);
fibo(N, N, Acc1, Acc2) ->
Acc1.

처음 구현 형태에 비하면 모양이 꽤 복잡해보입니다. 피보나치 수열 특성 상 세 개의 accumulator가 사용되었습니다. 'I'는 index를, 'Acc1'과 'Acc2'는 각각 f(n-2)f(n-1)의 계산값 저장을 위해 사용합니다. 구현에 대한 더욱 구체적인 이해는 여러분들께 맡기겠습니다. 이 구현보다 더 깔끔한 구현이 있을 수도 있으니 직접 한번 도전해보시는 것도 좋지 않을까요? ;)

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


[그림 1] fibo 실행 결과

정확한 시간을 측정해보지는 않았지만, 제 노트북(HP nc8000)에서 'fibo:fibo(40)'의 결과를 구하는 데 대략 3 ~ 4 초 가량이 소요됐으나, tail recursion으로 구현된 'fibo2:fibo(10000)'의 결과를 구하는 데에는 채 1 초도 걸리지 않더군요. Non-tail recursion 구현의 'fibo:fibo(100)'은 10 분 이상을 기다려도 답이 떨어지지 않아서 결국 중단하고 말았습니다. :-$

즐거운 Erlang 공부가 되시길...

2007년 8월 19일 일요일

Erlang 공부 - 넥슨 입사 시험 문제 1 번 풀이

지난 번에 Common Lisp으로 풀어 본 넥슨 입사 시험 문제 1 번에 대해서 이번에는 Erlang으로 다시 한번 시도해봤습니다.

상세한 문제 내용은 이전 글을 참고해주시고, 간단히 요약을 하면 다음과 같습니다.
1부터 5000 사이의 Self Number들의 합을 구하시오.

풀이 내용은 다음과 같습니다.
-module(selfnum).
-export([sum_of_digits/1,
generate/1,
get_self_numbers/2,
get_sum_of_self_numbers/2]).

sum_of_digits(N) ->
Digits = integer_to_list(N),
sum_of_digits1(Digits).

sum_of_digits1(Digits) ->
Nums = lists:map(fun(D) ->
D - $0 end,
Digits),
lists:sum(Nums).

generate(N) when N > 0 ->
N + sum_of_digits(N).

get_self_numbers(M, N) when M =< N ->
Range_Nums = lists:seq(M, N),
Gen_Nums = lists:map(fun generate/1, Range_Nums),
lists:subtract(Range_Nums, Gen_Nums).

get_sum_of_self_numbers(M, N) when M =< N ->
Self_Nums = get_self_numbers(M, N),
lists:sum(Self_Nums).

sum_of_digits 메서드(method)를 다르게 구현해봤습니다.
-module(selfnum).
-export([sum_of_digits/1,
generate/1,
get_self_numbers/2,
get_sum_of_self_numbers/2]).

sum_of_digits(N) ->
Digits = integer_to_list(N),
sum_of_digits(Digits, 0).

%%---------------------------------------
%% Tail-recursion 방식으로 구현
sum_of_digits([D|Rest], Acc) ->
I = D - $0,
sum_of_digits(Rest, Acc + I);
sum_of_digits([], Acc) ->
Acc.
%%---------------------------------------

generate(N) when N > 0 ->
N + sum_of_digits(N).

get_self_numbers(M, N) when M =< N ->
Range_Nums = lists:seq(M, N),
Gen_Nums = lists:map(fun generate/1, Range_Nums),
lists:subtract(Range_Nums, Gen_Nums).

get_sum_of_self_numbers(M, N) when M =< N ->
Self_Nums = get_self_numbers(M, N),
lists:sum(Self_Nums).

compile하고 각 메서드에 대해 실행한 결과는 다음과 같습니다.


[그림 1] 실행 결과

Erlang도 예전부터 관심은 있었는데, 계속 공부를 미루다 최근에 와서야 마음 먹고 집중해보고 있습니다. 오랫동안 C/C++, Java 관련 일만 해와서인지 패러다임이 다른 프로그래밍 언어에 익숙해지는 것이 쉽지 않습니다. 하지만, 재미있습니다. 모르고 있던 새로운 것을 알게 된다는 것은 그 자체만으로도 충분히 기쁨입니다. :)

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 방식으로 작성했으면 더 줄었을지도 모릅니다. 하지만 귀찮아서 그만 하렵니다. 이 부분은 여러분 몫으로 남겨두죠. ;-)

2007년 1월 7일 일요일

Common Lisp 공부 - 넥슨 입사 문제 1 번 풀이

요즘 공부 좀 해보려고 이것 저것 찔러보고 있는 중입니다. 아무 것도 하지 않고 계속 시간만 보내다가는 정말 머리가 굳어버릴 것만 같은 위기감을 느꼈기 때문이죠. 새해도 되고 했으니 설사 '작심삼일(作心三日)'이 될지언정 시도조차 하지 않아서야 사람이라고 하겠습니까.. 쩝..

아무튼, 찔러보는 것 중에서 Common Lisp이 있는데, 애자일 이야기에서 우연히 접하게 된 넥슨 입사 문제 중 1 번을 시험 삼아 구현해보았습니다. 공부를 막 시작한지라 구현 내용이 다소 비효율적이고 어눌할 수도 있으니 너그러이 이해해주세요. ;-)

문제 내용은 다음과 같습니다.
어떤 자연수 n이 있을 때, d(n)을 n의 각 자릿수 숫자들과 n 자신을 더한 숫자라고 정의하자. 예를 들어 d(91) = 9 + 1 + 91 = 101 이다. 이 때, n을 d(n)의 제네레이터(generator)라고 한다. 위의 예에서 91은 101의 제네레이터이다. 어떤 숫자들은 하나 이상의 제네레이터를 가지고 있는데, 101의 제네레이터는 91 뿐 아니라 100도 있다. 그런데 반대로, 제네레이터가 없는 숫자들도 있으며, 이런 숫자를 인도의 수학자 Kaprekar가 셀프 넘버(self-number)라 이름 붙였다. 예를 들어 1,3,5,7,9,20,31 은 셀프 넘버 들이다.

1 이상이고 5000 보다 작은 모든 셀프 넘버들의 합을 구하라.

풀이 내용은 다음과 같습니다.
;; 주어진 수의 각 자리수의 합을 구한다.
;; (예, 352 -> 3 + 5 + 2)
(defun sum-of-each-digit (x)
(if (< x 10)
x
(+ (mod x 10)
(sum-of-each-digit (truncate (/ x 10))))))

;; 주어진 수의 generated number를 구한다.
(defun get-generated-number (x)
(+ x (sum-of-each-digit x)))

;; 주어진 범위 내에 존재하는 generated number의 list를 구한다.
;; 범위: (x <= r < y)
(defun get-generated-number-list (x y)
(do ((i x (1+ i))
(gnum (get-generated-number x)
(get-generated-number i))
(gnums ()))
((or (>= gnum y) (>= i y))
(remove-duplicates (sort gnums #'<)))
(push gnum gnums)))

;; 주어진 범위 내의 정수 list를 구한다.
;; 범위: (x <= r < y)
(defun make-number-range-list (x y)
(do ((i x (1+ i))
(rnums ()))
((>= i y) (reverse rnums))
(push i rnums)))

;; 주어진 범위 내에 존재하는 Self Number의 list를 구한다.
;; 범위: (x <= r < y)
(defun get-self-number-list (x y)
(set-difference
(make-number-range-list x y)
(get-generated-number-list x y)))

;; 주어진 범위 내에 존재하는 Self Number의 합을 구한다.
;; 범위: (x <= r < y)
(defun sum-of-self-number-list (x y)
(apply #'+ (get-self-number-list x y)))

;; 1부터 5000 사이에 존재하는 Self Number들의 합을 구한다.
(sum-of-self-number-list 1 5000)

결과: 1227365

2005년 6월 1일 수요일

ID3 Tag에 관한 모든 것


ID3 Tag에 관한 모든 정보를 가지고 있다고 해도 과언이 아닐 정도로 꼭 필요한 정보만 체계적으로 정리해 두고 있는 사이트입니다.

http://www.id3.org

ID3 tag가 무엇이며 어떤 쓰임새가 있는지 간단히 소개하고, 과거 ID3v1으로부터 v1.1을 거쳐서 v2까지 진화해오는 동안의 간략한 history를 제공합니다. 그리고, ID3 Tag가 오디오 파일 내에 어떻게 위치하게 되는지 이해하기 쉽도록 도식화 해둔 것이나 개발자를 위해서 다양한 프로그래밍 언어로 구현된 구현체를 소개하고 있는 점은 군더더기 하나 없는 깔끔함을 보여주는 좋은 예일 겁니다.