Books by Example2008.01.03 13:26
요즘들어 SW 분야의 명저들을 찾아 읽어보는 데 굉장히 많은 시간을 할애하고 있습니다. 최근에 보고 있는 책들 중 탁월하다고 생각하는 것으로는 "실용주의 프로그래머(The Pragmatic Programmers)", "생각하는 프로그래밍(Programming Pearls)", 그리고 "컴퓨터 프로그램의 구조와 해석(SICP)" 등이 있습니다.

보통 컴퓨터 분야의 책을 읽을 때, 많은 사람들이 연습문제는 건너뛰고 잘 풀어보질 않습니다. 하지만 저는 이 연습문제들에 본문에서 얻을 수 있는 지식 + 알파가 녹아있다고 믿습니다. SW 분야의 명저가 된 책들에는 이런 연습문제들이 풍부하고, 굳이 연습문제가 아니더라도 많은 예제들이 포함되어 있습니다.

이런 문제들을 풀어보고 프로그램을 만들 떄 마다, 이 블로그에 올려보도록 하겠습니다. 단순히 정리한다는 목적도 있고, 저와 비슷한 고민을 하는 다른 사람들에게 유용한 정보를 제공하고자 하는 목적도 있고, 보다 많은 사람들을 이런 명저로 이끈다는 목적도 있습니다. 부디 제가 올리는 모든 문제들과 해설이, 그런 목적에 충실하기를 바랍니다.

현재까지 이와 관련하여 올려진 글들의 목록은 다음과 같습니다. 

"컴퓨터 프로그램의 구조와 해석(SICP)"


"생각하는 프로그래밍(Programming Pearls)"

이 목록은 이 주제에 대한 새로운 포스팅이 올라올 때 마다 업데이트됩니다.

신고
Posted by 이병준

소중한 의견, 감사합니다. ^^

  1. 저는 스터디 그룹에서 온라인으로 공부한 흔적은 남기기로 했기에
    연습문제를 블로그에 올리기로 했습니다.
    (아직 위키에 적응이 완료되지 않아서....OTL....)
    계속 좋은 글 부탁드립니다.^^

    2008.01.03 16:07 신고 [ ADDR : EDIT/ DEL : REPLY ]
  2. 지나가다 글 남깁니다.
    저는 운좋게도 학부때 관련 교재로 수업을 할 수 있었죠.
    좀 힘들긴 했지만 가장 인상적인 과목 중 하나였습니다.
    시간 나면 다시 한 번 보고 싶네요.
    연습문제 답 모아놓는 위키도 있으니 참고하세요.
    http://sicp.org.ua/sicp

    2008.01.03 23:50 신고 [ ADDR : EDIT/ DEL : REPLY ]

Books by Example/SICP2007.12.16 03:55

연습문제 1.21은 너무 쉬우므로 생략합니다. 1.22는 이미 있는 소스 코드를 가지고 search-for-primes라는 프로시저를 작성하는 것입니다. 기존의 프로시저를 아무 수정없이 사용할 수는 없는데, 그것은 start-prime-test가 검사 대상 수 n이 prime이 아닐 때 false를 반환하도록 구현되어 있지 않기 때문입니다. 그래서 아래의 소스 코드 붉은 색으로 표기된 부분에 false를 반환하는 코드를 넣었습니다. (저것말고 더 쉬운 방법이 있을텐데 지금으로선 잘 모르겠네요. ㅋ)

아 그리고, PLT-scheme은 SICP 책에 나오는 runtime이라는 함수를 제공하지 않습니다. 대신 current-seconds나 current-milliseconds같은 함수들을 제공합니다. (language를 PLT 아래에 있는 것 중 하나로 선택하면 사용할 수 있습니다.) 그래서 그 함수들을 사용하도록 코드를 고쳤습니다. (아래에 녹색 표시된 부분)

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (square x) (* x x))

(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n) (= (smallest-divisor n) n))

(define (timed-prime-test n)
  (start-prime-test n (current-milliseconds)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime n (- (current-milliseconds) start-time))
      (= 1 0)))

