CS/알고리즘4 [알고리즘] 여러가지 정렬과 시간복잡도 (선택정렬 / 삽입정렬 / 버블정렬 / 퀵정렬 / 힙정렬 / 합병정렬) 선택정렬 맨 앞에서부터 차례대로 정렬하는 방법 주어진 리스트 중에 최소값을 찾고 그 값을 맨 앞부터 차례대로 에 위치한 값과 교체하는 방식 시간복잡도 : O(N^2) 삽입정렬 맨 앞에서부터 차례대로 정렬하는 방법 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교해서 현재 선택된 숫자의 위치를 찾아 삽입해주는 방식 시간복잡도 : O(N^2) 버블정렬 첫번째 원소부터 인접한 원소끼리 비교하면서 계속 자리를 교환하면서 맨 끝부터 정렬하는 방식 시간복잡도 : O(N^2) 합병정렬 작은 단위로 잘게 쪼개서 작은 단위부터 정렬해서 정렬된 단위들을 계속 병합해가면서 정렬하는 방식 시간복잡도 : O(NlogN) 퀵 정렬 처음 하나의 피봇(Pivot)을 정해서 이 피봇보다 작은 값은 왼쪽, 큰 값은 오른쪽에 위치시킨 뒤.. 2021. 10. 21. [알고리즘] MST - 프림 알고리즘 (Prim Algorithm) 복습 Spanning Tree 그래프 내의 모든 정점을 포함하는 트리를 의미한다. Spanning Tree의 특징 Tree의 특수한 형태로 모든 정점이 연결되어 있어야 한다. 하나의 그래프에 여러개의 스패닝 트리가 존재할 수 있다. 사이클이 존재하면 안된다. N개의 정점을 정확히 N-1개의 간선으로 연결해야한다. Minimum Spanning Tree (MST) 사용된 간선들의 가중치 합이 최소인 Spanning Tree를 의미한다. 프림 알고리즘 ( Prim Algorithm) 무방향 그래프가 주어졌을 때 최소 스패닝트리 (MST)를 찾는 대표적인 알고리즘으로 시작 정점을 기준으로 가중치가 가장 작은 간선과 연결된 정점을 선택하며 신장 트리를 확장 시킨다 동작 방법 1. 임의의 정점을 선택 (어떤 정점.. 2021. 10. 20. [알고리즘] 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 사용하는 특징을 가지며, 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있다. 작동 과정 0. 모든 노드의 최소비용을 INF로 초기한다. 1. 시작 노드를 설정하고, 해당 노드의 비용을 0으로 해준다. 2. 시작 노드를 기준으로 각 노드의 최소 비용을 저장한다. 3. 방문하지 않은 노드 중에 가장 비용이 적은 노드를 선택한다. 이 때, 비용이 같은 노드가 여러개 있다면 맨 앞에 있는 노드를 선택한다. 4. 해당 노드를 거쳐서 특정한 노드를 가는 경우를 고려하여 최소 비용을 갱신한다.. 2021. 9. 17. [알고리즘] MST - 크루스칼 알고리즘 (Kruskal Algorithm) Spanning Tree 그래프 내의 모든 정점을 포함하는 트리를 의미한다. Spanning Tree의 특징 Tree의 특수한 형태로 모든 정점이 연결되어 있어야 한다. 하나의 그래프에 여러개의 스패닝 트리가 존재할 수 있다. 사이클이 존재하면 안된다. N개의 정점을 정확히 N-1개의 간선으로 연결해야한다. Minimum Spanning Tree (MST) 사용된 간선들의 가중치 합이 최소인 Spanning Tree를 의미한다. MST의 특징 간선의 가중치의 합이 최소여야한다. Spanning Tree의 특징을 가져야한다. MST의 구현 방법 대표적인 MST알고리즘은 크루스칼과 프림 알고리즘이 있다. 이번시간엔, 크루스칼에 대해서만 설명할 것이다. 크루스칼 알고리즘(Kruskal Algorithm) 모든.. 2021. 9. 15. 이전 1 다음
