Computer Science/알고리즘30 [알고리즘] ep1-3) 힙(heap) *완전 이진 트리(Complete Binary Tree): 트리의 위부터 아래, 왼쪽부터 오른쪽의 순서로 빠짐없이 가득 차있는 이진 트리 ㅁ힙(heap): 가장 크거나 가장 작은 값을 빠르게 찾기 위해 만든 완전 이진 트리의 일종 + 영단어 heap: 무엇인가를 차곡차곡 쌓아 올린 더미+ 자료구조의 힙(Heap)과 컴퓨터 메모리의 힙 영역(Heap Area)은 완전히 다른 개념이다 [힙의 활용]우선순위 큐(Priority Queue): 힙을 사용하여 구현할 수 있으며, 각 요소가 우선순위를 가지는 큐힙 정렬(Heap Sort): 힙을 이용한 정렬 알고리즘으로, O(nlog(n))의 시간 복잡도를 가진다그래프 알고리즘: 크루스칼 알고리즘, 다익스트라 알고리즘 등에서 우선순위 큐를 활용해 최소 신장 트리,.. 2024. 7. 3. [알고리즘] ep1-1) 우선순위 큐 ㅇ우선순위 큐(Priority Queue): 각 요소마다 우선순위를 부여하고 이 우선순위에 따라 요소를 처리하는 큐요소가 삽입될 때 우선순위가 함께 부여되며, 삭제 시에는 가장 높은 우선순위를 가진 요소가 먼저 삭제된다 활용 분야: CPU 작업 스케줄링, 네트워크 패킷 처리, 최단 경로 알고리즘(다익스트라 알고리즘 등) 등 [구현 방법 2가지]1. 리스트를 이용한 구현① 무순리스트로 구현: 리스트에 임의 순서로 저장e.g. 선택정렬 ② 순서리스트로 구현: 리스트에 키 정렬 순서로 저장e.g. 삽입정렬 2. 힙을 이용한 구현① 최대 힙 사용② 최소 힙 사용 일반적으로 우선순위 큐를 구현할 때는 힙을 사용하는 것이 가장 효율적이다(최대 힙 or 최소 힙) 출처 및 참고: 알고리즘-원리와.. 2024. 7. 3. [알고리즘] ep1-2) 버블정렬, 선택정렬, 삽입정렬 컴퓨터에서 정렬을 수행하는 이유 중 가장 큰 이유가 바로 이진 탐색이 가능한 데이터를 만들기 위해서이다이진탐색의 시간복잡도: O(log(n)) ㅇ제자리(in-place): 추가적인 메모리 공간을 거의 사용하지 않고, 주어진 데이터 구조 내에서만 작업을 수행하는 것일반적으로 어떤 정렬 알고리즘이 정렬 대상 개체를 위해 필요한 메모리에 추가하여 오직 상수 메모리만을 사용한다면, 해당 정렬 알고리즘이 제자리(in-place)에서 수행한다고 얘기한다 장점메모리 효율성: 추가적인 메모리 공간을 거의 사용하지 않으므로 메모리 효율성이 높다캐시 효율성: 메모리 내에서 직접 데이터 이동이 이루어지기 때문에 캐시 효율성이 높다단점복잡한 구현: 일부 복잡한 알고리즘의 경우 제자리 알고리즘으로 구현하기 어려울 수 있다비.. 2024. 7. 2. 이전 1 2 3 4 다음