(define (report-prime n elapsed-time)
  (newline)
  (display n)
  (display " is prime and ")
  (display elapsed-time)
  (display " milli-seconds have passed"))

(define (search-for-primes start-from count)
  (if (> count 0)
      (if (even? start-from)
          (search-for-primes (+ start-from 1) count)
          (if (timed-prime-test start-from)
              (search-for-primes (+ start-from 2) (- count 1))
              (search-for-primes (+ start-from 2) count)))))

(display (sqrt 10))
(search-for-primes 1000000000 3)
(newline)
(search-for-primes 10000000000 3)
(newline)
(search-for-primes 100000000000 3)
(newline)
(search-for-primes 1000000000000 3)

맨 마지막의 8줄은 실행 결과를 확인하기 위한 부분입니다. sqrt 10이 대략 3입니다. search-for-primes의 실행 결과는 탐색이 시작되는 수의 자릿수가 10이 증가할 때 마다 대략 3배씩 늘어납니다. (따라서, 책에서 '정말 그러한가?'하고 묻는 부분에 대한 답은 'yes'라고 할 수 있겠습니다.)

아이가 아파서 늦게까지 잠을 잘 수가 없었는데, 이제 열도 떨어지고 했으니 그만 자야겠습니다.


신고
Posted by 이병준

소중한 의견, 감사합니다. ^^

  1. runtime이 안되어 고생하였는데 먼저 해결책을 알려주셔서 고맙습니다.^^ㅜㅜ

    2008.01.17 15:20 신고 [ ADDR : EDIT/ DEL : REPLY ]

Books by Example/SICP2007.11.17 17:50

본문에 나오는 이야기입니다만, T(a,b): (a <- a + b, b <- a)라고 하고, T 규칙을 순차적으로 n번 적용한 것을 T^n이라고 하면, T^n(1,0)은 n번째 피보나치 수열이죠.

그런데 사실 이 규칙 T는

  T_{p,q}(a,b): (a <- bq + aq + ap, b <- bp + aq)

의 특별한 케이스(p=0, q=1)입니다.

여기까지를 알고 있을때, 규칙 T_{p,q}를 연속적으로 두 번 적용해 보면(T_{p,q}^2) 어떻게 되나요?

a <- (bp + aq)q + (bq+aq+ap)q + (bq+aq+ap)p
       = b(2pq+q^2) + a(2pq+q^2) + a(p^2+q^2)
b <- (bp+aq)p + (bq+aq+ap)q
       = b(p^2 + q^2) + a(2pq+q^2)

결국, p^2+q^2 = p', 2pq+q^2 = q'로 놓게되면

  a <- bq' + aq' + ap', b <- bp' + aq'

이 됩니다.

그렇다면 피보나치 수열을 계산하는데 필요한 인자를 a, b, p, q의 네 가지로 보았을 때, 이터레이션의 수를 반으로 줄이고 싶으면 그럴 때 마다 a, b, p, q를 a, b, p^2+q^2, 2pq+q^2로 바꾸면 되겠군요. 그렇게 할 수 없을 때에는 a, b, p, q를 bq+aq+ap, bp+aq, p, q로 바꾸면 되고요.

맨 마지막에는 이렇게 해서 만들어진 최종 4-tuple을 다시 (a, b, p, q)라고 했을 때 b를 반환하도록 하면 되겠습니다.

그렇다면 결국 책에 나온 Scheme 문제는 다음과 같이 채우면 되겠군요.

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
           ((even? count) (fib-iter a b (+ (* p p) (* q q)) (+ (* 2 p q) (* q q)) (/ count 2)))
           (else (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1)))))

이 문제는 Scheme 식으로 생각하는 문제라기 보다는 수학 문제처럼 느껴진다는...


신고
Posted by 이병준

소중한 의견, 감사합니다. ^^

  1. 전 피보나치 수열을 로그 차수가 나오는 알고리즘이 있다는 점이 무척 신기했습니다.^^

    2008.01.14 11:31 신고 [ ADDR : EDIT/ DEL : REPLY ]

