괴발자의 전공노트

#큐(Queue) 란? 큐(Queue)는 대표적인 자료구조 중 하나로 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 형태를 가진 자료구조를 의미한다. 쉽게 생각하면 대기열을 생각하면 된다. 예를 들어 손님이 많은 가게에서 웨이팅을 할 때 가장 먼저 기다린 사람이 가게에 자리가 생기면 가장 먼저 입장하는 것과 같다. 이렇게 큐(Queue) 와 같은 형태를 FIFO(First In First Out) 구조라고 칭하기도 하며 가끔 LILO 구조 라고(Last In Last Out) 칭하기도 한다. 위 그림을 보면 알 수 있듯이 큐(Queue)에 데이터를 넣는 것을 Enqueue라고하며, 데이터를 꺼내는 행위는 Dequeue라고 칭한다. #큐(Queue) 의 종류 1) 큐(Queue) 가장 표준적인 큐(Qu..

힙(Heap) 이란? Heap은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리의 한 종류이다. Tip! 완전 이진 트리(CBT, Complete Binary Tree) 완전 이진 트리는 노드를 삽입할 때 왼쪽 최하단 노드부터 순서대로 데이터를 삽하는 이진 트리를 의미한다. 힙(Heap)의 구조와 조건 힙은 최대값을 구하기 위한 구조를 가진 최대 힙(Max Heap) 과, 최소값을 구하기 위한 구조를 가진 최소 힙(Min Heap)으로 분류할 수 있다. 힙은 아래와 같이 두 가지 조건을 가지고 있는 자료구조를 의미한다. 최대 힙(Max Heap)의 경우, 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같아야 한다. 최소 힙(Min Heap)은 반대로 각 노드의 값은 해..

트리(Tree) 란 ? 계층적인 데이터 구조로 노드(Node)와 엣지(Edge, 가지 또는 연결선)을 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조를 의미한다. (Edge는 가지라는 의미에서 Branch라고 부르기도 한다.) 참고로 Tree도 그래프의 한 종류이나 그래프는 사이클을 이루는 자료구조를 포함한다. 트리에서 각 요소는 노드로 표현되며, 노드는 데이터를 저장하는 요소를 의미한다. 주로 트리 중 이진 트리(Binary Tree) 가 탐색(검색) 알고리즘 구현시 많이 사용된다. 트리의 구성요소 노드(Node) 트리에서 데이터를 저장하는 기본요소로 데이터와 연결된 노드에 대한 Branch의 주소를 포함한다. 부모 노드(Parent Node) 어떤 노드의 이전 레벨에 Branch로 연결된 노드를..

해쉬 테이블(Hash Table) 키(key)에 데이터(Value)를 저장하는 데이터 구조 Key를 통해 바로 데이터를 받아올 수 있기 때문에 배열이나, 리스트에 비해 속도가 훨씬 빠르다. 자바의 해쉬 맵(HashMap)과 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블로 구현된 대표적인 예시로 키(Key)값을 가지고 바로 값(Value)를 꺼낼 수 있다. 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용한다. (아래코드 참고) import java.util.HashMap; public class HashMapExample { public static void main(String[] args) { // 초기 용량(capacity)을 10으로 설정하여 HashMap 생성 int i..

그래프(Graph) 그래프는 노드(하나의 점) 간을 연결하는 간선으로 구성된 자료 구조를 의미한다. 그래프(Graph)특징 - 그래프는 순환 혹은 비순환 구조를 이룬다. - 그래프는 방향이 있는 그래프와 방향이 없는 그래프가 있다. - 루트 / 노드(부모 / 자식)의 개념이 없을 수도 있다. - 무방향, 방향 ,양방향 등 2개 이상의 경로가 가능하다. - 네트워크 모델이다. 트리(Tree) 트리는 그래프와 같이 노드와 노드간을 연결하는 간선으로 구성된 자료구조이다. 그러나 트리는 그래프 중에서도 특수한 케이스에 해당하는 자료구조이다. 트리는 두 개의 노드 사이에 반드시 1개의 경로만을 가지며 사이클이 존재하지 않는 방향 그래프이다. 이러한 특성 때문에 '최소 연결 트리'라고 부르기도 한다. 부모 / 자식..