SW 마에스트로 멘토님의 추천으로 SICP 를 공부중이다. 책에서 사용하는 언어는 Scheme이라고 하는 Lisp의 dialect인데, 지금까지 배운 언어들과는 꽤 다르지만 재밌는 언어다.
연습문제 1.16
제곱 프로시저를 O(log n)의 시간 복잡도로 구현하되, 반복 프로시저로 만드는 문제이다.
반복 프로시저와 재귀 프로시저의 차이를 이 문제를 풀면서 좀 더 확실하게 깨달았다.
현재까지의 프로시저 진행 상태를 자기 자신을 호출할 때 넘겨주면 반복, 그렇지 않으면 재귀 프로시저이다.
다른 말로 하면, 프로시저 진행 상태를 변수에 저장하면 반복, 콜 스택에 저장하면 재귀 프로시저이다.
(define (even? n)
(= (remainder n 2) 0))
(define (iter-expt a b n)
(cond ((= n 1) (* a b))
((even? n) (iter-expt a
(square b)
(/ n 2)))
(else (iter-expt (* a b)
b
(- n 1)))))
; 위 프로시저에서 진행 상태를 변수 a 에 명시적으로 저장해서 사용하고 있다.
(iter-expt 1 2 10)
연습문제 1.17
곱셈 프로시저를 O(log n)의 시간 복잡도로, 재귀 프로시저로 구현하는 문제이다.
어렵지 않게 풀 수 있다.
(define (double n)
(* n 2))
(define (halve n)
(/ n 2))
(define (even? n)
(= 0 (remainder n 2)))
(define (fast-mult a b)
(cond ((= b 1) a)
((even? b) (fast-mult (double a) (halve b)))
(else (+ a (fast-mult a (- b 1))))))
(fast-mult 100 50)
연습문제 1.18
위의 곱셈 프로시저를 반복 프로시저로 구현하는 문제이다.
위에서 콜 스택에 저장 했던 프로시저 상태를 명시적으로 변수에 저장해 구현하면 된다.
(define (even? n)
(= 0 (remainder n 2)))
(define (double n)
(* 2 n))
(define (halve n)
(/ n 2))
(define (iter-mult n a b)
(cond ((= b 0) n)
((even? b) (iter-mult n (double a) (halve b)))
(else (iter-mult (+ n a) a (- b 1)))))
; 변수 n 에 진행 상태를 저장한다.
(iter-mult 0 100 50)
연습문제 1.19
지금까지 배운 것을 바탕으로, 피보나치 수를 구하는 프로시저를 O(log n) 시간복잡도로 구현하는 문제이다.
물론 그 공식을 직접 생각해내는 것은 아니고, 문제를 읽으면 피보나치 수열 구하는 점화식을 두번 연속해서 적용했을때의 수식을 구하는 방법을 알 수 있다.
이를 바탕으로 위와 같이 남은 계산 횟수가 짝수 일 때 횟수를 절반으로 줄일 수 있다. 실제 구현식은 중요한 게 아니므로 여기 적어놓지는 않겠다.