-
2017.06.21
[C] 탐색(Search)
탐색(Search) [탐색이란?] - 탐색(search)은 컴퓨터가 가장 많이 하는 작업 중의 하나임. - 탐색은 컴퓨터 프로그램에서 가장 많이 사용하는 작업임과 동시에 많은 시간이 요구되므로 탐색을 효율적으로 수행하는 것은 매우 중요함. - 탐색은 기본적으로 여러 개의 자료 중에서 원하는 자료를 찾는 작업. - 탐색을 위하여 사용되는 자료 구조는 배열, 연결 리스트, 트리, 그래프 등 매우 다양할 수 있음. - 탐색 중에서 가장 기초적인 방법은 배열을 사용하여 자료를 저장하고 찾는 것. - 그러나 탐색 성능을 향상하고자 한다면 이진 탐색 트리와 같은 더욱 진보된 방법으로 자료를 저장하고 탐색해야 함. - 탐색의 단위는 항목이며, 항목은 간단하게 숫자일 수도 있고, 아니면 구조체가 될 수도 있음. - 항..
-
2017.06.20
[C] 해싱(Hashing)
해싱(Hashing) [해싱이란?] - 대부분의 탐색 방법들은 탐색 키를 저장된 키 값과 반복적으로 비교함으로써 탐색하고자 하는 항목에 접근함. - 하지만 해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근함. - 해시 테이블(hash table) : 키 값의 연산에 의해 직접 접근이 가능한 구조 - 해싱(hashing) : 해시 테이블을 이용한 탐색 - 해싱은 일상생활에서의 정리 정돈으로 비유할 수 있음. - 키들의 비교에 의한 탐색 방법은 정렬이 안 되어 있으면 O(n)이고 정렬되어 있으면 O(log₂n). - 이 정도의 시간 복잡도가 허용되는 경우도 있는 반면, 어떤 경우는 더 빠른 탐색 방법이 필요함. - 해싱은 이론적으로는 O(1)의 시간 안..
-
2017.06.19
[C] 그래프(Graph)
그래프(Graph) [그래프란?] - 그래프(graph) : 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조. 예) 지도 - 지도를 그래프로 표시하면 하나의 도시에서 다른 도시로 갈 때 최단 거리 경로가 어떤 것인지를 알고리즘을 이용해 쉽게 찾을 수 있음. - 운영 체제에서 프로세스와 자원들이 어떻게 연관되는지를 그래프로 표현하게 되면 시스템의 효율이나 교착 상태 유무 등을 알아낼 수 있음. - 그래프는 많은 문제들을 표현할 수 있는 훌륭한 논리적 도구. - 선형 리스트나 트리의 구조로는 복잡한 문제들을 표현할 수 없음. - 그래프 구조는 인접 행렬이나 인접 리스트로 메모리 에 표현되고 처리될 수 있으므로 광범위한 분야의 다양한 문제들을 그래프로 표현하여 컴퓨터 프로그래밍에 의해 해결할 수 있..
-
2017.06.18
[C] 정렬(Sorting)
정렬(Sorting) - 정렬(sorting) : 물건을 크기순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것. - 정렬은 컴퓨터공학을 포함한 모든 과학 기술 분야에서 가장 기본적이고 중요한 알고리즘 중의 하나로 일상생활에서 많이 사용됨. - 정렬은 자료 탐색에 있어서 필수적임. - 일반적으로 정렬시켜야 될 대상은 레코드(record)라고 불림. - 레코드는 다시 필드(field)라고 하는, 더 작은 단위로 나누어짐. - 여러 필드 중에서 특별히 레코드와 레코드를 식별해주는 역할을 하는 필드를 키(key)라고 함. 레코드 { [필드][필드][필드][필드][필드][필드][필드][필드][필드][필드] 레코드 { [필드][필드][필드][필드][필드][필..
-
2017.06.17
[C] 우선순위 큐(Priority Queue)
우선순위 큐(Priority Queue) - 컴퓨터에 우선순위의 개념이 필요할 때가 있음. 예) 네트워크 패킷 중에서 네트워크 관리와 관련된 패킷은 다른 일반 패킷보다 우선순위를 가짐. 예) 운영 시스템에서도 시스템 프로세스는 응용 프로세스보다 우선순위를 가지게 됨. - 따라서 자료 구조에서도 이러한 우선순위를 지원하는 것이 필요함. - 우선순위 큐(priority queue) : 우선순위의 개념을 큐에 도입한 자료 구조. - 보통의 큐는 선입 선출(FIFO)의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 되지만, 우선순위 큐에서는 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가게 됨. - 스택에 들어 있는 데이터들은 우선순위가 없음. 단지 먼저 들어간 데이터가 가장 늦게 나옴...
-
2017.06.11
Comparison among FUNCALL and APPLY and REDUCE
;; Comparison CG-USER(38): (funcall #'+ 1 2 3)6CG-USER(39): (apply #'+ '(1 2 3))6CG-USER(40): (reduce #'+ '(1 2 3))6 Comparison among FUNCALL and APPLY and REDUCE.Keep in mind that you should write only numbers when you use FUNCALL with #'(arithmetic operator).
-
2017.06.08
Block's World
;;;; Block's World;; ;;;; Global Variables;; (defstruct blocks (name nil) (color nil) (ison 'table) (isunder nil)) (defvar *blocks*) ;;;; Main;; (defun start-world () (setf *blocks* nil)) (defun new-block (name color) (push (make-blocks :name name :color color) *blocks*)) (defun get-block (name) (dolist (x *blocks* nil) (if (equal name (blocks-name x)) (return x)))) (defun clear-top? (name) (if ..
-
2017.06.06
Destructive Operations
;; Destructive Operations ;; CG-USER(28): (setf x nil);; NIL;; CG-USER(29): (nconc x y);; (D E F);; CG-USER(30): x;; NIL;; CG-USER(31): y;; (D E F);; CG-USER(32): (setf X (nconc X Y));; (D E F);; CG-USER(33): y;; (D E F);; CG-USER(34): x;; (D E F) ;; CG-USER(14): (setf x '(a b c));; (A B C);; CG-USER(15): (setf y '(d e f));; (D E F);; CG-USER(16): (setf z (append x y));; (A B C D E F);; CG-USER(..
-
2017.06.01
Readable Code
-
2017.06.01
[C] 트리(Tree)
트리(Tree) - 선형 자료 구조(linear data structure) : 자료들이 직선과 같이 나열되어 있는 구조 (리스트, 스택, 큐 등) - 트리는 계층적인 구조(hierarchical structure) 또는 비선형 자료 구조(nonlinear data structure)를 가지고 있으며, 계층적인 자료를 표현하는 데 이용되는 자료 구조. - 인공 지능 문제에서도 트리가 사용되는데 대표적인 것으로 결정 트리(decision tree)가 있음. - 결정 트리는 인간의 의사 결정 구조를 표현하는 한 가지 방법. [트리에서 쓰이는 용어] - 노드(node) : 트리의 구성 요소 - 트리는 한 개 이상의 노드로 이루어진 유한 집합임. - 이들 중 하나의 노드는 루트(root) 노드라고 불리고, 나머..
