알고리즘/이론정리3 우선순위 큐(Priority Queue) 일반적인 큐는 먼저 집어넣은 데이터가 먼저 나오는 FIFO구조로 저장하는 선형 자료구조이다. 하지만 우선 순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는것을 말한다. 우선순위 큐의 속성 모든 항목에는 우선순위가 있다. 우선위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 큐에서 제외 됌 두 요소의 우선 순위가 같으면 큐의 순서에 따라 제공 예시 데이터가 4 -> 8 -> 2순으로 들어간다고 했을때 큐와 우선순위 큐의 처리 순서는 (높은 값이 높은 우선순위를 갖는다고 가정함) input : 4 -> 8 -> 2 큐: 4 -> 8 -> 2 우선순위 큐 : 8 -> 4 -> 2 우선순위 큐를 구현하는 방법 단순히 리스트를 기반으로 구현 힙을 이용하여 구현 데이터의 개수가 n개일 때, 시.. 2021. 9. 10. 이진트리(binary tree), 이진트리 순회방법 이진트리 : 부모 하나에 자식이 둘 딸린 구조 1.1 이진트리 종류 Binary Tree(기본) 다른 조건 없이 자식노드가 2개씩만 붙어 있음됌 Binary Search Tree 안에 데이터가 왼쪽 노드와 그 이하의 자식 도드들은 현재 노드 보다 작아야 함 오른쪽 노드와 그 이하 자식 노드들은 현재노드(8) 보다 커야함 만약 8보다 작은수를 찾고싶으면 왼쪽, 반대로 8보다 큰 수를 찾고싶으면 오른쪽으로 가면 된다. Balance UnBalance Complete Bianry Tree(완전이진트) 모든 노드들이 왼쪽부터 채워져 있고 마지막 레벨은 왼쪽부터 채워져 있다 Full Bianry Tree 자식노드가 아예 없거나 2개로 구성된 Tree Perfect Bianry Tree 모든 노드가 2개의 자식노드.. 2021. 8. 25. Hash, Hashing, Hash Table <해시, 해싱, 해시 테이블> Hash란? hash는 임의 크기를 가진 데이터를 고정된 데이터 크기로 변환시키는 것을 뜻함 hash를 이용해서 특정한 배열의 인덱스나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다. hash의 장점 저장하거나 찾고자 하는 위치를 참조할 수 있다 => 빠른 속도로 처리가능 Hash Table 고정된 판을 먼저 선언함 key-value 쌍에서 key값을 테이블에 저장할 때 key값을 함수를 이용해 계산 ->결과값을 배열의 인덱스로 사용하여 저장하는 방식(여기서 key값을 계산하는 함수는 hash function이라 함) Collusion : 충돌 hash table은 충돌이 일어 날 수 있다는 큰 단점이 있다. 충돌이 일어나는 경우 충돌해결 방법 2가지 chaining과 Open A.. 2021. 8. 13. 이전 1 다음
