알고리즘 (4) 썸네일형 리스트형 [알고리즘] Huffman Coding ※ 2022년 4월 12일에 작성된 글입니다.Huffman Coding데이터 문자의 등장 빈도에 따라서 다른 길이의 부호를 사용하는 알고리즘Huffman Coding Tree각 글자의 빈도가 알려져 있는 메시지의 내용을 압축하는데 사용되는 이진 트리생성 절차문자빈도 수A41B35C62D4E97모든 문자를 빈도수에 따라 나열한다.가장 빈도수가 낮은 노드 2개를 고른다.해당 노드를 자식 노드로 하는 새로운 부모 노드를 만든다.하나의 루트 노드가 나올 때까지 2~3번 과정을 반복한다. [자료구조] Graph ※ 2022년 1월 27일에 작성된 글입니다.🖇 Graph연결되어 있는 객체 간의 관계를 표현하는 자료구조Graph의 구조vertices(정점)= node여러 가지 특성을 가질 수 있는 객체 V(G): 그래프 G의 정점들의 집합 edge(간선)= link정점들 간의 관계 E(G): 그래프 G의 간선들의 집합 Graph vs Tree GraphTree방향성방향, 무방향방향순환가능불가능루트 노드루트 노드의 개념이 없음한 개의 루트 노드만 존재부모-자식부모-자식의 개념이 없음부모-자식 관계모델네트워크 모델계층 모델순회DFS, BFSDFS, BFS 안의 Pre-, In-, Post-order간선의 수그래프의 따라 다름노드가 N인 트리는 항상 N-1의 간선을 가짐Graph의 종류무방향 그래프방향 그래프Graph.. [자료구조] Heap ※ 2022년 1월 10일에 작성된 글입니다.🌳 Heap부모 노드의 키가 자식 노드의 키보다 크거나 같은 완전 이진 트리Heap의 종류max heap부모 노드의 키 ≥ 자식 노드의 키min heap부모 노드의 키 ≤ 자식 노드의 키Heap의 높이n개의 노드를 가지고 있는 힙의 높이는 O(log n)마지막 레벨 h 외에는 각 레벨 i에 2i-1개의 노드 존재Heap의 구현 방법배열완전 이진 트리이므로 각 노드에 번호(배열의 인덱스)를 붙일 수 있다.012345678910 9765432213부모 노드와 자식 노드를 찾기가 쉽다.왼쪽 자식의 인덱스 = 부모의 인덱스 * 2오른쪽 자식의 인덱스 = 부모의 인덱스 * 2 + 1부모의 인덱스 = 자식의 인덱스 / 2Heap의 연산upheap삽입downheap삭제u.. [자료구조] Priority Queue ※ 2022년 1월 4일에 작성된 글입니다.🚦 Priority Queue우선순위를 가진 항목들을 저장하는 큐FIFO가 아니라 우선 순위가 높은 데이터가 먼저 나간다.Priority Queue의 연산insert우선순위 큐에 요소를 추가한다.delete우선순위 큐에서 가장 우선순위가 높은 요소를 삭제하고 이 요소를 반환한다.find우선순위가 가장 높은 요소를 반환한다.isEmpty우선순위 큐가 비어있는지 확인한다.Priority Queue의 구분최소 우선순위 큐최대 우선순위 큐Priority Queue의 응용 분야시뮬레이션 시스템네트워크 트래픽 제어운영 체제에서의 작업 스케쥴링Priority Queue의 구현 방법배열(array)연결리스트(linked list)힙(heap)구현 방법삽입삭제순서 없는 배열O.. 이전 1 다음
