노드의 차수 : 어떤 노드가 가지고 있는 자식 노드의 개수 전체 트리의 차수 : 트리가 가지고 있는 노드의 차수중에 가장 큰값 트리의 레벨 : 트리의 각층에 번호를 매기는 것, 루트의 레벨은 0또는 1이고 한층씩 내려갈 수록 1씩증가 트리의 높이 : 트리가 가지고 있는 최대레벨을 말한다. 이진트리의 성질 - N개의 노드를 가진 이진트리는 N-1개의 간선을 가진다. 높이가 h인 이진트리는 최소 h개의 노드를 가지며, 최대 2^(h+1)-1 개의 노드를 가진다.(루트의 레벨을 0이라 가정) - 노드의 개수가 1 이상인 이진트리에서 차수(분지수)가 i인 노드의 개수를 Ni라고 할때, N0 = N2 +1 이다. 증명 ) n = n0+n1+n2 (전체 노드의 개수는 차수가0인 노드와 1인노드와 2인 노드의 개수를..

1. 스택 - 선입 후출 구조 - 맨 처음에 들어간 원소를 top라고 지정한다. 1) 배열 ⓐ 구조체 선언 #define SIZE 1000 typedef struct { int key; // 다른필드 }element; element stack[SIZE]; ⓑ push int top = 0; void push(int* top_ptr, element item) { if (*top_ptr >= SIZE) { printf("스택이 다 찼습니다."); } stack[(*top_ptr)++] = item; } ⓒ pop void pop(int* top_ptr) { if (*top_ptr == 0) { printf("스택이 비어있습니다."); } stack[(*top_ptr)--]; } * push와 pop 모두 매..

1. DOTIMES 와 DOLIST 함수 1) DOTIMES - 리슾의 내장함수로서 반복문으로 사용된다. - 구조 (DOTIMES (i n 결과값) ...) ex) (DOTIMES (i 4 'end) (format t "~&I is ~S." i)) - 출력 화면 * 시작변수 값 0부터 시작하여 4회 반복한다는 의미 * format문(9Chpter 내용) (format t "입력값") = "입력값" (반환값으로 기본값 nil도 같이 출력) ~& : 줄의 맨 앞으로 가라 / ~% : 엔터 / ~S : 변수 지시어 2) DOLIST - 리스트안의 내용을 반복하는 함수 - 구조 (DOLIST (index-var 리스트 [결과 값(result-form)]) 반복할 내용) ex) 색깔 리스트를 입력받아 꽃의 색깔 ..

1. 변수(Variables) 1) 지역 변수 : 함수 내에서만 범위가 한정된다. 2) 전역 변수 : 전체 범위에서 사용가능한 변수 - setf : 변수를 정의 값 변경이 가능하다. 전역변수로 선언하려면 (seft *변수이름* 값)을 하면된다. ex) (setf vowels '(a e i o u)) - defconstant : 상수선언 (값변경 불가) - defvar : 전역변수 선언 변수이름을 *로 감싸야된다. 다시 함수선언하려고 하면 경고 뜸-> 값이 변경이 안됨 - defparameter : 전역변수 선언 다시 함수로 변수 선언하면 값이 변경이 된다. 경고는 뜸 2. Side Effects - main efftet는 값 자체를 되돌려주는 것. - side efftect는 함수마다 다름. ex) se..

1. EVAL 함수 - 리슾에서 심장의 역할을 하는 함수다. - evaluate의 약자로 문자열이 코드라고 가정하고 평가해서 실행한다는 의미 ex) 리슾에서 (+ 3 5) 를 입력하면 8이 나오는 것처럼 (+ 3 5)는 5로 평가된다는 의미 1) 규칙 - Self-evaluating : 숫자 , 그리고 심볼, t와 nil은 자기자신을 반환한다. ex) 23을 입력하면 23이 출력 - 리스트 eval 규칙 ⓐ 첫번째 요소는 함수이름이어야 한다. ⓑ 남은 요소들은 함수의 매개변수여야 한다. ex) (equal (+ 7 5) (* 2 8)) 2. Defun 함수 - 매크로 함수이다. - 함수이름, 매개변수, 함수 바디로 이루어져 있다. 1) 규칙 - Self-evaluating : 숫자 , 그리고 심볼, t와..

1. 조건문 - Lisp에서 조건문은 IF나 COND 를 이용하여 나타낼 수 있다. - 조건문의 결과는 T와 FALSE(NIL) 두가지로 나온다 1) If - 사용방법 (IF ( 조건문 ) '참일때 결과값 '거짓일때 결과값 ) ex) (if (oddp 1) 'odd 'even) = odd 2) COND - 사용방법 (COND ((조건문 1) '조건문1이 참일때 결과값) ((조건문 2) '조건문2가 참일때 결과값) ... (t '조건문들이 참이 아닐 때 결과값)) ex) 두 수를 입력받아 비교하는 함수 (defun compare (x y) (cond ((equal x y) 'number_same) ((< x y) 'first_is_smaller) (t 'first_is_bigger))) 3) AND와 OR..

1. 리스트 - 리습(Lisp)은 List Processor의 약자이다. - 리스트의 표현은 괄호안에 나타낸다. ex) (red green blue) - 리스트는 Cons cells(콘 셀)의 연결로 이루어져 있다. - 이러한 콘셀은 2개의 포인터로 연결되어 있는데 하나는 데이터, 하나는 다음 요소를 가르킨다 * 연결리스트와 유사하다 1) 리스트의 길이 - 리스트의 길이는 요소의 개수와 같다. ex) (a b c d) : 4개 (a (b c) d) : 3개(Nested list라 불린다- 리스트안 리스트) - NIL : 빈 리스트 2) 리스트의 동등성 ex) (A (B C) D) 와 (A B (C D)) 는 같은 리스트일까? 답 : x (괄호 안 요소가 같아야 함) 3) FIRST, SECOND, THI..

1. 동적 메모리 할당 - 일반적인 배열은 크기가 고정되어있다. - 이러한 고정된 크기 때문에 배열이 남을 수도, 부족할 수도 있다. - 일반적인 배열의 단점을 보완한 것이 '동적 메모리 할당' 이다. 1) 의미 : 메모리를 운영체제로부터 할당받아서 사용하고, 사용이 끝나면 반납하는 기능 - 동적 메모리가 할당되는 공간을 히프(heap)라고 한다. * 히프는 운영체제가 사용되지 않는 메모리 공간을 모아놓은 곳이다. 2) 선언 방법 int *p; p = (int *)malloc(sizeof(int)); //동적 메모리 할당 *p = 1000; //동적 메모리 사용 free(p); //동적 메모리 반납 - malloc() 함수는 size 바이트 만큼 메모리 블록을 할당한다. 따라서 sizeof(int) = ..

- 외부 변수의 값을 변경할 때 포인터를 매개변수로 사용하면 편리하다 - 그 예로 외부변수 2개의 값을 서로 바꾸는 swap() 함수를 구현하는 방법이 있다. void swap(int *px *py) { int tmp; tmp = *px; *px = *py; *py = tmp; } int main(){ int x = 3; int y = 6; printf("swap 전 : %d, %d" x, y); swap(&x, &y); //변수의 주소를 집어넣는다. printf("swap 후 : %d, %d" x, y); return 0; }