전체 글 (34) 썸네일형 리스트형 09. 자료구조론 - Heap (Priority Queue) Heap (Priority Queue) 힙 또는 우선순위 큐는 요소가 지워질 때 먼저 들어온 것이 먼저 나가는 것이 아니라 우선순위가 높은 요소가 더 먼저 나가는 자료구조입니다. 따라서 heap에서는 insert와 pop 연산을 지원하는데, 여기서 pop은 deleteMin이나 deleteMax같은 연산이 됩니다 . 우선순위 큐는 주로 스케줄링을 할 때 사용됩니다. Heap에는 min heap과 max heap이 있으며 둘의 차이는 다음과 같습니다. min heap : 각 부모노드의 값은 자식 노드의 값들보다 항상 작거나 같다. (작은 값이 우선순위가 높을 때 사용) max heap : 각 부모노드의 값은 자식 노드의 값들보다 항상 크거나 같다. (큰 값이 우선순위가 높을 때 사용) 따라서 루트노드는 m.. 08. 자료구조론 - Disjoint Set Disjoint Set (서로소 집합) Disjoint set은 서로 공통된 요소를 가지지 않고 분리된 집합들을 관리하기 위한 자료구조입니다. Disjoint set 내의 집합 $S_i$, $S_j$ 에 대해서 $i != j$ 라면 $S_i$와 $S_j$ 에 공통으로 존재하는 요소는 없습니다. Disjoint set에서 수행할 수 있는 기본적인 연산에는 Union, Find가 있습니다. Union은 두 서로소 집합을 합치는 연산이고, Find는 원하는 요소가 어떤 서로소 집합에 있는지 찾는 연산입니다. Disjoint set은 거꾸로된 트리들을 통해 구성할 수 있습니다. 일반적인 트리는 부모가 자식을 가리키는 방향이라면, Disjoint set의 집합 하나를 이루는 트리는 자식이 부모를 가리키는 방향으로.. 07. 자료구조론 - AVL Tree AVL (Adelson-Velskii and Landis) Tree AVL트리는 Binary search tree 의 일종입니다. 06. 자료구조론 - 이진탐색트리 (Binary Search Tree) 이진탐색트리 (BST) 이진탐색트리는 이진트리의 일종으로, 트리의 노드들을 일정한 기준으로 정렬해놓아서 트리 내에서 원하는 노드를 쉽게 찾을 수 있도록 한 트리입니다. 이진탐색트리는 다음 coldyun.tistory.com 일반적인 그냥 이진탐색트리는 랜덤한 값을 insert, delete할 경우 운이 나쁘면 치우친 트리가 생성될 수도 있습니다. 예를 들어 위와 같이 {1, 2, 3, 4}라는 값을 이진탐색트리에 넣는 경우, 이진탐색트리는 들어온 순서대로 알맞은 위치에 leaf노드로 해당 값을 삽입하기 때.. 06. 자료구조론 - 이진탐색트리 (Binary Search Tree) 이진탐색트리 (BST) 이진탐색트리는 이진트리의 일종으로, 트리의 노드들을 일정한 기준으로 정렬해놓아서 트리 내에서 원하는 노드를 쉽게 찾을 수 있도록 한 트리입니다. 이진탐색트리는 다음과 같은 특징을 갖습니다. 트리 내의 모든 노드X에 대해서 1. X의 왼쪽 subtree에 있는 모든 값들은 X보다 작고, 2. X의 오른쪽 subtree에 있는 모든 값들은 X보다 크다. 3. 트리 내의 모든 노드의 값은 중복되지 않는다. 따라서 이진탐색트리에서 어떤 subtree를 떼어내더라도 그또한 이진탐색트리가 됩니다. 이진탐색트리에서 탐색을 빠르게 할 수 있다고 하였는데, 이에 앞서 linear array에서의 탐색에 대해 알아보겠습니다. 순차탐색 : 일반배열에 값을 정렬하지 않고 그냥 저장해놓고, 원하는 값을 .. 05. 자료구조론 - 트리 (Tree) 트리 (Tree) 트리는 cycle없이 간선(edge)들로 연결된 노드들의 집합입니다. 트리에 cycle이 존재한다는 것은 특정 노드에서 출발하여 한번 지난 간선을 다시 방문하지 않고 처음 출발한 노드로 돌아올 수 있는 경로가 존재한다는 것입니다. 만약 간선으로 연결된 노드들의 집합에서 cycle이 존재한다면 그것은 트리가 아닌 그래프(graph)이고, 따라서 트리는 그래프의 한 종류가 됩니다. 트리의 최상단 노드는 root 노드입니다. 특정 노드의 하위에 달린 모든 노드들은 해당 노드의 child가 되고, 해당 루트 노드는 child 노드들의 parent가 됩니다. 그리고 특정 노드의 child노드들은 서로의 silbling이 됩니다. 특정 노드의 degree는 해당 노드의 child의 수이며, 전체 .. 04. 자료구조론 - 스택, 큐 (Stack, Queue) 스택 (Stack) 스택은 순서가 있는 리스트의 한 종류입니다. 그리고 리스트 아이템의 삽입과 삭제가 모두 리스트의 한쪽에서 일어납니다. 스택에서 수행할 수 있는 연산은 Push, Pop, Top 이 있습니다. 스택에서 삽입은 push, 삭제는 pop이 됩니다. 위와 같이 스택에 X를 push하면 무조건 리스트의 맨 위에 쌓이게되고, pop을 하면 맨 위에 있는 아이템이 리스트에서 제거됩니다. 그리고 top 연산자는 리스트 맨 위의 아이템을 리턴하지만, 해당 아이템을 리스트에서 제거하지는 않습니다. 스택은 일반적인 배열을 통해 구현할 수도 있고, 앞선 게시물의 linked list를 이용하여 구현할 수도 있습니다. Array 를 이용한 Stack 구현 typedef struct _Stack { int c.. 03. 자료구조론 - Linked List List 리스트는 여러 요소들의 순서가 있는 sequence 입니다. 리스트에서는 요소를 delete, find, insert 하는 등의 operation을 수행할 수 있어야하고, 이러한 리스트를 구현하는 방법에는 두가지가 있습니다. 1. 배열로 List 구현 첫번째로 array를 이용하여 리스트를 구현할 수 있습니다. 배열로 구현한 리스트에서 insert를 수행하려면 위와 같이 X가 들어가려는 위치의 뒤쪽 요소들을 모두 뒤로 한 칸 씩 민 후, 빈 자리에 X를 넣어주어야합니다. 동일하게 delete를 수행할 때에도, X를 제거한 후 뒤쪽 요소들을 한 칸 씩 앞으로 당겨주어야 합니다. 따라서 이러한 배열로 만든 리스트는 리스트의 중간에 insert나 delete를 수행하기 어렵다는 단점이 있습니다. 이 .. 02. 자료구조론 Intro (Performance Evaluation) Performance Analysis 효율적인 알고리즘은 알고리즘을 수행하여 결과를 도출해낼 때까지 걸리는 시간이 짧고, 컴퓨터의 메모리를 적게 사용하는 알고리즘입니다. 두가지 복잡도를 통해 알고리즘의 성능을 분석할 수 있으며, 이러한 성능분석은 하드웨어에 independent 하게 수행됩니다. 시간복잡도 (time complexity) : 알고리즘이 종료될때까지 필요한 시간의 양이며, 이때 절대적인 시간이 아니라 알고리즘이 수행되는데 필요한 연산의 개수를 이용해 측정됩니다. 공간복잡도 (space complexity) : 알고리즘이 종료될때까지 필요한 메모리의 양을 나타냅니다. 공간 복잡도 (Space Complexity) 1) C (Fixed space requirements) : 프로그램의 입출력의.. 이전 1 2 3 4 5 다음
