반응형 큐2 우선순위 큐와 힙은 뭘까? 23.1 도입 우선순위 큐 선입선출이 아니고, 우선순위가 가장 높은 자료가 가장 먼저 꺼내진다. 연결 리스트나 동적 배열로 구현 가능하다 O(n) 시간 소요되며 비효율적이다. 힙을 통해 구현하는 것이 가장 적합하다. 힙 가장 큰 또는 가장 작은 원소를 찾는데 최적화된 형태의 이진 트리 O(lgN) 시간 소요 23.2 힙의 정의와 구현 특정한 규칙을 만족하는 이진 트리 대소 관계 규칙: 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소 이상이다. 힙의 모양 규칙 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. 마지막 레벨에 노드가 있을 때는 항상 왼쪽부터 순서대로 채워져 있어야 한다. 배열을 이용한 힙의 구현 트리에 포함된 노드의 개수만 알면 트리 전체의 구조를 알 수 있다. 배열을 제일.. 2024. 4. 17. 큐와 스택, 데크는 뭘까? 큐와 스택, 데크 일렬로 늘어선 같은 형태의 자료들을 저장한다. 셋의 차이는 어느 쪽 끝에서 자료를 넣고 뺄 수 있는가 이다. 셋 다 O(1)에 이루어진다. push : 자료를 넣는 것 pop : 자료를 빼는 것 큐 선입선출 가장 먼저 들어간 자료 순으로 빠진다. 줄서기 스택 후입선출 가장 늦게 들어간 것 순으로 빠진다. 컨텍스트 관리 데크 양쪽 끝에서 자료들을 넣고 뺄 수 있다. 스택과 큐를 모두 구현 가능하다. 19.2 큐와 스택, 데크의 구현 연결 리스트 양쪽 끝에서 추가와 삭제를 모두 상수 시간에 할 수 있다. 노드의 할당과 삭제, 포인터를 따라가는데 드는 시간이 걸리기 때문에 가장 효율적이진 않다. 동적 배열 스택은 쉽게 가능하다. 하지만 앞에서 추가와 삭제가 일어나는 것은 동적 배열에서 쉽지 .. 2024. 4. 17. 이전 1 다음 728x90 반응형
