전체 글

12.1 정렬이란? ● 정렬: 대상을 크기순으로 오름차순이나 내림차순으로 나열하는 것(키 값을 기준으로) - 레코드: 정렬시켜야 할 대상 - 필드: 레코드의 구성단위 ex) 학생이라는 레코드의 필드는 이름, 학번, 주소, 등 - 키(key): 레코드와 레코드를 식별해 주는 역할을 하는 필드 ex) 학번 각 상황에서 가장 효율적인 정렬 알고리즘을 선택하여야 함 효율성의 기준 = 비교 연산의 횟수 + 이동 연산의 횟수 ● 효율성과 복잡성 단순하지만 비효율적인 정렬 알고리즘 (자료 개수가 적을 때 사용) - 삽입 정렬, 선택 정렬, 버블 정렬 등 복잡하지만 효율적인 정렬 알고리즘 - 퀵 정렬, 히프 정렬, 합병 정렬, 기수 정렬, 권정열 등 ● 내부와 외부 정렬 내부 정렬 - 정렬 전 모든 데이터가 메인 메모..

04 void prim(GraphType *g, int s){ int i,u,v; for(u=0; un; u++){ distance[u] = INF; } distance[s]=0; for(i=0; in; i++){ u = get_min_vertex(g->n); selected[u] = TRUE; // 04 문제 프린트문 시작 printf("selected[]= "); for(int j=0;jn;j++){ printf("%d ",selected[j]); } printf("\n"); printf("distance[]= "); for(int j=0;jn;j++){ printf("%d ",distance[j]); } // 04 문제 프린트문 종료 if(distance[u]==INF) return; printf(..

11.4 최단 경로 ● 최단 경로(shortest path): 정점 i와 j를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로 - DIjkstra 알고리즘은 하나의 시작 정점에서 다른 정점까지의 최단 경로를 구한다. - Floyd 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 경로를 구한다. 가중치는 가중치 인접 행렬에 저장돼 있고 u와 v사이에 간선이 없다면 INF가 저장된다. * 인접행렬에서는 간선이 없으면 인접 행렬의 값이 0인 반면 가중치 인접 행렬에서는 실제 가중치가 0일 수 있어서 0의 값이 간선이 없음을 나타내지 못한다. 따라서 INF가 간선이 없음을 나타낸다. 11.5 Dijkstra의 최단 경로 알고리즘 ●DIjkstra 알고리즘: 하나의 시작 정점으로부터 모든 다른 정..

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 가장 최근에 들어온 데이터에 우선순위를 부여하면 스택을, 가장 먼저 들어온 데이터에 우선순위를 부여하면 큐를 구현할 수 있는 등 적절한 우선순위만 부여하면 여러 일반적인 자료구조를 구현할 수 있기..