CS

11.1 최소 비용 신장 트리● 신장 트리(spanning Tree): 그래프 내의 모든 정점을 포함하는 트리- 모든 정점들이 연결되어 있어야 한다.- 사이클을 포함하여선 안된다.- n개의 정점을 정확히 (n-1) 개의 간선으로 연결한다.- 하나의 그래프에는 많은 신장 트리가 존재 가능하다. - dfs나 bfs를 수행하면서 탐색 도중에 사용된 간선들을 모으면 신장 트리를 만들 수 있다.- 신장 트리 = 그래프의 최소 연결 부분 그래프 = n-1개의 간선으로 연결되어 있으면 필연적으로 신장 트리 ● 최소 비용 신장 트리 (MST: minimum spanning tree): 신장 트리 중 사용된 간선들의 가중 치 합이 최소인 신장 트리- 신장 트리의 조건들을 마찬가지로 지켜야 한다.(n..

01 (2) 02, 06 03 (2) 04 무방향 그래프면 간선마다 2개의 노드가 생기므로 (2) 05 (2) 07 (1) 진입 진출 0 1 3 1 2 2 2 3 1 3 2 2 4 3 2 5 0 1 (2) 0 = {1, 2, 3} 1 = {0, 2, 3, 4} 2 = {0, 1, 4} 3 = {0, 1, 4} 4 = {1, 2, 3, 5} 5 = {4} 7 (5) 0, 1, 3 사이클 -> 85 1, 2 ,4 사이클 -> 60 0, 2, 4 , 1, 3 사이클 -> 130 1, 3, 4 사이클 -> 50 09 (1) O(n) (2) O(n) (3) O(n^2) 10 정점은 n, 간선은 e개라고 하면 (1) O(e) (2) O(e) (3) O(e) 12 생략 13 (1) 3 1 0 2 4 5 6 7 8 9..

10.4 그래프의 탐색 ● 그래프 탐색: 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 - 깊이 우선 탐색(DFS: depth first search): 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 다른 방향으로 탐색하는 순회 방법 - 너비 우선 탐색(BFS: breath first search): 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어진 정점을 나중에 방문하는 순회 방법 10.5 깊이 우선 탐색 - 시작 정점 v부터 방문한 정점을 표시하고, 인접한 정점들 중에서 아직 방문하지 않은 정점 u를 선택 - 방문하지 않은 정점이 없으면 탐색 종료 - 아직 방문하지 않은 정점 u가 있다면 그 u를 새로운 시작 정점으..

10.1 그래프란? ● 그래프: 객체 사이의 연결 관계를 표현할 수 있는 자료구조 - ex) 지하철 노선도, 전기 회로 그래프, 운영체제의 프로세스 및 자원들의 연결 관계 그래프 - 선형리스트나 트리의 구조로는 표현하기 어려운 복잡한 문제들을 표현할 수 있다. (트리도 일종의 그래프) - 인접 행렬이나 인접 리스트로 메모리에 표현되고 처리될 수 있다. - 문제 해결을 위한 도구로서 많은 이론과 응용이 존재 ● 그래프의 역사 수학자 오일러의 konigsbert bridge 문제는 '각 지역에서 출발하여 7개의 모든 다리를 단 한 번만 건너서 처음 출발했던 지역으로 돌아올 수 있는가'라는 문제다. 오일러는 이 문제에 대해 '각 지역에 연결된 다리의 개수가 모두 짝수여야함'을 증명하였다. - A, B, C, ..

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 / 반대..