공부하는 블로그

Heap ? 힙(Heap)은 부모 노드와 자식 노드 간에는 키 값의 대소관계가 존재하는 완전 이진트리이다. 대소관계는 오로지 부모 노드와 자식 노드 간에만 성립하며 형제 사이에는 대소관계가 정해지지 않는다. 부모 노드의 값이 자식 노드의 값보다 크거나 같으면 최대 힙(Max Heap), 그 반대면 최소 힙(Min Heap)이다. * 이진트리(Binary Tree) : 한 노드가 최대 두 개의 자식노드를 가지는 트리 * 완전 이진트리(Complete Binary Tree) : 노드를 삽일할 때 왼쪽부터 차례대로 삽입하는 이진 트리이다. 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안되었으며 우선순위 큐를 구현할 때 주로 사용된다. * 우선순위 큐(Priority Queue) : 우선순위가 ..

Graph ? 그래프(Graph)는 노드(N, Node)와 그 노드를 연결하는 간선(E, Edge)을 통해 정점간의 관계를 표현하는 자료구조이다. 일상 생활 속 지도나 지하철 노선도를 그래프라고 할 수 있다. 지도 어플에서 지점 간 최단 거리를 찾는 과정은 그래프를 탐색하는 과정이라 볼 수 있다. Graph 종류 그래프에서 간선은 방향성이 존재하며 화살표를 이용하여 표현한다. 간선은 순환이 가능하며 자체 간선(Self-loop)도 가능하다. 이러한 간선의 방향성과 순환성으로 그래프의 종류를 나눌 수 있다. 방향성의 유무에 따라 방향 그래프(Directed)와 무방향 그래프(Undirected)로, 순환성의 유무에 따라 순환 그래프(Cyclic)와 비순환 그래프(Acyclic)로 나뉜다. 간선에 가중치가 ..

Hash Table 해시 테이블(Hash Table)은 자료의 탐색을 위한 알고리즘으로 탐색 키워드인 Key와 그에 대한 결과 값인 Value가 한 쌍으로 저장된 자료구조이다. 해시 테이블은 해싱(Hashing)을 통해 Key 값에 알맞은 Value를 찾아낸다. Hashing? 해싱은 Key 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 해싱에서 자료를 저장하는 데 배열을 사용한다. 배열은 원하는 항목이 저장된 인덱스(index)를 알고 있을 경우 O(1)의 시간 복잡도로 매우 빠르게 자료를 삽입하거나 꺼낼 수 있다. 배열의 인덱스는 0부터 시작하는 정수로 문자열인 Key를 통해 배열로 저장된 Value에 접근하기 위해서는 해시 함수(Hash Func..

Queue? 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. Queue Method · add() : 리스트의 끝 부분에 새로운 요소를 추가한다. · remove() : 리스트의 첫 번째 항목을 제거한다. · peek() : 큐에서 가장 위에 있는 항목을 반환한다. · isEmpty() : 큐가 비어 있을 때에 true를 반환한다. Queue Code(JAVA) import java.util.ArrayList; import java.util.List; class MyQueue { private List que = new ArrayL..