힙(Heap) 힙(Heap)이란? 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어지 자료구조이다. 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도이다. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진트리를 말한다. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 힙의 종류 최대 힙(Max Heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 key(부모 노드) >= key(자식 노드) 최소 힙(Min Heap) 부모 노드의 키 값이 자식 노드의 키 값보..

트리(Tree) 트리(Tree)란? 그래프의 일종으로 정점과 간선을 이용하여 데이터의 배치 형태를 추상화한 자료구조이다. 서로 다른 두 노드를 연결하는 길이 하나뿐인 그래프를 트리라고 부른다. 힙(Heap)을 구현하는 방법 중 하나가 트리다. 트리의 특징 그래프의 한 종류로, 최소 연결 트리라고도 불린다. 일반적으로 대상 정보의 각 항목들을 계층적으로 구조화할 때 사용하는 비선형적인 자료구조이다. 트리의 구조는 데이터 저장의 의미 보다는 저장된 데이터를 효과적으로 탐색하기 위해서 사용한다. 리스트와 다르게 데이터가 단순히 나열되는 구조가 아니다. -> 트리는 부모(Parent)와 자식(Child)의 계층적인 관계료 표현된다. 사이클이 없다. 한 개의 루트 노드 만이 존재하며 모든 자식 노드는 한 개의 부..

큐(Queue) 큐의 개념 컴퓨터의 기본적인 자료 구조의 한 가지로, 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식이다. 한쪽 끝에서만 삽입이 이루어지고, 다른 한쪽 끝에서는 삭제 연산만 이루어지는 유한 순서 리스트이다. 큐의 연산 enqueue() : 큐의 맨 끝(rear)에 항목을 추가 dequeue() : 큐가 비어있지 않으면 맨 앞(front) 요소를 삭제하고 반환 peek() : 큐가 비어있지 않으면 맨 앞(front) 요소를 삭제하지 않고 반환 isEmpty() : 큐가 비어 있으면 true 아니면 false를 반환 isFull() : 큐가 가득 차 있으면 true 아니면 false를 반환 size() : 큐의 모든 요소들의 개수를 반환 ..

이진트리(Binary Tree) & 이진 탐색 트리(Binary Search Tree) 이진트리(Binary Tree) 모든 노드들이 둘 이하의 자식을 가진 트리이다. 이진트리 유형 전 이진트리(Full Binary Tree) 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다. 완전 이진트리(Complete Binary Tree) 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리이다. 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다. 마지막 레벨 h에서 1 ~ 2h - 1개의 노드를 가질 수 있다. 완전 이진트리는 배열을 사용해 효율적으로 표현이 가능하다. 포화 이진트리(Perfect Binary Tree) 모든 내부 노드가 두 개의 자식 노드를 가지며..

리스트(List) 리스트란? 데이터를 순차적으로 저장하는 선형 자료구조 순서를 가진 항목들의 모임 배열이 가지고 있는 인덱스라는 장점을 버리고 빈틈없는 데이터 적재라는 새로운 장점을 취한 자료구조 중복된 데이터의 저장을 허용 ArrayList, LinkedList 등 여러 인터페이스를 구현한 자료형 자바스크립트, 파이썬 같은 경우 리스트를 따로 구현하지 않고 배열에 List의 기능 중 일부를 제공 1. ArrayList 배열을 이용해서 리스트를 구현하는 것을 의미하는 자료구조이다. 장점 index를 통한 검색이 용이하다. 연속적이므로 메모리 관리가 편하다. 내부적으로 배열을 이용하기 때문에 인덱스를 이용하여 접근하는 것이 빠르다. 단점 데이터의 추가, 삭제가 느리다. 정적이므로 배열의 크기를 컴파일 이전..

너비 우선 탐색(BFS) & 깊이 우선 탐색(DFS) 너비 우선 탐색(Breadth-First Search) 루트 노트(혹은 다른 임의의 노드)에서 시작해 인접한 노드를 먼저 탐색하는 방법 그래프 탐색이란 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다. 예를 들어, 특정 도시에서 다른 도시로 갈 수 있는지, 전자회로에서 특정 단자와 단자가 서로 연결되어 있는지를 탐색하는 알고리즘이다. 장점 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다. 단순 검색 속도가 깊이 우선 탐색(DFS) 보다 빠르다. 너비를 우선 탐색하기에 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장한다. 최단경로가 존재한다면 어느 한 경로가 무한히 깊어진다해도 최단경로를 반드시 찾을 수 있..