자바스크립트로 배우는 SICP - 01
다 필기(?)하려했더니 10페이지도 못가서 지친다.
번역서라 더 그런 것 같다.
그래서 이 책은 그냥 기억해야 할 것 같은 내용들만 간단히 적기로 했다.
expression은 표현식이다.
수학에서 수식 안에 수식을 중첩하는 것처럼 연산자 조합도 중첩할 수 있다.
즉 연산자 조합 자체를 다른 연산자 조합의 피연산자로 사용할 수 있다.
예: (3 * 5) + (10 - 6)
연산 순서의 혼동을 피하기 위해 소괄호로 연산자 조합들을 묶을 수 있다.
소괄호를 생략하면 자바스크립트는 통상적인 관례에 따라 연산 순서를 결정한다.
즉 곱셈과 나눗셈을 덧셈과 뺄셈보다 먼저 처리한다.
예를 들어 다음은
3 * 5 + 10 / 2
다음에 해당한다.
(3 * 5) + (10 / 2)
이런 관례를 일컬어 *와 /가 연산자 +와 -보다 우선순위(precedence)가 높다고 말한다.
일련의 덧셈과 뺄셈들은 왼쪽에서부터 오른쪽으로 평가(evaluation)되며, 일련의 곱셈과 나눗셈 또한 마찬가지다
따라서 다음은
1 - 5 / 2 * 4 + 3;
다음에 해당한다.
(1 - ((5 / 2) * 4)) + 3
이런 관례를 일컬어 연산자 +, -, *, /가 왼쪽 결합(left-associative)이라고 말한다.
expression1 && expression2
논리곱
expression1 ? expression2 : false의 문법적 설탕
expression1 || expression2
논리합
expression1 ? true : expression2의 문법적 설탕
연습문제
자바스크립트에서 다음 결과는 무엇일까?
const a = 0
const b = 4
b > a && b < a * b ? b : a
내가 생각한 답 : false
왜냐하면 b < a * b는 거짓이기 때문에
b > a && b < a * b ? b : a
는
b > a && a로 축약된다.
b > a 는 참이지만 a는 0이다.
따라서 false
눈 돌아갈 뻔했다.
연습문제 2
다음 수식을 자바스크립트 표현식으로 옮겨라
(5 + 4 + (2 - (3 - (6 + 4/5)))) / 3 * (6 - 2) * (2 - 7)
근데 난 c++로 하겠다.
자바스크립트 모르기 때문이다.
내일부터 공부할거다.
내 풀이
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | #include <iostream> float plus(float a, float b) { return a + b; } float minus(float a, float b) { return a - b; } int main() { float sum1 = plus(5 + 4, minus(2, minus(3, plus(6, static_cast<float>(4) / 5)))); float sum2 = 3 * (6 - 2) * (2 - 7); printf("%f", sum1 / sum2); } | cs |
찍었는데 맞았다.
연습문제 1-3
세 개의 수를 받고 셋 중 가장 작은 것을 제외한 두 수의 제곱들을 합한 결과를 돌려주는 함수를 구현하라
풀이
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #include <iostream> int func(int a, int b, int c) { return a * a + b * b + c * c - ( a > b ? (c < b&& c < a) ? c * c : b * b : (c < b&& c < a) ? c * c : a * a ); } int main() { printf("%d", func(1, 2, 3)); } | cs |
어떻게 고쳐도 계속 4로 나와서 한참 고쳤다.
삼항연산자에 괄호를 씌워주지 않았기 때문.
해석기라고 불러도 되는지 모르겠다만 하여튼 해석기는 연산할 때 제일 왼쪽의 숫자부터 평가한다.
즉 이건
return a * a + b * b + c * c -
a > b
?
(c < b&& c < a) ?
c * c : b * b
:
(c < b&& c < a) ?
c * c : a * a;
이거랑 똑같은 의미였을 것
return (a * a + b * b + c * c - a > b)
?
(c < b&& c < a) ?
c * c : b * b
:
(c < b&& c < a) ?
c * c : a * a;
이 문제를 풀며 최솟값 찾는 알고리즘에 대해서 생각해보게 되었다.
a가 최솟값이라고 가정하자.
그러면 a < n은 참일 수밖에 없다.
반대로 생각하면 n1 < n2가 참이 나오는 n2는 무조건 최솟값이 아니라는 것.
내 생각이지만 최솟값을 구하는 알고리즘을 이렇게 짤 수 있는 것 같다.
- 집합의 모든 원소들에 대해 < 연산을 한다.
- < 연산에서 참이 나오는 원소들은 모두 배제한다.
- 나머지 원소들에 이것을 반복한다.
이런 식으로 최솟값을 구할 수 있을 것 같다.
굳이 이걸 말로 설명해놓는 이유는 기초적인 알고리즘임에도 불구하고 다시 하려고 할 때마다 계속 리트라이하기 때문이다.
연습문제 1.4
다음 함수의 작동 방식을 서술하라
function plus(a, b) { return a + b; }
function minus(a, b) { return a - b; }
function a_plus_abs_b(a, b) {
return (b >= 0 ? plus : minus)(a, b);
}
대충 plus minus 중 하나로 평가된 다음 호출된다는 내용인 것 같다.
모르겠다. 답지찾아봐야겠다.
이 책은 따지자면 취미이기 때문에 꼼꼼히 안할 것이다.
연습문제 1.5
뱃 빈디들은 주어진 해석기가 인수 우선 평가를 사용하는지 정상 순서 평가를 사용하는지 파악하는 방법을 고안했다.
이를 위해 밴은 다음 두 함수를 선언했다.
이제 다음과 같은 문장을 평가하면 해석기의 평가 방식을 파악할 수 있다.
test(0, p());
해석기가 인수 우선 평가를 사용할 때와 정상 우선 평가를 사용할 때 이 문장이 어떤 식으로 평가되는지를 각각 서술하라
내가 생각한 답:
정상 우선 평가는 모든 표현식들을 병합정렬에서 분할하고 정복하는 것마냥 완전히 전개한 후 차근차근 평가하는 거고
인수 우선 평가는 반대니까
정상 우선 평가를 할 때는 무한루프에 빠질 것이고
인수 우선 평가를 할 때는 0이 출력될 것 같다.
답지 찾아본다.
예제: 뉴턴 방식으로 제곱근 구하기
수학 함수와 컴퓨터 함수의 주요한 차이점이 있다.
컴퓨터 함수들은 효과적(effective)이어야 한다는 것.
이 점을 보여주는 예로 제곱근을 구하는 문제를 생각해보자.
제곱근은 다음과 같이 정의할 수 있다.
루트x = y>=0이고 y^2 = x라는 조건을 충족하는 y
이 정의는 완벽하다.
이제 프로그램으로 옮겨보자.
function sqrt(x) {
return y >= 0 && square(y) == x라는 조건을 충족하는 y
}
제곱근을 어떻게 구하면 되는지 더 궁금해질 뿐이다.
수학 함수와 컴퓨터 함수의 이러한 차이점은 사물의 성질(property: 속성)을 서술하는 것과 뭔가를 하는 방법을 서술하는 것의 차이를 반영한다.
이를 선언적 지식declarative knowledge와 명령적 지식imperative knowledge의 구분이라고 말하기도 한다.
수학에서는 주로 선언적 서술(이것은 무엇인가?)에 관심을 두지만 컴퓨터 과학에서는 주로 명령적 서술(어떻게 하는가?) 에 관심을 둔다.
제곱근을 계산하는 데에 흔히 쓰이는 방법은 뉴턴 방법을 이용해서 제곱근의 근삿값을 거듭 개선해나가는 것이다.
뉴턴 방법에서는 먼저 수 x의 제곱근이 될만한 y의 값을 추측하고, y와 x/y의 평균으로 더 나은 추측값을 구하는 과정을 반복한다.
다음은 뉴턴 방법의 예
| 추측값 | 몫 | 평균 |
| 1 | 2/1 = 2 | (2+1)/2 = 1.5 |
| 1.5 | 2/1.5 = 1.3333 | (1.1333 + 1.5)/2 = 1.4167 |
| 1.4167 | 2/1.4167 = 1.4118 | (1.4167 + 1.4118) / 2 = 1.4142 |
| 1.4142 | .... |
이 과정을 반복하면 추측값이 실제 제곱근에 점점 더 가까워진다.
추측값과 몫의 평균을 다음 추측값으로 하면 몫에 점점 더 가까워진다는 것 같다.
이를 자바스크립트(나는 c++)로 정식화formulation해보겠다. 책에 있는 예제이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include<iostream> #include<math.h> double square(double par) { return par * par; } double average(double a, double b) { return (a + b) / 2; } double improve(double guess, double x) { return average(guess, x / guess); } bool is_good_enough(double guess, double x) { return abs(square(guess) - x) < 0.001; } double sqrt_iter(double guess, double x) { return is_good_enough(guess, x) ? guess : sqrt_iter(improve(guess, x), x); } double sqrt(int x) { return sqrt_iter(1, x); } int main() { std::cout << sqrt(9) << std::endl; } | cs |
improve 함수는 추측값의 정밀도를 상승시킨다는 의미의 함수라고 한다.
연습문제 1. 6
문자 ?와 :가 관여하는 조건부 표현식 문법이 마음에 들지 않은 알리사 P. 해커는 "그냥 조건부 표현식처럼 작동하는 보통의 조건부 함수를 선언해서 사용하면 안 될까?"라고 물었다.
알리사의 동료 에바 루 에이터는 실제로 그런 함수를 만드는 것이 가능하다고 주장하고, 다음과 같은 conditional 함수를 선언했다.
1 2 3 | function conditional(predicate, then_clause, else_clause) { return predicate ? then_clause : else_clause; } | cs |
그러고는 아래와 같이 이 함수의 사용법을 알리사에게 시연했다.
1 2 3 4 5 | conditional(2 === 3, 0, 5); 5 conditional(1 === 1, 0, 5); 0 | cs |
이를 반긴 알리사는 conditional을 이용해서 다음과 같은 제곱근 계산 함수를 작성했다.
1 2 3 4 5 6 | function sqrt_iter(guess, x) { return conditional(is_good_enough(guess, x), guess, sqrt_iter(improve(guess, x), x)); } | cs |
이 함수로 제곱근을 계산하면 어떤 일이 생기는지 설명하라.
풀이)
이 코드에서 sqrt_iter()은 술어(조건)에 영향받지 않고 실행된다
따라서 conditional 내부로는 절대 진입을 하지 않고 무한 재귀를 돌게 된다
연습문제 1.7은 일단 패스.. 피곤하다. 더 좋은 is_good_enough를 구현하란다. 시간남을 때 풀거나 답지나 찾아봐야겠다
연습문제 1.8
세제곱근을 위한 뉴턴 방법에서는, y가 x의 세제곱근을 근사하는 값이라고 할 때 다음 공식으로 더 나은 근삿값을 구한다.
(x/y^2 + 2y) / 3
이 공식을 이용해서 제곱근 함수와 비슷한 형태의 세제곱근 함수를 구현하라.
풀이
머리 안돌아가서 무지성으로 했다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | #include<iostream> #include<math.h> double square(double par) { return par * par; } double _3_square(double par) { return par * par * par; } double divide_by_3(double par) { return par / 3; } double improve(double guess, double x) { return divide_by_3( x / square(guess) + 2 * guess ); } bool is_good_enough(double guess, double x) { return abs(_3_square(guess) - x) < 0.001; } double sqrt_iter(double guess, double x) { return is_good_enough(guess, x) ? guess : sqrt_iter(improve(guess, x), x); } double sqrt(int x) { return sqrt_iter(1, x); } int main() { std::cout << sqrt(9) << std::endl; } | cs |
그랬더니 맞았다.
구글에 검색해보니 9의 세제곱근이 2.08쯤 된다.
그리고 내 프로그램은 2.09로 출력
블랙박스 추상으로서의 함수
재귀적 반복
이런 연산을 수행하려면 해석기는 나중에 수행할 연산들을 기억해야 한다.
n!을 계산할 때 deffered operation chain(지연된 곱셈 연산들의 연쇄) 은 선형으로 비례한다.
그래서 이런 재귀적 과정을 선형 재귀적 과정이라고 부른다.
지연된 연산들의 사슬을 특징으로 하는 과정
두 과정의 차이점을 다른 방식으로 살펴볼 수도 있다.
반복적 과정에서 상태 변수들은 임의의 시점에서 과정의 상태를 완벽하게 서술한다.
특정 단계를 마친 후 해석기를 멈추었다고 할 때, 상태 변수 세 개만 기억해두면 언제라도 멈춘 지점부터 과정을 진행할 수 있다.
그러나 재귀적 과정에서는 그럴 수 없다.
재귀적 과정에서는 해석기가 관리하며 상태 변수들에는 들어있지 않은 어떤 숨겨진 정보가 존재한다
그 정보는 deffered operation chain을 처리할 때 과정이 현재 어디에 있는지를 나타낸다.
chain이 길수록 해석기는 더 많은 정보를 관리해야 한다.
반복과 재귀를 비교할 때는 재귀적 과정이라는 개념을 재귀 함수라는 개념과 혼동하지 말아야 한다.
함수가 재귀적이라는 것은 함수 선언에서 함수가 함수 자신을 참조한다는 구문 상의 사실을 말한다.
그러나 어떤 과정이 재귀적이라는 것은 그 과정이 어떤 식으로 전개되는가에 관한 것이지, 함수가 어떤 구문으로 작성되었는가에 관한 것이 아니다.
과정과 함수의 구분이 헷갈리는 이유 중 하나는 흔히 쓰이는 프로그래밍 언어(C, 자바, 파이썬 등)대부분의 함수 호출 구현이, 비록 재귀적 함수가 반복적 과정을 서술한다고 해도 그 함수가 소비하는 메모리는 호출 횟수에 비례하도록 설계되었다는 점이다.
그러다보니 그런 언어들에서는 반복적 과정을 do, repeat, until, for, while 같은 특별한 루프 구조로만 서술할 수 있다.
'
제5장에서 살펴볼 자바스크립트 구현에는 그런 결함이 없다.
그 구현은 반복적 과정을 고정된 크기의 공간에서 실행한다.
이는 그 반복적 과정이 재귀적 함수로 서술된다고 해도 마찬가지다.
이런 성질을 가진 구현을 가리켜 꼬리재귀적(tail-recursive)구현이라고 부른다.
꼬리 재귀적 구현에서는 반복을 통상적인 호출 메커니즘으로 표현할 수 있으므로, 특별한 반복 구조는 오직 편의 구문(문법적 설탕)으로만 쓰일 뿐이다.
꼬리재귀가 무엇일까 찾아봤다.
꼬리 재귀는 '재귀 호출이 끝나면 아무 일도 하지 않고 결과만 바로 반환되도록 하는' 방법이다. 이 방식을 사용하면 이전 함수의 상태를 유지하지도 않고 추가 연산을 하지도 않아서 스택이 넘쳐나는 문제를 해결할 수 있게 된다.
윗그림의 함수를 살펴보며 스택에 어떻게 쌓이고 풀릴지 계산을 하고 어색함을 느꼈다.
분명 return product가 지연적으로 일어날텐데 그것은 deffered operation으로 쳐주지 않는 것일까?
그러나 꼬리 재귀에 대해서 찾아보고 의문이 풀렸다.
c++에서도 위와 같이 하면 꼬리재귀 지원하는 컴파일러에서는 꼬리재귀를 시켜준다고 한다.
연습문제 1.9
다음 두 함수는 주어진 인자를 1 증가시키는 함수 inc와 1 감소시키는 함수 dec를 이용해서 두 양의 정수의 덧셈을 구현한다.
1 2 3 4 5 6 7 8 9 | function plus(a, b) { return a === 0 ? b : inc(plus(dec(a),b)); } function plus(a, b) { return a === 0 ? b : plus(dec(a), inc(b)); } | cs |
plus(4, 5); 를 평가할 때 각 함수가 생성하는 과정을 치환 모형으로 표현하라.
이 과정들은 반복적인가, 아니면 재귀적인가?
풀이)
재귀적인가 반복적인가 구별할 수 있는 방법은
연산이 위의 그림처럼 쌓였을 때 남은 것이 return 구문밖에 없느냐
아니면 다른 연산도 남아있느냐일 것 같다.
생각해보았는데
inc(plus(dec(a), b)); 이건 plus 호출들이 끝난 후에도 inc 함수를 계산할 수 있어야 한다.
그런데 plus(dec(a), inc(b)); 정해진 값까지 감소, 증가만 시키다가 마지막에 남는 것은 return 구문 뿐이다.
연습문제 1.10
다음 함수는 아커만(리바이..?) 함수(Ackermann's function) 라고 부르는 수학 함수를 계산한다.
1 2 3 4 5 6 7 8 9 | function A(x, y) { return y === 0 ? 0 : x === 0 ? 2 * y : y === 1 ? 2 : A(x - 1, A(x, y - 1)); } | cs |
다음 문장들은 각각 어떤 값으로 평가되는가?
1 2 3 | A(1, 10); A(2, 4); A(3, 3); | cs |
1시간 30분동안 멍때리면서 낙서해보았지만 못풀었다.
나중에 해야겠다.
백준 풀다 보면 되지 않을까(??)
트리 재귀tree recursion
흔히 볼 수 있는 또다른 계산 패턴으로 tree recursion이 있다.
트리 재귀 패턴의 대표적인 예로는 피보나치 수가 있다.
계산이 매우 많이 중복되기 때문에 tree recursion으로 계산하기에 나쁘다.
그렇다고 tree recursion이 쓸모가 없다는 결론을 내려서는 안된다.
수치가 아니라 위계 구조로 된 데이터를 다루는 과정에서는 tree recursion이 강력하고 자연스럽다.
그리고 수치 연산에서도 tree recursion이 프로그램의 이해와 설계에 도움이 되기도 한다.
예를 들어 tree recursion으로 옮긴 피보나치 수(그냥 재귀함수로 옮긴 거)는 수학적 정의를 그대로 옮긴 것이라는 점에서 좀 더 직관적이다.
예제:잔돈 만들기
50센트, 25센트, 10센트, 5센트, 1센트 동전들로 1달러 만큼의 잔돈을 만드는 방법의 수를 구하는 경우는 총 몇 가지나 될까?
이 문제는 재귀함수로 간단히 풀 수 있다.
주어진 금액을 만드는 전체 방법의 수는 제 1종 동전을 전혀 사용하지 않는 방법의 수에 제 1종 동전을 사용하는 방법의 수를 더한 것과 같다.
단 완결적인 알고리즘이 되려면 다음과 같은 degenerate case(퇴화 사례)들도 정의해두어야 한다.
- 만일 a가 정확히 0이면 잔돈을 만드는 방법은 단 한 가지이다.
- 만일 a가 0보다 작으면 잔돈을 만드는 방법은 0가지이다.
- 만일 n이 0이면 잔돈을 만드는 방법은 0가지이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | function count_change(amount) { return cc(amount, 5); } function cc(amount, kinds_of_coins) { return amount === 0 ? 1 : amount < 0 || kinds_of_coins === 0 ? 0 : cc(amount, kinds_of_coins - 1) + cc(amount - first_denomination(kinds_of_coins), kinds_of_coins); } function first_denomination(kinds_of_coins) { return 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 : 0; } | cs |
쉬운 거라는데 이해가 될 듯 말 듯 하다.
그러니까. 현재 금액의 경우의 수를 cc(amount, kinds_of_coins - 1)로 먼저 계산해준다.
그리고 금액에서 1종 동전을 뺀 나머지 경우의 수를 cc(amount - first_denomination(kinds_of_coins), kinds_of_coins)로 계산해준다.
그 둘을 더한다.
한국말로 설명하니까 이해가 된다.
내 머릿속에서 트리를 펼치지 말고 단순하게 생각해야겠다.
연습문제.
만일 n < 3이면 f(n) = n이고 만일 n >= 3이면 f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)으로 정의되는 함수 f가 있다.
재귀적 과정으로 f를 계산하는 자바스크립트 함수를 작성하라.
반복적 과정으로 f를 계산하는 자바스크립트 함수를 작성하라.
풀이
반복적 과정이란 함수 호출이 다 끝난 후 return 밖에 남지 않는 것을 의미한다.
이건 내일 풀어야겠다.
음 서점에서 보고 내용이 흥미롭길래 샀는데
어찌 가면 갈수록 기하급수적으로 어려워진다.
너무 어려운 문제는 적당히 넘어가고 나중에 푸는 걸로 기억해놔야겠다.
나중에 보면 자료구조서도 아니고 RB 트리 허프먼부호화트리 만들고 하던데
코테에 도움이 될지도..? 모르겠다.
물론 읽을 수만 있다면 말이다.
이 책은 언제까지 다 끝내겠다 하는 것은 너무 요원해보이니 못하겠고
하루에 1시간, 그날 기분따라 더하고 싶으면 30분 추가해서 하려고 한다.
문제는 대충 풀고 넘어가도 개념을 읽기만 해도 유익한 책일 것 같다.