dew's CSE Studying

9.1 우선순위 큐 추상 데이터 타입우선순위 큐의 소개우선순위 큐의 사용: 시뮬레이션 시스템, 네트워크 트래픽 제어, 운영체제에서의 작업 스케쥴링, 수치 해석적인 계산 등우선순위 큐는 배열, 연결리스트 등 여러 가지 방법으로 구현이 가능한데 우리는 가장 효율적인 히프(heap)로 구현~ 최소 우선순위 큐: 가장 우선순위가 낮은 요소를 먼저 삭제최대 우선순위 큐: 가장 우선순위가 높은 요소를 먼저 삭제 9.2 우선순위 큐의 구현방법배열을 사용하는 방법정렬X배열삽입 O(1) : 그냥 배열 맨 끝에 요소 추가삭제 O(n): 가장 우선순위가 높은 요소를 찾아야 한다. 정렬이 안 되어있으므로 처음부터 끝까지 다 스캔해야 한다 정렬O배열삽입 O(n): 삽입위치를 찾고->이동 시켜서 빈자리 만들고->삽입해야함삭제 O..

8.1 트리의 개념-계층적 자료구조트리의 용어들트리는 한 개 이상의 노드로 이루어진 유한집합이다. 루트-서브트리에서 서브트리는 또다시 루트-서브트리로 나눠질 수 있다.조상노드(ancestor node): 루트 노드에서 임의의 노드까지의 경로를 이루고 있는 노드를후손노드(descendent node): 임의의 노드 하위에 연결된 모든 노드들을 의미한다단말노드(terminal node, leaf node): 자식노드가 없는 노드(차수=0)비단말노드(nonterminal node): 자식노드가 있는 노드 노드의 차수(degree): 어떤 노드가 가지고 있는 자식노드의 개수트리의 차수: 트리가 가지고 있는 노드의 차수 중에서 가장 큰 값레벨(level): 트리의 각 층에 번호를 매기는 것. 루트노드가 1층이다높..