Books by Example/SICP2007.11.15 22:27
1.16번

연습문제 1.16은 b를 n번 곱하는 문제의 복잡도를 어떻게 n에서 log n 으로 (밑수는 2)로 낮출 수 있느냐 하는 문제입니다. b * b * b * b * ... 이렇게 하는 대신 b를 계속해서 제곱해 나가다가 (b --> b^2 --> b^4 --> ... ) 마지막에 n이 홀수냐 짝수냐에 따라서 그 결과에 b를 한 번 더 곱해주거나 아니면 그냥 놔두거나 하면 되겠죠.

굉장히 간단한 아이디어입니다만, 의외로 실무에서 프로그래밍을 하다 보면 이렇게 간단한 부분도 놓치게 되는 일이 많은 것 같습니다.

비슷한 종류의 사례로 strcat에 관한 것도 있는데, 이에 대해서는 "조엘 온 소프트웨어"라는 책에 보면 나옵니다. strcat이 보통 '널 문자'를 찾기 위해 포인터를 문자열 앞에서 뒤 방향으로 계속 검색해 나가는데, 그런 이유로 strcat을 여러번 적용하면 문자열을 여러 개 합칠 경우 그 계산 복잡도가 n^n으로 바뀌고 만다, 뭐 그런 이야기였습니다.

아무튼 이 문제의 Scheme 식 해답은 다음과 같습니다.

(define (fast-expt-iter b n)
  (define (fast-expt-iter-part b m c)
    (cond ((= c 0) m)
          ((even? c) (fast-expt-iter-part (* b b) m (/ c 2)))
          (else (fast-expt-iter-part b (* b m) (- c 1)))))


  (fast-expt-iter-part b 1 n))

(fast-expt-iter 2 32)

"되도는 알고리즘보다 반복하는 알고리즘을 짜는 것이 더 어렵다"고 해서 (사실 그렇습니다) 문제 풀기전에 좀 겁먹었습니다만, 문제 자체가 쉬워서 크게 어려울 것은 없었습니다.

1.17번, 1.18번

그러면 a * b를 그런 식으로 계산할 수도 있겠군요. a * b를 덧셈만으로 구현한다고 하면 a를 b 번 더해나가야 되겠습니다만, a를 2a, 4a, 이런 식으로 계속 두 배 해 나가는 식으로 하면 더 빨리 돌도록 구현할 수 있겠습니다. 원래는 17번은 재귀 프로세스, 18번은 반복 프로세스로 구현하는 것인데, 재귀 프로세스로 구현하는 것은 반복 프로세스로 구현하는 것에 비해 쉬으므로, 반복 프로세스로 구현하는 경우만 보였습니다.

(define (double x) (* 2 x))

(define (halve x) (/ x 2))

(define (mul a b)
  (define (f adder result count)
    (cond ((= count 0) result)
          ((even? count) (f (double adder) result (halve count)))
          (else (f adder (+ result adder) (- count 1)))))
  (f a 0 b))

(mul 3 7)

신고
Posted by 이병준

소중한 의견, 감사합니다. ^^

Books by Example/SICP2007.11.10 16:11

