CS

01 (1) 02 (1) 완전 이진 트리에 대응되는 번호를 붙일 수 있기에 배열의 인덱스에 넣을 수 있다. 03 (2) 04 (1) 최소 히프 사용 시 오름차순 데이터 추출에 용이 05 (2) 06 2번 노드와 3번 노드중 더 작은 데이터를 가진 노드 07 ⌈log2 10⌉= 4 08, 09, 10, 13, 17 하단 손글씨 풀이 참조 11 typedef struct element { char todo[50]; int key; }element; //max heap 코드 추가 int main(){ char c; HeapType *h; h=create(); init(h); while(c!='q'){ printf("삽입(i), 삭제(d): "); scanf("%c",&c); if(c=='i'){ element..

9.6 머신 스레줄링 머신 스케줄링(machine schdling): 소요시간이 다른 여러 작업을 가장 최소의 시간으로 처리하는 것 - 머신 스케줄링에 대한 최적의 해를 찾는 방법 중 하나가 LPT이다. LPT(longest processing time first): 가장 긴 작업을 우선적으로 스케줄에 할당하는 것. 가장 긴 작업인 빨강부터 초록까지 순차적으로 스케줄에 할당한 후 가장 먼저 끝나는 초록을 작업한 M3에 그 다음 작업인 보라를 할당한다. - 항상 종료 시간이 최소인, 즉 작업이 가장 먼저 끝나는 기계가 다음 스케줄링에 선택된다. - 작업을 할당한 후에는 기계의 종료 시간을 할당한 작업 시간만큼 증가시킨 후에 다시 최소 히프에 넣는다. #include #include #define MAX_E..

9.1 우선순위 큐 추상 데이터 타입 ● 우선순위 큐: 우선순위의 개념을 큐에 도입한 자료구조로, 우선순위가 높은 데이터가 먼저 나간다. 자료구조 삭제되는 요소 스택 가장 최근에 들어온 데이터 큐 가장 먼저 들어온 데이터 우선순위 큐 가장 우선순위가 높은 데이터 - 우선순위 큐는 배열, 연결 리스트 등의 여러 방법으로 구현이 가능한데, 가장 효율적인 구조는 heap이다. - 최소 우선순위 큐는 가장 우선 순위가 낮은 요소를, 최대 우선순위 큐는 우선 순위가 높은 요소를 먼저 삭제한다. ♠ 324p Quiz 01 가장 최근에 들어온 데이터에 우선순위를 부여하면 스택을, 가장 먼저 들어온 데이터에 우선순위를 부여하면 큐를 구현할 수 있는 등 적절한 우선순위만 부여하면 여러 일반적인 자료구조를 구현할 수 있기..

01 (4) 02 (2) A-B-D-C-E-G-H-F 03 (4) 04 (3) D,G,H,F -> 4개 05 (1) 트리의 차수 = B의 차수 = 3 06 (3) + / \ * / / \ / \ A B C D + * A B / C D 07 (4) 2^5-1 08 (3) 09 평균의 시간 복잡도: O(logn) 최악의 시간 복잡도: O(n) 10 (1) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | ------------------------------------------------------------------------------------- | | 6 | 4 | 9 | 2 | 5 | 7 | 10 | 1 | 3 | |..

8.9 이진 트리의 추가 연산 ● 노드의 개수 - 트리안의 노드들을 전체적으로 순회하여 카운트를 센다. int get_node_count(TreeNode *node){ int count =0; if(node!=NULL){ count = 1+get_node_count(node->left) + get_node_count(node->right); } return count; } ● 단말 노드 개수 구하기 - 단말 노드는 노드의 자식 노드가 없을 때만 count를 올려준다. int get_leaf_count(TreeNode *node){ int count =0; if(node!=NULL){ if(node->left ==NULL && node->right ==NULL){ return 1; } else{ count..

8.1 트리의 개념 트리: 계층적인 자료구조로, 가족의 가계도, 회사의 조직도, 인공지능의 결정 트리 등에 사용된다. ● 트리의 용어들 노드: 트리의 구성 요소에 해당하는 각각의 데이터셋 루트 노드: 계층구조에서 최상단에 위치하는 노드 서브 노드: 루트 노드를 제외한 나머지 노드 간선(edge): 루트와 서브트리를 연결하는 선 서브트리: 특정 노드에 대한 하위 노드들의 집합 부모 노드 , 자식노드, 형제노드: 가계도에서의 위치 및 관계와 유사한 노드 조상 노드: 루트 노드~ 임의의 노드까지의 경로를 이루고 있는 노드들 후손 노드: 임의의 노드 하위에 연결된 모든 노드들(특정 노드의 서브트리에 속하는 모든 노드) 단말 노드: 자식 노드가 없는 노드/ terminal node 또는 leaf node / 반대..

01 (3) 02 삽입이나 삭제 연산을 하지 않는 나머지 데이터들을 전체적으로 한 칸씩 옮겨주어야 하므로 배열로 구현된 리스트가 가장 많이 실행시간이 소요된다. (1) 03, 04 ListNode *search(ListNode *L,element data){ //03 ListNode *temp = L->link;; for(temp;temp != L;temp = temp->link){ if(temp->data == data){ return temp; } } return NULL; } int get_size(ListNode* L){ //04 int count=1; ListNode *temp = L->link;; for(temp;temp != L;temp = temp->link){ count++; } retu..

7.5 연결 리스트로 구현한 스택 ● 연결된 스택(linked stack) : 연결리스트를 이용한 스택 - 크기가 제한되지 않은 채 동적 메모리 할당을 통해 새로운 요소를 삽입할 수 있다. - 동적 메모리 할당 및 해제에 소요되는 시간으로 인해 삽입과 삭제 시 소요 시간은 늘어난다. - top 변수를 가장 최근에 삽입된 데이터를 나타내는 정수가 아닌, 노드를 가리키는 포인터로 선언 typedef int element; typedef struct StackNode{ element data; struct StackNode* link; }StackNode; typedef struct{ StackNode *top; }LinkedStackType; 각 노드는 data 필드와 다음 노드를 가리키는 링크 필드로 이루..

7.1 원형 연결 리스트 ● 원형 연결 리스트의 소개, 정의, 처음에 삽입, 끝에 삽입 · 원형 리스트: 마지막 노드가 첫 번째 노드를 가리키는 리스트. - 마지막 노드의 링크 필드가 NULL이 아닌 첫 번째 노드 주소를 가리킨다. - 하나의 노드에서 모든 노드를 거쳐 자기 자신으로 되돌아올 수 있다. - 삭제나 삽입 시 선행 노드를 가리키는 포인터를 통해 연산이 용이해진다. - 특히 리스트의 끝에 노드를 삽입하는 연산 시 모든 노드를 다시 탐색할 필요 없이 헤드 포인터가 마지막 노드를 가리키도록 구성한다. 아래는 원형 리스트의 처음에 삽입하는 코드이다. ListNode* insert_first(ListNode* head, element data){ ListNode *node = (ListNode*)ma..

01 (2) 02 (1) 인덱스를 통해 바로 접근할 수 있다 03 (3) 04 (c) 05 p = p->link; 06 q = p; 07 D 08 (4) delete는 insert와 달리 탐색을 한 후 삭제를 해야되기 때문에 DQ부터 Xn까지의 탐색이 필요 09 ListNode* insert_last(ListNode* head,element item){ ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); newnode->data = item; newnode->link = NULL; ListNode* p = head; if(p==NULL) head = newnode; else { while(p->link !=NULL){ p = p->link; } p->li..