자료구조/큐(Queue) (4) 썸네일형 리스트형 [자료구조] 힙(Heap)과 우선순위 큐(Priority Queue) - 코딩밥상 힙(Heap)이란? 힙은 순서 속성(Heap Order Property)을 만족하는 완전 이진 트리입니다. 완전 이진 트리를 복습하자면, 최고 깊이를 제외한 모든 깊이의 노드가 완전히 채워져있는 트리입니다. '힙 순서 속성'이란 트리 내의 모든 노드가 부모 노드보다 커야 한다는 규칙입니다. (본 정리 글에서는 정수 데이터 값을 priority기준으로 하겠습니다.) 힙은 이진 탐색이 불가능하기에 모든 노드를 순회하며 탐색해야 합니다. 하지만 "힙에서 가장 작은 데이터를 갖는 노드는 뿌리 노드이다" 라는 규칙을 가집니다. 따라서 힙에 사용되는 연산은 두 가지뿐입니다 노드 삽입 연산 힙의 최고 깊이 가장 우측에 새 노드를 추가(완전 이진 트리 유지) 삽입한 노드를 부모 노드와 비교 - 부모 노드보다 크면 종료.. [자로구조] 링크드 큐(Linked Queue) - 코딩밥상 링크드 리스트 기반으로 큐 구현하기 링크드 큐는 순환 큐보다 직관적으로 구현할 수 있습니다. 링크드 큐의 각 노드는 이전 노드에 대한 포인터를 이용해 연결되므로 삽입 연산을 할 떄는 삽입 하려는 노드에 후단을 연결하고, 제거 연산을 할 때는 전단 바로 다음 노드에서 전단에 대한 포인터를 거두기만 하면 됩니다. 링크드 큐와 순환 큐의 또 다른 한가지 점은 큐가 가득 찬 상태인지 확인할 필요가 없습니다. 배열 기반으로 구현한 순환큐와는 다르게 링크드 리스트 기반은 용량의 제한이 없기 때문입니다. 하지만 성능적으로 치면 순환 큐가 더 빠릅니다. 노드를 생성하고 삭제하기 위해 malloc()과 free()함수를 호출 할 필요가 없기 때문입니다. 따라서 필요한 큐의 크기를 미리 정할 수 있고 고성능이 요구되는 상.. [자료구조] 순환 큐(Circular Queue) - 코딩밥상 배열 기반 순환 큐 배열을 기반으로 선입선출의 방식을 따르는 큐를 구현한다고 생각해 봅시다. 제거 연산 후에 전단 요소가 삭제 된다면 남아있는 모든 요소들은 빈 자리를 채우기 위해 앞으로 당겨야 합니다. 이는 엄청난 비용을 필요로 합니다. 그렇다면 전단을 가리키는 변수를 도입해서 배열 내 요소들을 옮기는 대신 전안의 위치만 변경하면 어떻게 될까요? 그 전처럼 불필요한 비용은 발생하지 않지만, 배열의 크기는 생성과 함께 고정되기때문에 삽입과 연산이 반복될수록 사용가능한 배열의 공간은 점차 작아지다가 결국 사용 불가능해지겠네요... 이러한 복잡한 문제를 해결하기 위해 이 책에서는 고대 로마 철학자인 세네카가 남긴 명언을 제시합니다. "모든 시작은 또 다른 시작의 끝으로부터 비롯된다." 즉 배열의 끝과 시작.. [자료구조] 큐(Queue) - 코딩밥상 큐의 개념 앞서 배운 스택은 데이터의 입출력이 이루어지는 창구가 하나뿐이고 데이터 처리 방식이 LIFO인 ADT였습니다. 이번에 배울 큐는 이와 반대로 입출력 창구가 각각 따로 존재하고, 제일 먼저 들어간 데이터가 제일 먼저 나오는 FIFO(First In First Out)구조 입니다. 은행에 일을 보러 가서 대기번호를 뽑는경우, 맛집을 가서 웨이팅을 서는 경우 등 일상생활에서 자주 접하는 방식들이 큐로 이루어 질 수 있겠네요 즉 다른 작업에 영향을 받지 않고 데이터의 입력 순서대로 선입선출을 따라 동작하는 알고리즘을 짤 때 유용하게 사용할 수 있습니다. 큐의 핵심 기능 '삽입과 제거' 큐의 가장 앞 요소를 전단, 가장 마지막 요소를 후단이라고 부르는데, 삽입 연산은 후단, 제거 연산은 전단에서 각각 .. 이전 1 다음