파스칼의 세모꼴(Pascal's Triangle) 문제는 널리 잘 알려진 문제입니다. 하지만 안타깝게도 이 책을 읽기 전에 저는 이 문제를 함수형 언어에서는 풀어본 적이 없습니다. 파스칼의 세모꼴 모양은 흔히 알려져 있는 대로, 다음과 같습니다.

http://www.mathsisfun.com/pascals-triangle.html

출처: http://www.mathsisfun.com/pascals-triangle.html


이 문제를 저는 이렇게 풀기로 했습니다. 우선 위에서 부터 아래쪽으로, 1부터 증가하는 번호를 매깁니다. 이것을 x라고 했습니다. 그리고 왼쪽에서 오른쪽으로 역시 1부터 증가하는 번호를 매깁니다. 이것을 y라고 합니다. 그렇다면 x와 y의 값에 따라서, 모든 수는 (x, y)의 유일한 좌표 값을 가집니다. 이 x, y 사이의 관계를 알 수 있으면 어떤 좌표에 있는 값이 무엇인지 알 수 있습니다.

(define (f x y)
  (if (or (= y 1) (= x y)) 1
      (+ (f (- x 1) (- y 1)) (f (- x 1) y))))


그 값을 알아내는 공식은 위와 같습니다. 이 공식을 만든 다음에, 이 공식을 사용해서 파스칼 삼각형을 화면에 출력하도록 했습니다. 안타깝게도 출력에 관한 사항을 어떻게 처리할 지는 그다지 배운 바가 없어서, 대충 출력하도록 만들었습니다. 적당히 잘 뜯어고치면, 이것보다는 더 나은 출력을 만들 수 있을 거라 믿습니다.

(define (pascal n)
  (define (pascal-iter x y)
    (cond ((and (= x n) (= y (+ n 1))) (display ""))
          ((= y (+ x 1)) (display "\n") (pascal-iter (+ x 1) 1))
          (else (display (f x y)) (display " ") (pascal-iter x (+ y 1)))))
  (pascal-iter 1 1))


이 코드를 다음과 같이 하여 실행합니다.

(pascal 5)

그러면 아래의 삼각형을 얻습니다. (5 보다 큰 수를 입력하면 출력이 영 볼썽 사납습니다 ㅋㅋ)

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1


그런데 문제를 풀고보니 화면 출력에 대한 내용까지를 풀 필요는 없고, 각 좌표의 수가 무엇인지를 알수만 있으면 되는 것 같습니다. (괜히 삽질했구나 하는 생각이 듭니다 -_-;;)

화면 출력에 관한 코드를 만들 때 곤란했던 부분은, 흔히 C++에서는 다음과 같이 표현되는 루프를 어떻게 만들 것이냐 하는 점이었습니다.

for ( int i = 1; i <= n; ++i ) {
    for ( int j = 1; j <= n; ++j ) {
        ...
    }
}


뭐 보시다시피 대충 해결했습니다. ^O^;;

신고
Posted by 이병준

소중한 의견, 감사합니다. ^^

  1. estel

    정보 감사합니다!

    2016.01.21 19:53 신고 [ ADDR : EDIT/ DEL : REPLY ]

Books by Example/SICP2007.11.10 09:50

이 문제는 되도는 프로시저를 사용해 되도는 프로세스와 반복 프로세스를 구현해 보는 문제입니다. 되도는 프로세스는 흔히 "재귀적 프로세스"라고 부르는 것이고, 반복 프로세스는 "iterative process"입니다. (프로시저와 프로세스는 다른 개념인데, 프로시저는 코드라고 생각하면 되고, 프로세스는 그 코드에 의해 만들어지는 실행 궤적이라고 생각하면 됩니다. 따라서 프로시저는 재귀적으로 구현되더라도, 그 실행 궤적 자체는 반복적이 되는 일이 Scheme같은 언어에서는 발생할 수 있습니다. C에서라면 좀 곤란하지만요.)

C와 같은 언어에서 전자는 흔히 '함수의 재귀적 호출'에 의해 구현되고 반복 프로세스는 for나 while과 같은 별도의 문법에 의해 구현됩니다만, lisp는 for와 같은 문법을 지원하지 않기 때문에 재귀적 프로세스나 반복 프로세스나 전부 재귀적인 프로시저에 의해 구현해야 합니다. 처음에는 이것이 이해가 잘 되지 않을 수 있습니다. 책에서는 재귀적 프로세스와 반복 프로세스의 차이를 다음과 같이 언급하고 있습니다.

반복하는 프로세스에서는 프로그램 변수가 프로세스 단계마다 어떤 상태에 있는지 정확하게 나타내기 때문에, 계산을 잠시 멈추더라도 각각의 변수의 값만 알면 실행기가 곧바로 계산을 이어갈 수 있다. 하지만 되도는 프로세스는 그렇지 않다. 프로세스 안에 상태변수도 없을 뿐더러, 뒤로 미뤄 둔 연산의 끈을 이어가면서 '어디까지 계산했는지' 알아내려면, 실행기 속에 숨은 정보가 더 있어야 한다. 끈이 길 수록 그런 정보는 더 많아진다.



1.11번 문제는 함수 f(n) = (n-1) + 2f(n-2) + 3f(n-3) (n < 3일때는 f(n) = n)을 재귀적 프로세스와 반복 프로세스 두 가지 다른 버전으로 구현해 보는 것입니다. 통상 재귀적 프로세스는 하향적으로 문제 풀이가 전개되는 반면, 반복 프로세스는 상향적으로 문제 풀이가 전개됩니다. 전자는 좀 연역적인 성격이 있고, 후자는 좀 귀납적인 성격이 있다, 이렇게도 볼 수 있겠습니다. 그 점을 염두에 두면 문제풀이가 쉬워지는 것 같습니다.

답은 아래에 있습니다.

(define (func n)
  (if (< n 3) n
      (+ (- n 1) (* 2 (func (- n 2))) (* 3 (func (- n 3))))))

(define (func-iter n)
  (define (func-iter-part a b c count)
    (if (= count n) (+ (- count 1) (* 2 b) (* 3 c))
        (func-iter-part (+ (- count 1) (* 2 b) (* 3 c)) a b (+ count 1))))
  (if (< n 3) n
      (func-iter-part 2 1 0 3)))

(func 8)

(func-iter 8)

이렇게 할 수도 있습니다.

(define (func-iter n)
  (define (func-iter-part a b c count)
    (if (= count (+ n 1)) a
        (func-iter-part (+ (- count 1) (* 2 b) (* 3 c)) a b (+ count 1))))
  (if (< n 3) n
      (func-iter-part 2 1 0 3)))


거의 같은데 루프를 한 번 더 도는 것만 다르죠. ㅋㅋ 그런데 이 문제에 대한 인터넷 해답을 보니, 인터넷에서의 해답이 제 답과 조금 다르군요. 왜 그런가 잠시 생각해봤는데... 책에 오타가 있습니다 ㅎㅎ

To English Readers: There's typo in the exercise 1.11 of korean version of SICP. So. ignore the above answer - the answer for the 'wrong' question. Correct answer is given below (only the iterative version of the answer. I didn't give the recursive version of the answer, because it's too easy).

오타가 있어도 문제가 안풀리는 건 아닙니다만, 아무튼 답은 조금 달라집니다. 원서에 실린 문제 공식은 f(n) = (n-1) + 2f(n-2) + 3f(n-3)이 아니라 f(n) = f(n-1) + 2f(n-2) + 3f(n-3) 입니다. (한글판에는 f가 빠졌습니다.) f가 있을 경우의 해답은 다음과 같습니다. 역시 반복 프로세스의 경우만 싣습니다. 재귀적 프로세스의 경우에는 답이 뻔해서...

(define (f-b n)
  (define (f-b-iter a b c count n)
    (if (= count n) a
        (f-b-iter (+ a b c) (* 2 a) (* 3 (/ b 2)) (+ 1 count) n)))
  (f-b-iter 2 2 0 2 n))




사용자 삽입 이미지


이제 조금 익숙해지긴 했습니다만, 그래도 어렵긴 어렵군요. ㅋㅋ

신고
Posted by 이병준

소중한 의견, 감사합니다. ^^

  1. 어쩐지 이상하다 했습니다.OTL....
    저는 n 파라메터를 따로 만들었는데, 앞에서 배운 블록구조 안에 숨겨서 변수를 그대로 쓸 수 있다는 것을 깜박했습니다.
    좋은 정보 고맙습니다.^^

    2008.01.04 10:54 신고 [ ADDR : EDIT/ DEL : REPLY ]