선택 정렬 (Selection Sort) 첫 번째 데이터를 두 번째 데이터 ~ 마지막 데이터까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 데이터를 세 번째 데이터 ~ 마지막 데이터까지 차례대로 비교하여 가장 작은 값을 두 번째 위치에 놓는 과정을 반복해 정렬하는 과정을 말한다. 특징 장점 - 자료 이동 횟수가 미리 결정된다. 단점 - 안정성을 만족하지 않는다. - 같은 값을 같은 데이터가 있는 경우 상대적인 위치가 변경될 수도 있다. 시간 복잡도 비교 - 두 개의 for문이 실행됨 = O(n^2) - 외부 루프 : n-1번 - 내부 루프 : n-1, n-2, n-3,..., 2, 1번 교환 - 외부 루프의 실행 횟수만큼 작업 = O(1) ∴ O(n^2) 정렬 알고리즘 시간 복잡도..
Spanning Tree Spanning Tree = 스패닝 트리 = 신장 트리 그래프 내의 모든 정점을 포함하는 트리로 그래프의 최소 연결 부분 그래프이다. 특징 DFS/BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. 모든 정점들이 연결되어 있어야 하고, 사이클이 포함되서는 안된다. 그래프에 있는 n개의 정점(v)을 정확히 n-1개의 간선(e)으로 연결한다. Minumum Spanning Tree (MST) Spanning Tree 중에서 간선들의 가중치 합이 최소인 트리를 MST라고 부른다. 각 간선의 가중치가 동일하지 않을 때, 단순히 가장 적은 간선을 사용한다고 해서 최소 비용을 얻는 것은 아니다. 특징 간선의 가중치의 합이 최소여야 ..
그래프를 탐색하는 방법에는 크게 2가지로 나눌 수 있는데, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다. 💡 그래프란 ? 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종. 그래프를 탐색한다는 것 = 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문하는 것 깊이 우선 탐색 (DFS, Depth-First Search) : 최대한 깊이 내려간 후, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동 깊이 우선 탐색의 개념 루트 노드(혹은 다른 임의의 노드)에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식. 예를 들어, 미로 찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더이상 갈 수 없게 되면 ..
💡 다익스트라(Dijkstra) 알고리즘이란? 그래프에서 '최소 비용', '최소 거리'를 구해야 하는 경우에 사용하는 알고리즘으로, 그래프 상에서 시작 정점부터 나머지 각 정점까지의 최소 비용인 경로를 찾을 때 유용하게 사용된다. 다익스트라 알고리즘은 그래프의 어느 간선의 가중치라도 음수가 있으면 안된다는 특징이 있다. (가중치에 음수가 있을 시 벨만-포드 알고리즘 이용) 다익스트라 알고리즘을 구현하기 위해서는 다음 과정을 반복하면 된다. 1. 방문하지 않은 정점 중 가장 가중치가 작은 정점을 방문한다. 2. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록된 값보다 작으면 그 거리를 갱신해준다. 예시를 통해 좀 더 자세하게 설명해보겠다. 다음과 같은 그래프가 있다고 하자. 시작 정점은 0번 정..
