Data Structure – Segment Tree (Range Sum & Range Max)
세그먼트 트리(Sement Tree) 특정 구간 내 데이터에 대한 연산을 빠르게 구할 수 있는 트리(연산: 합, 최댓값, 최솟값 등) 세그먼트 트리의 잎 노드: […]
Category: Data Structure
자료구조
Data Structure – Topological sorting (위상 정렬)
위상 정렬: 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용되는 알고리즘 ex) 1->4->0->2->3->5 방향 그래프를 대상으로 위상 정렬을 […]
Data Structure – Huffman Coding (데이터 압축)
힙을 이용한 허프만 부호화 (텍스트 데이터 압축) 유니코드 문자는 1바이트씩 차지한다. 만약 문자가 10개면 10바이트나 차지하게 된다.그러나 ‘데이비드 허프먼‘이 제시한 압축 기법에 […]
Data Structure – Red Black Tree (Insert Function)
레드-블랙 트리 2-3-4트리 역할이 가능한 이진 탐색 트리 레드 블랙 트리 테스트 예시 (전개도 참고) 레드-블랙 트리 삽입 연산 구현
Data Structure – Floyd Algorithm
최단경로 알고리즘 에지에 가중치가 주어진 방향 그래프에서 경로의 길이는 경로 상에 있는 에지 가중치 합이다.이 합이 가장 작을 때 ‘최단 경로’라고 한다. […]
Data Structure – Bellman Ford Algorithm
최단경로 알고리즘 에지에 가중치가 주어진 방향 그래프에서 경로의 길이는 경로 상에 있는 에지 가중치 합이다.이 합이 가장 작을 때 ‘최단 경로’라고 한다. […]
Data Structure – Dijkstra Algorithm
최단경로 알고리즘 에지에 가중치가 주어진 방향 그래프에서 경로의 길이는 경로 상에 있는 에지 가중치 합이다.이 합이 가장 작을 때 ‘최단 경로’라고 한다. […]
Data Structure – Prim Algorithm
MST: 프림 알고리즘 ‘부분 트리에 속한 정점’과 ‘인접한 정점’ 사이의 에지 중 가중치가 최소인 에지를 선택한다. n-1개의 에지가 선택될 때까지 진행한다. prim으로 […]
Data Structure – Kruskal Algorithm
크루스칼 알고리즘 가중치가 작은 순서대로, 에지를 하나씩 추가하며 MST를 만든다. Cycle이 만들어지면 해당 에지는 버린다. 이를 n-1개의 에지가 만들어질 때까지 진행한다. MST: […]
Data Structure – Heap (Algorithm)
힙(Heap) 각 노드에 저장되어 있는 값이 자식 노드에 저장되어 있는 값보다 크거나 같은 완전 이진 트리 (최대 힙)각 노드에 저장되어 있는 값이 […]