시냅스

주메모리의 관리, Main Memory memory에 Load된 program -> process 메모리는 바이트로 이뤄진 주소를 배열로 한다. PC(Programcounter) -> 주소 -> 명령어, 필요하면 더 데이터를 더 가져오거나 내보낼 수도 있다. 기본 하드웨어 Basic HardWare 메모리 CPU는 각 처리 코어에 내장된 레지스터와 메인 메모리에만 접근할 수 있다. 명령어와 데이터들은 CPU가 접근할 수 있는 레지스터와 메인 메모리에 있어야 한다. 캐시 CPU 코어에 내장된 레지스터에는 CPU가 빠르게 접근할 수 있다. 다만 메모리에 접근하는 속도는 상대적으로 느리다. CPU와 메모리 사이에 캐시라는 빠른 속도의 메모리를 추가하여 자주 접근하는 데이터를 캐시에 둠으로써 속도 차이 문제를..

이진 탐색 트리, Binary search tree 이진 탐색 트리는 각 노드에는 값이 있다. 값들은 전순서(임의의 원소를 비교할 수 있는 부분 순서 집합)가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지신 노드들로 이뤄진다. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이워진다. 이진 탐색 트리는 일반적으로 탐색에서 O(log n)으로 장점을 갖는다. 다만, 편향 트리로 이뤄져있다면 O(n)의 가능성이 있다. 이 경우 red black tree를 이용할 수 있다. 아래에서는 Linked list를 사용한 이진 탐색 트리의 구현을 살펴본다. 구현 생성 삽입 개별 node 삭제 Tree 삭제 생성 typedef struct BinSearchTreeNodeType..

힙 Heap 힙은 항상 완전 이진 트리 (위로부터 왼쪽 오른쪽 순서대로 쌓이는 것을 말한다.)의 형태를 지닌다. 부모의 값은 자식의 값보다 크거나(Max heap), 작아야(Min heap) 한다. 따라서 루트노드에는 항상 데이터 중 크거나 작은 값이 저장되어 있기 때문에 최대, 최소값 탐색에 O(1)이 걸린다. 데이터의 삽입과 삭제는 모두 O(log N)이 소요된다. 이러한 특성은 완전 이진 트리이며, 부모노드가 항상 크거나 작다는 확증에 기인한다. Max heap 구현 생성 삽입 root node 반환, Pop Heap 삭제 생성 typedef struct HeapNodeType { int key; } HeapNode; typedef struct HeapType { int maxElementCount..