자료구조 & 알고리즘10 [6] Heap 이 글에서는 힙 자료구조에 대해서 알아보도록 하겠습니다. Heap은 최댓값 및 최솟값을 빠르게 찾아내기 위해 고안되었고 완전이진트리를 기본으로 한 자료구조입니다. 우선 완전 이진트리 (complete binary tree)의 속성을 모두 충족합니다. 완전 이진트리란 트리의 왼쪽부터 비는 곳 없이 채워져 있게 됩니다. 위 이미지에서 complete 에 해당하는 구조가 완전 이진트리인데요 (물론 Perfect Binary Tree도 complete에 포함됩니다) 왼쪽부터 노드가 채워지고 중간에 비는 구조가 없는 것을 확인할 수 있습니다. 이런 완전이진 트리의 특성에 하나의 제약 조건을 추가하여 heap 자료구조가 구성됩니다. 그 특성은 바로 모든 Parent는 자신의 Child보다 크거나 작다는 특성입니다... 2020. 10. 28. [5] 이진 탐색 트리 오늘은 이진 탐색 트리(Binary Search Tree)에 대해 다루어 보도록 하겠습니다. 이진 탐색 트리는 트리 구조에서 자식이 항상 2개 이하인 Binary Tree 의 특성을 그대로 물려 받고 거기에 "탐색" 이라는 키워드가 추가되었다고 생각하시면 되겠습니다. 탐색을 용이하기 위해 한가지 규칙이 더 추가되었는데요 자식을 입력할 때 왼쪽 자식엔 현재 노드보다 작은 값을, 오른쪽 자식엔 현재 노드보다 큰 값을 넣는 규칙입니다. 그런 규칙을 갖게 되면, 현재 갖고있는 key를 찾을 때 개별 node에서 크기를 비교해서 왼쪽 child로 탐색할 지 오른쪽 child로 탐색할지를 파악할 수 있어 경로를 찾기에 매우 용이합니다. Binary Search Tree의 예시인데요 Root node 인 8부터 살펴.. 2020. 10. 28. [4] 큐 Queue는 자료구조 중의 하나로, 먼저 입력되는 정보가 먼저 나오는 형태의 구조를 지닙니다. 이를 First in First Out 이라 하고, 앞 글자를 따서 FIFO 라 부릅니다. 자료구조로서의 정의가 있기 전에, queue 라는 단어는 "줄 지어 서있는" 것을 의미하는데요 위 사진 처럼 인기 있는 레스토랑에서 식사를 하려고 줄을 서면, 먼저 온 사람이 먼저 식당에 들어가게 됩니다. 자료구조로서의 큐는 그런 특성을 본따서 지은 이름이 아닐까 생각되네요. 큐가 지원하는 메소드는 다음과 같습니다. Enqueue : Queue의 front(맨 앞)에 값을 넣는 것을 의미합니다. Dequeue : Queue의 Back(맨 뒤)에서 값을 빼는 것을 의미합니다. 큐도 스택과 같이 Array와 LL으로 구현할 .. 2020. 10. 25. [3] 스택 스택 자료구조에 대해 알아보고, 이를 직접 구현하며 자세히 알아보겠습니다. 스택은 자료구조의 한 종류로, 나중에 입력한 정보를 가장 먼저 꺼낼 수 있는 구조를 갖는 자료구조입니다. 이러한 구조를 LIFO (Last In First Out) 라고 합니다. 항상 넣은 순서의 반대로 꺼낼 수 있게 한쪽 방향이 막혀있습니다. Stack의 의미를 생각해보면, 무언가가 쌓여있는 것을 생각하게 되는데, 쌓여있는 것의 맨 마지막 것 부터 뺄 수 없는것과 같은 이치입니다. 스택을 구현한다는 것은, 한쪽으로만 꺼낼 수 있는 구조를 만들어 주는 것이라고 볼 수 있겠습니다. 구현 구현은 Array로 해도 되고 Linked List로 해도 되지만, 이 글에선 Linked List를 이용하여 구현합니다. typedef struc.. 2020. 10. 20. 이전 1 2 3 다음
