자료구조21 [자료구조] 1124 12. 정렬 정렬이란? 선택 정렬 삽입 정렬 버블 정렬 셸 정렬 합병 정렬 퀵 정렬 히프 정렬 기수 정렬 정렬 알고리즘의 비교 12.1 정렬이란? 정렬 알고리즘 분류 (1) 단순하지만 비효율적인 방법 vs. 복잡하지만 효율적인 방법 (2) 내부 정렬 vs. 외부 정렬 우리는 내부 정렬만을 다룬다. Space complexity: 새로운 공간이 필요한가? (3) 안정성 (stability) : 나중에도 순서가 유지될 애들은 처음부터 순서를 유지하면서 정렬하는가? ▶ Stable sort: 삽입정렬 (insertion sort): 정렬되지 않은 곳에서 정렬된 곳으로 삽입한다. (정렬된 곳에서 비교한다.) 버블정렬 (bubble sort): 2개의 레코드를 비교해서 순서를 바꾼다. 따라서 한 단계마다 가장 큰.. 2023. 12. 2. [자료구조] 1121 (2) - 12. 정렬 12. 정렬 정렬이란? 선택 정렬 삽입 정렬 버블 정렬 셸 정렬 합병 정렬 퀵 정렬 히프 정렬 기수 정렬 정렬 알고리즘의 비교 12.1 정렬이란? : 데이터들을 특정 순서(오름차순, 내림차순 등)로 정리하는 것 정렬의 대상 : 일반적으로 정렬시켜야 될 대상은 레코드(record)이다. 정렬 알고리즘 개요 출처: 이화여자대학교 이숙영교수님 자료구조 2023. 11. 28. [자료구조] 1121 (1) 11. 그래프(2) 최소 비용 신장 트리 (MST: Minimum Spanning Tree) Kruscal의 MST 알고리즘 Prim의 MST 알고리즘 최단 경로 Dijkstra의 최단 경로 알고리즘 Floyd의 최단 경로 알고리즘 위상 정렬 11.5 Dijkstra의 최단 경로 알고리즘 Dijkstra's 최단경로 프로그램 Dijkstra's 최단경로 알고리즘 복잡도 : 네트워크에 n개의 정점이 있다면, Dijkstra의 최단경로 알고리즘은 주 반복문을 n번 반복하고, 내부 반복문을 2n번 반복하므로, O(n^2)의 복잡도를 가진다. 11.6 Floyd의 최단 경로 알고리즘 Floyd의 최단경로 알고리즘 : 모든 정점과 정점 사이의 최단경로를 찾는다. Floyd의 최단경로 알고리즘 아이디어 A^k[i].. 2023. 11. 28. [자료구조] 1117 11. 그래프(2) 최소 비용 신장 트리 (MST: Minimum Spanning Tree) Kruscal의 MST 알고리즘 Prim의 MST 알고리즘 최단 경로 Dijkstra의 최단 경로 알고리즘 Floyd의 최단 경로 알고리즘 위상 정렬 11.3 Prim의 MST 알고리즘 Prim's MST 프로그램 ▶ Disconnected Graph: Kruskal's MST algorithm: 전체 edge의 weight를 비교하여, edge weight가 작은 것부터 연결하기 때문에, disconnected graph도 처리할 수 있다. Prim's MST algorithm: 이미 MST에 포함된 vertex와 연결된 edge들의 weight만을 비교하기 때문에, disconnected graph에서는 제대.. 2023. 11. 28. [자료구조] 1114 11. 그래프(2) 최소 비용 신장 트리 (MST: Minimum Spanning Tree) Kruscal의 MST 알고리즘 Prim의 MST 알고리즘 최단 경로 Dijkstra의 최단 경로 알고리즘 Floyd의 최단 경로 알고리즘 위상 정렬 11.2 Kruscal의 MST 알고리즘 union-find 알고리즘 : 모든 edge의 weight를 검사해서, 가장 weight가 작은 edge가 사이클을 만들지 않으면, 추가한다. union-find 프로그램 set_init: 자기 자신을 root 노드로 초기화한다. --> parent[i] = -1 set_find: root 노드를 찾는다. set_union: 두 노드가 서로 다른 집합에 속해 있으면(root 노드가 다르면), 합친다. union-find 연.. 2023. 11. 26. [자료구조] 1110 - 11. 그래프(2) 최소 비용 신장 트리 (MST: Minimum Spanning Tree) Kruscal의 MST 알고리즘 Prim의 MST 알고리즘 최단 경로 Dijkstra의 최단 경로 알고리즘 Floyd의 최단 경로 알고리즘 위상 정렬 11.1 최소 비용 신장 트리 (MST: Minimum Spanning Tree) ▶ 신장 트리 (spanning tree) : 그래프 내의 모든 정점을 포함하는 트리 트리: 사이클x ▶ 깊이 우선 탐색 (DFS) 신장 트리 알고리즘 DFS 알고리즘: 모든 정점들을 탐색하여, 만약 그 정점을 방문하지 않았다면, 방문되었다고 표시한다. Spanning tree 알고리즘: 만약 그 정점을 방문하지 않았다면, (v, u)를 신장 트리 간선이라고 표시한다. 최소 비용 신장 트리 (MST: M.. 2023. 11. 26. [자료구조] 1110 깊이 우선 탐색 (DFS) - example ▶ 깊이 우선 탐색 (DFS) : 숫자가 작은 것부터 시작해서, 간선이 있는 숫자들로 내려간다. 그래프 표현 방법 인접 행렬 (adjacent matrix) 방법 인접 리스트 (adjacent list) 방법 출처: 이화여자대학교 이숙영교수님 자료구조 2023. 11. 11. [자료구조] 1107 단순 경로(simple path), 사이클(cycle), 단순 사이클(simple cycle) 단순 경로(simple path): 반복되는 정점이 없는 경로 사이클(cycle): 시작 정점과 종료 정점이 같은 경로 단순 사이클(simple cycle): 시작 정점과 종료 정점이 같고, 반복되는 정점이 없는 경로 (사이클, 단순 경로) 연결 그래프(connected graph), bridge 그래프 탐색 : 하나의 정점(source node)로부터 시작하여, 차례대로, 모든 정점들을 한 번씩 방문한다. (target node를 찾을 때까지) 그래프 탐색 알고리즘 깊이 우선 탐색 (DFS: Depth-First Search) 너비 우선 탐색 (BFS: Breadth-First Search) 깊이 우선 탐색 .. 2023. 11. 10. [자료구조] 1103 - 10. 그래프 (1) 10.1 그래프란? 그래프의 소개 그래프: 객체 사이의 연결 관계를 표현할 수 있는 자료 구조 그래프의 역사 Konigsberg의 다리 문제 (오일러 문제): 임의의 지역에서 출발하여 모든 다리를 단 한번만 건너서 처음 출발했던 지역으로 돌아올 수 있는가? - 'A, B, C, D의 위치가 어떠한 관계로 연결되었는가?' - 지역 = 정점(vertex) - 다리 = 간선(edge) 오일러 경로: 그래프에 존재하는 모든 간선(edge)를 한번만 통과하면서 처음 정점(node)로 되돌아오는 경로 오일러 정리: 모든 정점(node)에 연결된 간선(edge)의 개수가 짝수일 때만 오일러 경로가 존재한다. 그래프로 표현할 수 있는 것들 : 도로, 미로, 선수과목 10.2 그래프의 정의와 용어 그래프의 정의 ▶ G .. 2023. 11. 4. 이전 1 2 3 다음
