SICP 1장 복습 체크리스트

일러두기

아래의 체크리스트에서 언급하는 모든 프로시저는 책을 보지 않고 짤 수 있을 정도로 숙달되어야 책을 제대로 읽었다고 할 수 있습니다. Dr.Racket을 열고 자신을 시험해보시기 바랍니다.

scheme의 기본 문법

• 전위표기식^{prefix notation}으로 프로시저를 작성하는 법을 설명할 수 있어야 합니다.
• define, cond, if, let의 사용에 완전히 익숙해져야 합니다.

컴파일러가 언어를 처리하는 법

• 컴파일러가 언어를 처리하는 두가지 방식인, 인자먼저 계산법과 정의대로 계산법의 정의를 각각 설명할 수 있어야 합니다.
• 또 각각의 방법의 차이가 두드러지는 예시를 들 수 있어야 합니다.

시간복잡도와 공간복잡도

• 프로세스의 자람차수 즉, 시간복잡도를 빅 세타 표기법으로 나타낼 수 있습니다.
• 복잡한 프로세스의 시간복잡도와 공간복잡도를 구할 수 있어야 합니다. (ex. change-count)

프로시저 설계 기법

• 람다식의 의미와 사용법을 정확히 알고 있어야 합니다.
• 프로시저와 프로세스의 차이를 설명할 수 있어야 합니다.
• 되도는 프로시저가 무엇인지 설명할 수 있고, 구현할 수 있어야 합니다.
• 되도는 프로세스와 반복하는 프로세스를 구현하는 기법에 완벽히 익숙해져야 합니다.
• expmod나 fast-exp처럼 시행 범위를 반씩 줄여서 자람차수를 $Θ(\log n)$으로 만드는 기법을 이해해야 합니다.
• 차수 높은 프로시저로 여러 복잡한 연산을 단순화할 수 있어야 합니다.

코드 구현 능력

아래의 프로시저들의 수학적인 의미를 이해하고, 책을 보지 않고도 똑같이 구현할 수 있어야 합니다.

1. 뉴턴법을 이용한 제곱근

;case 1
(define (sqrt x)
  (sqrt-iter 1.0 x))

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x)))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (improve guess x)
  (average guess (/ x guess)))

;case2
(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))

2. 팩토리얼

;recursion 
(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))
    
;iteration
(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

3. 피보나치 수열

;recursion
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

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

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

4. 거스름돈

(define (count-change amount)
  (cc amount 5))
  
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+
                (cc amount 
                    (- kinds-of-coins 1))
                (cc (- amount 
                       (first-denomination kinds-of-coins)) 
                    kinds-of-coins)))))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

5. 거듭제곱

;recursion
(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))
    
;iteration
(define (expt b n)
  (expt-iter b n 1))

(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                 (- counter 1)
                 (* b product))))

;Θ(log n) recursion
(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))  
    
;Θ(log n) iteration
(define (expt-iter b count product)
  (cond ((= count 0) product)
        ((even? count)
         (expt-iter (square b)
                    (/ count 2)
                    product))
        (else
         (expt-iter b
                    (- count 1)
                    (* b product)))))

6. 최대 공약수

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

7. 소수판별

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

(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 (prime? n)
  (= n (smallest-divisor n)))
  
;Fermat
(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #f)))

8. 수열의 덧셈

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

9. 이분법

(define (half-interval-method f a b)
  (let ((a-value (f a))
        (b-value (f b)))
    (cond ((and (negative? a-value) (positive? b-value))
           (search f a b))
          ((and (negative? b-value) (positive? a-value))
           (search f b a))
          (else
           (error "Values are not of opposite sign" a b)))))

(define (search f neg-point pos-point)
  (let ((mid-point (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
         mid-point
         (let ((test-value (f mid-point)))
           (cond ((positive? test-value)
                  (search f neg-point mid-point))
                 ((negative? test-value)
                  (search f mid-point pos-point))
                 (else mid-point))))))

(define (close-enough? x y)
  (< (abs (- x y)) 0.001))
  
(half-interval-method sin 2.0 4.0)
;π

10. 고정점

(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? next guess)
          next
          (try next))))
  (try first-guess))

11. 뉴턴 방법

(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) ((deriv g) x)))))

(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))

(define (sqrt x)
  (newtons-method (lambda (y) (- (square y) x))
                  1.0))

12. 기타 다시 풀어볼 문제들

• 연습문제 1.41