Data Structure4 힙(Heap)을 통한 우선순위 큐 구현 우선순위큐 (Priority Queue) 우선순위큐는 우선순위에 따라 정렬되어 순차적으로 처리되는 자료구조이다. 우선순위큐는 Heap을 통해 구현이 가능하다. 힙(Heap) Heap은 '완전 이진 트리'로 구현된 트리구조의 자료구조이다. Max Heap인지 Min Heap인지 여부에 따라 부모와 자식은 절대적인 정렬상태를 가진다. +) 형제(sibiling)끼리의 정렬은 관계가 없다 O(log2n)의 준수한 시간복잡도를 가진다. 최대(Max) 힙을 통한 우선순위 큐 구현은 다음과 같다. #include using namespace std; #define MAX_SIZE 99999 //삽입과정은 완전 이진트리를 유지하는 형태로 순차적 삽입. // 왼쪽에서 오른쪽으로 순차적으로 삽입 // 삽입 이후에 루트노.. 2021. 11. 25. Hash Table과 Map은 언제 사용하면 좋을까? Hash Table Map 삽입속도 O(1) O(logN) 삭제속도 O(1) O(logN) 검색속도 O(1) O(logN) Hash와 Map의 핵심적인 차이점은 다음과 같다. 1. Hash table은 멀티스레드에서 동기화를 지원할 수 있다. 2. Map은 항상 정렬된 상태로 데이터가 유지된다. 3. Hash는 Hash Function을 이용해 O(1)의 검색속도를, Map은 O(logN)의 성능을 지닌다. 따라서 데이터의 양이 적을 경우 map보다 Hash Table의 성능이 우수해진다. 기본적으로 RB-Tree 기반으로 구현되어 자체적인 balancing이 가능하기에 성능은 트리의 레벨만에 영향을 받는다. http://veblush.github.io/ko/posts/map-vs-unorderedmap.. 2021. 10. 18. Stack의 구현은 벡터 vector ? 연결리스트 Linkedlist ? 최근 졸업이 예정되면서 면접을 보러다니기 시작하고 있다. 면접에서는 보통 1차적으로 기술면접을 보게되는데, 전공과 업계기술을 얼마나 숙지하고 있는지 질문을 받게된다. 개인적으로 기대되는 프로젝트를 진행중인 회사에서 운좋게 면접기회를 얻게 되었는데 해당 면접에서 면접관님께 받았던 질문중 하나가 글의 제목과 같다. "Stack을 구현할때는 벡터와 연결리스트 중 어떤걸 선택하실건가요?" stack, vector, linkedlist 세가지를 모두 파악하고 있어야 답할 수 있어야하는 질문이었다. 앞선 질문에 vector와 linkedlist의 장단점에 대해서는 제대로 답을 했지만 Stack이 연관되자 당시에 쉽게 답을 내지 못했다. 그렇게 어려운 질문을 하신것도 아니었는데, 지금 생각하면 정말 창피한 기억이다... 2021. 10. 17. 원형 큐 (circular queue) 일반적인 큐, 버퍼의 형태와 같이 FIFO의 구조를 가지고 있다. (First In First Out) 입력부와 출력부를 담당하는 Front와 Rear변수도 동일하다. 다만 원형 큐의 경우 일반적인 선형 큐의 문제점을 보완한다. 선형적인 큐의 경우 구조상 Dequeue를 할때마다 front가 앞으로 진행되면서 front가 진행된 공간이 활용되지 못하게된다. 이는 굉장히 비효율적인데 원형큐의 경우 큐가 다찼을 경우 혹은 배열이 모두 비워졌을경우, rear를 전체 배열 크기로 %(모듈러)연산을 하여, 다시 처음부터 회귀하여 공간을 활용한다. 원형큐에서도 오버플로우 발생 시 오버라이트(배열 제일 첫번째 원소를 덮어쓰며 회귀)를 허용하는 경우와 허용하지 않는 경우가 있는데 이는 원형큐의 용도에 따라 다르다. 원.. 2021. 8. 8. 이전 1 다음
