두드리는 개발자 홍차/Data Structure2 우선순위 큐 - 히프, 허프만 코드 개념 보통의 큐는 FIFO(first-in-first-out) 원칙에 따라 먼저 들어온 데이터가 먼저 나간다. 그러나 우선순위 큐는 데이터들이 우선순위를 가진다. 따라서 우선순위가 높은 데이터가 먼저 나간다. 구현방법 배열 사용 연결리스트 사용 히프 사용 히프 히프는 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다. 완전 이진 트리이다. 히프의 종류는 최대히프, 최소히프 두 가지가 있다. max heap : key(부모 노드) >= key(자식 노드) min heap : key(부모 노드) 영상압축, 딥러닝 등에 활용 //최소히프를 사용한 허프만 코드 #include #include #define MAX_ELEMENT 200 typedef struct Tre.. 2019. 12. 13. TIL #017 정렬 알고리즘 - Selection sort 오늘 배운 것> 정렬 알고리즘 - 선택 정렬(selection sort), 카운팅 정렬(counting sort) 1. 정렬 알고리즘은 ‘정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지된다면’ 안정 정렬(stable sort)로 구분한다. 예를 들어, 4(1) 5 3 4(2) 1을 선택정렬(selection sort)한다면 선택정렬은 최소값을 찾아서 이 최소값을 배열의 첫번째 요소와 교환한다. 따라서 선택정렬의 과정은 다음과 같다. 4(1) 5 3 4(2) 1 1 5 3 4(2) 4(1) 1 3 5 4(2) 4(1) 1 3 4(2) 5 4(1) 1 3 4(2) 4(1) 5 그 결과 4(1)과 4(2)의 순서가 바뀌었음을 알 수 있다. 이를 해결하여 안정 정렬로 만들기 위해서는 최.. 2019. 11. 28. 이전 1 다음
