리안이와 함께하는 세상

정렬 알고리즘의 성능 비교알고리즘 최선 평균 최악 삽입 정렬O(n) O(n^2) O(n^2) 선택 정렬 O(n^2) O(n^2) O(n^2) 버블 정렬 O(n^2) O(n^2) O(n^2) 쉘 정렬 O(n) O(n^1.5) O(n^1.5) 퀵 정렬 O(nlog 2n)O(nlog 2n) O(n^2) 힙 정렬 O(nlog 2n) O(nlog 2n) O(nlog 2n) 합병 정렬 O(nlog 2n)O(nlog 2n) O(nlog 2n) 기수 정렬 O(dn) O(dn) O(dn) (표 : http://wonjayk.tistory.com/225 )* 안정성 이 있는 정렬 : 같은 값을 가진 데이터의 순서가 정렬 후에도 바뀌지 않고 그대로 유지하는 정렬 ex) 삽입정렬, 버블정렬, 합병정렬, 기수 정렬 1. 삽입(..

: 자신을 가리키는 간선이 없는 경우 제거하고 기록(간선도 같이 사라짐), 반복 > 참 쉽죠잉? > 그래프가 방향을 가진 간선으로 만들어진 경우에만 할 수 있음. > 위상의 순서는 여러가지가 나올 수 있음. 구체적으로 보자면 1. 네트워크 내에서 선행자가 없는 정점들을 정렬. 2. 이 정점들과 이들로부터 나오는 간선들을 네트워크에서 삭제 3. 모든 정점들이 정렬되었거나, 남아있는 정점들이 모두 선행자를 가지고 있어 어떤 정점도 제거할 수 없을 때까지 1.2.를 반복(출처 : 컴퓨터 일반 2017 쪽집게 기출문제집 정답 및 해설) ps. 책에 해설이 매우 잘 나와있음 굿

: 신장트리의 경로에 가중치가 주어져 있을 때, 최소의 비용으로 모든 정점을 연결하는 트리. ※ 신장트리니까 사이클X, n-1개의 경로(간선, 이하 경로라 함)를 가짐 * 최소비용 신장트리를 생성하는 알고리즘 : 크루스칼(Kruskal) 알고리즘, 프림(Prim) 알고리즘 1. 크루스칼 알고리즘(Kruskal's algorithm): 그래프 내에서 최소의 가중치를 가지는 경로를 선택하여 MST를 구성 (MST는 최소비용 신장트리임, 트리 구성중 여러개의 MST가 생기나 결국 하나로 합쳐짐. 신장트리니까!) - 사이클 안됨 (신장트리라고!!) - 이미지에서 볼 수 있듯, 비용이 최소면 사이클이 형성되지 않는 한 무조건 연결(이미지 출처 : http://serverbob.3x.ro/IA/DDU0137.htm..

: 그래프에서 모든 정점을 연결하는 최소의 경로가 있을 때, 이것을 신장트리라 한다. > 정점이 n개 일 때 신장트리의 간선의 개수는 n-1 (n개의 정점을 연결해야 하니까) > 사이클이 있으면 안된다. 그럼 최소의 경로가 아니니까 **(중요) 배 속에 있는 신장과 무관하다 EX)[이미지 펌 : http://cfile22.uf.tistory.com/image/2769543652D9233431A6CD // http://emzei.tistory.com/126 ]

: 각 경로의 레벨을 더한다. (루트의 레벨은 0)Ex) 1레벨의 경로 22레벨의 경로 33레벨의 경로 3 +___________________ 1*2 + 2*3 + 3*3 = 17

: 리스트의 양쪽 끝에서 노드의 삽입과 삭제가 모두 가능한 선형 리스트: 스택과 큐를 복합한 운영방식 ※ 입력제한 데크(Scroll) : 출력은 양방향에서 가능하나, 입력은 한 방향만 가능※ 출력제한 데크(Shelf) : 입력은 양방향에서 가능하나, 출력은 한 방향만 가능