happy coding

heap은 binary tree의 일종이다. HEAP 1. 최대 힙 >> 부모 노드는 자식 노드보다 작지만 않으면 된다. + 완전이진트리이다. 최대 트리(Max Tree)는 각 노드의 키(Key)값이 (자식 노드가 있다면) 그 자식의 키(Key)값보다 작지 않은(=크거나 같은) 트리이다. 최대 힙(Max Heap)은 최대 트리(Max Tree)이면서 완전 이진 트리(Complete Binary Tree)이다. 2. 최소 힙 >> 부모 노드는 자식 노드보다 크지만 않으면 된다. + 완전이진트리이다. 최소 트리(Min Tree)는 각 노드의 키(Key)값이 (자식 노드가 있다면) 그 자식의 키(Key)값보다 크지 않은(=작거나 같은) 트리이다. 최소 힙(Min Heap)은 최소 트리(Min Tree)이면서 ..

Algorithm specification 알고리즘은 유한한 일련의 명령을 해결하는 것이다. 알고리즘의 조건에는 1. 0개 이상의 입력 2. 적어도 1개의 출력 3. 모호하지 않은 명확성 4. 한정된 수의 단계 후에 종료되는 유한성 5. 프로그램과는 다른 ??? 이 있다. //Binary Search assumption sorted n (>=1) distinct integers stored in the array list return index i (if i, list[i] = searchnum) or -1 (otherwise) denote left and right left and right ends of the list to be searched initially, left = 0 and right ..

그래프 그래프(graph)란 연결되어 있는 객체간의 관계를 표현하는 자료 구조이다. 예시로는, 전기회로, 프로젝트 관리 그리고 지도에서 도시들의 연결 등이 있다. 그래프 이론(graph theory)은 그래프를 문제 해결의 도구로 이용하는 연구 분야를 의미한다. 트리 또한 그래프의 일종, 트리는 acyclic graph(사이클이 없는 그래프)이다. 그래프는 오일러에 의해 창안되었으며, 여기서 오일러 문제란 "모든 다리를 한 번만 건너서 처음 출발했던 장소로 돌아오는 문제" 이다. 문제의 핵심만을 표현하기 위해, 위치는 정점으로 다리는 간선으로 표기하였으며, 정점에 연결된 간선의 개수가 짝수이면 오일러 경로가 존재한다고 할 수 있다. 그래프는 V(정점(vertices)들의 집합)과 E(간선(edge)들의 ..

트리 트리(Tree)란 계층적인 구조를 나타내는 자료구조를 의미하고, 부모-자식 관계의 1개 이상의 노드들로 이루어진다. 서브트리와 루트노드가 있다. 사이클이 없는 그래프, 노드(node) : 트리의 구성요소 루트(root) : 부모가 없는 노드 서브트리(subtree) : 하나의 노드와 그 노드들의 자손들로 이루어진 트리 단말 노드(terminal node) : 자식이 없는 노드 비단말 노드(nonterminal node) : 적어도 하나의 자식을 가지는 노드 레벨(level) : 트리의 각 층의 번호 높이(height) : 트리의 최대 레벨 차수(degree) : 노드가 가지고 있는 자식 노드의 개수 이진 트리 이진 트리(binary tree)는 모든 노드가 2개의 서브 트리를 가지고 있는 트리이며 ..

큐란 스택과 마찬가지로 삽입과 삭제의 위치가 제한되어 있는 유한 순서 리스트이다. 큐의 뒤에서는 삽입만 하고, 앞에서는 삭제만 할 수 있는 구조이다. > 삽입한 순서대로 원소가 나열되어 가장 먼저 삽입한 원소는 맨 앞에 있다가 가장 먼저 삭제된다. > 선입선출구조 선형 큐 스택이 연탄이면, 큐는 한줄서기 > push. pop : enQueue. deQueue 모든 자료구조는 array(seq structure)와 linked list 로 이루어져 있다. 초기상태(공백 큐)는 front = rear = -1 이다. 삽입된 상태(enQueue(Q,A))에서는 rear가 A를 가리키고, enQueue(Q,B)에서는 rear가 B를 가리키는 상태가 된다. 원소를 삭제할 때(deQueue(Q))는 front를 A..

스택(stack) 논리적 개념으로는 linear list(ordered list) 에서 array와 linked list 가 있다. 이를 통해 stack 또는 queue를 구현한다. 연결리스트는 동적인 자료구조, 순차 접근 방식, O(n), 데이터의 접근과 탐색이 중요할 때 사용한다. 배열은 정적인 자료구조, 임의 접근 방식, O(1), 데이터의 추가와 삭제가 중요할 때 사용한다. 스택은 삽입과 삭제는 O(1)이고, 탐색은 O(n)이다. 큐 또한 같다. 스택이란, 접시를 쌓듯이 같은 크기의 자료를 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. 스택에 저장된 원소는 top으로 정한 곳에서만 접근이 가능하다. 여기서, top의 위치에서만 원소를 삽입하므로 먼저 삽입한 원소(가장 최근에 들어온 데이터)는 밑에..

연결 자료구조(Linked Data Structure) 연결 자료구조란, 자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조로, 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순가 연결되기 때문에 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다. 또한, 여러 개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현하기 때문에 크기 변경이 유연하고 더 효율적으로 메모리를 사용할 수 있다. 여기서 연결리스트란, 리스트를 연결 자료구조로 표현한 구조인데, 연결하는 방식에 따라 단순연결 리스트와 원형 -, 이중 - , 이중 원형 - 이 존재한다. 순차 자료구조의 문제점은 1. 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해 원소들을 이동시키는 추가적인 작업과 시간이 소요된다..

linked list 를 어떻게 c언어로 구현하는지 배열(array)은 구현이 간단하고 빠르지만 크기가 고정되고 중간에 삽입과 삭제가 어렵다. 연결리스트는 각각의 원소가 포인터를 사용하여 다음 번째 원소의 위치를 가리킨다. 데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들어서 쉽게 추가할 수 있지만,구현이 어렵고 오류가 나기 쉽고 포인터 연산을 많이 하기 때문에 느리다. 하지만 왜 쓰냐면, 배열의 단점을 완벽하게 커버하기 때문이다. 연결 리스트의 구조는 노드 = 데이터 필드 + 링크 필드 로 이루어져 있다. 여기서 첫 번째 노드를 가리키는 포인터를 헤드 포인터라고 한다. 자기 참조 구조체(self-referential structure)란 특별한 구조체로서 구성 멤버 중에 같은 타입의 구조체를 ..