Computer Science/자료구조&알고리즘12 [그래프] 최소 신장 트리(Minimum spanning tree) 최소 신장 트리(Minimum Spanning Tree) 신장 트리(spanning)란? : 그래프 G를 구성하는 부그래프로서 G의 모든 정점을 포함하는 그래프. 최소 신장 트리란, 이러한 신장 트리들 중에서 에지의 가중치의 합이 최소인 신장트리를 말한다. 파란색으로 표시된 에지로 연결된 노드로 구성된 그래프가 위 그래프의 최소 신장 트리이다. 대표적인 응용 문제로는 각 도시를 연결하는 도로를 짓는데 드는 최소 비용 구하기 등이 있다. 최소 신장 트리의 성질 최소 신장 트리의 중요한 특징 세 가지. 1.트리성질 최소 신장 트리는 트리이기 때문에 당연히 트리가 가지는 성질을 똑같이 갖는다. 트리가 갖는 성질에는 다음과 같은 것이 있다. 노드의 수가 N개이면 에지의 수는 (N-1)개이다. 에지 하나를 삭제하.. 2021. 9. 15. [그래프] 다익스트라 알고리즘 (Dijkstra algorithm) 다익스트라 알고리즘 에지에 가중치가 있는 그래프(weighted graph)에서 최단 경로를 찾는 알고리즘 에지의 가중치가 양수일때만 사용 가능하다. 시작 노드 S로부터 다른 모든 노드까지의 최단 경로를 찾는다. 기본 원리 필요한 자료구조 노드 사이의 관계를 표현할 그래프: graph 시작 노드로부터 각 정점까지의 거리를 기록할 배열: distance 최단 경로가 확정된 노드를 꺼내올 최소힙: min_heap 우선 시작 노드를 제외한 모든 노드의 비용을 가장 큰 값(이를테면, 무한대)으로 초기화한다. 시작 노드를 최소힙에 넣는다. 최소힙에서 노드를 꺼낸 후 인접한 노드를 확인한다. 이때, 인접한 노드로 이동하는 비용(현재까지의 비용+이동하는데 드는 비용)이 해당 노드에 기록되어있는 값보다 작다면? 값을 .. 2021. 7. 27. [정렬] 퀵정렬 (Quick Sort) 앞에서 살펴본 선택 정렬, 삽입 정렬, 버블 정렬은 모두 구현은 간단하지만 느린 정렬 알고리즘이었다. 이번 글에서 살펴볼 퀵 정렬은 가장 많이 쓰이는 정렬 알고리즘이며 분할과 정복을 기반으로 하는 알고리즘이다. 평균적인 시간 복잡도는 O(NlogN)이다. 기본 아이디어 우선 배열 안에서 임의의 요소를 고른다. 이 요소를 피벗(pivot)이라고 부른다. 설명을 위해 중간에 위치한 원소를 피벗으로 잡았지만, 아무 원소나 잡아도 상관없다. 이 피벗을 선택하는 방법에도 여러 알고리즘이 있다. 가장 왼쪽의 요소를 피벗으로 삼는 방법도 있고, 랜덤으로 선택하는 방법도 있고, 또 가장 오른쪽의 요소를 피벗으로 삼는 방법도 있는데, 최종적인 성능은 모두 비슷하다. 피벗을 잡았으면, 배열을 순회하면서 피벗보다 작은 쪽과.. 2021. 7. 27. [정렬] 삽입정렬(Insertion Sort) 특징 구현이 간단하다 제자리 정렬이다 안정 정렬이다. 시간 복잡도가 O(n^2)으로 느리다. 기본 아이디어 i는 1부터 시작하여 n-1까지 늘려간다. array[0]부터 array[i-1]까지 정렬되어 있을 때, array[i]를 포함하여 정렬한다. array[i]를 뒤에서부터 순차적으로 array[i-1], array[i-2] ... 과 비교하다가 자기보다 작은 숫자가 나오면 그 뒤에 삽입한다. 아래 영상 참고 www.youtube.com/watch?v=OGzPmgsI-pQ 비교연산은 1 + 2 + 3 + ... + (n-1) 회 일어나고, 스왑 연산의 횟수도 비교 연산과 같으므로 시간 복잡도는 O(n^2) 파이썬 코드 def insertion_sort(array): for i in range(1, l.. 2021. 3. 28. [정렬] 선택정렬 (Selection Sort) 특징 가장 기본적인 정렬 알고리즘이며 구현이 쉽다. 제자리 정렬 알고리즘이다. 불안정 정렬 알고리즘이다. 시간 복잡도가 O(n^2)으로 상당히 느리다. 기본 아이디어 배열을 순회하며 최소값을 찾는다. 최소값을 찾으면 배열의 가장 첫 인덱스에 있는 값과 자리를 바꾼다. (최대값을 찾을 수도 있다. 이때는 가장 뒤에 있는 값과 자리를 바꾼다.) 다시 배열을 순회하며 다음 최소값을 찾는다. 최소값을 찾으면 두 번째 인덱스에 있는 값과 자리를 바꾼다. 원소가 하나 남을 때까지 위 과정을 반복한다. 원소가 들어갈 자리는 이미 정해져 있고, 그 자리에 넣을 원소를선택하는 알고리즘 의사 코드 Algorithm selection_sort(array) input: array output: sorted array for .. 2021. 3. 26. [정렬] 버블정렬 (Bubble Sort) 특징 구현이 쉽다. 제자리 정렬이다. 안정 정렬이다. 시간 복잡도가 O(n^2)으로 느리다. 스왑 연산이 많이 일어나기 때문에 굉장히 비효율적이다. 기본 아이디어 배열을 순회하면서 서로 인접한 두 원소를 비교한다. 만약 더 큰 원소가 앞쪽에 있다면 두 원소의 자리를 바꾼다(오름차순 기준). 만약 마지막까지 도달했는데 스왑이 한번도 일어나지 않았다면, 모든 원소가 정렬 상태에 도달한 것으로 판단할 수 있다. 이때는 연산이 끝나지 않았음에도 강제로 연산을 종료함으로써 수행시간을 조금 더 줄일 수 있다. 의사코드 Algorithm bubble_sort(array) input: array output: void n = length of array for i = n-1 to 2 by -1 do sorted = T.. 2021. 3. 11. 이전 1 2 다음
