알고리즘 (5) 썸네일형 리스트형 [Algorithm] 다익스트라(Dijkstra) 1. 개요 - 단일 출발지 최단거리 알고리즘 - 가중 그래프에서 사용할 수 있다. - 구현에 우선 순위 큐가 사용되며, BFS와 거의 유사하다. 2. 설명 다익스트라 알고리즘의 핵심 개념은, 각 정점 간 최단 거리를 구하면, 결국 출발지를 기준으로 모든 정점에 대한 최단 거리를 구할 수 있다는 것이다. 이는 BFS과 같이 너비 탐색을 하며, 탐색 시간을 줄이기 위해 "우선 순위 큐"를 사용하게 된다. - 초기 각 정점의 최단 거리는 모두 무한 값으로 설정이 되어야 한다. - 우선 순위 큐에 들어가는 정보는 (시작점 - 현재 정점 까지의 거리, 현재 정점)과 같다. - 시작 정점은 우선 순위 큐에 넣을 때 거리 0으로 지정하여 넣는다. - 시작 정점의 최단 거리는 0 이다. 1) 동작 절차 다익스트라 알고.. 퀵 정렬 (Quick Sort) 퀵 정렬(Quick Sort) -하나의 요소를 고른 후(Pivot) 기준값보다 작은 요소는 앞에 위치 시키고, 큰 요소는 뒤에 위치시키는 정렬- 다른 말이 필요없다. 무려 퀵 정렬이다. 이름(Quick)에서도 알 수 있듯여러 정렬 알고리즘 중에서 가장 빠르다.평균 시간 복잡도는 O(n) 최악 시간복잡도는 O(n^2)이다. "그렇다면 퀵만 쓰면 되는 것을, 왜 여러 정렬을 쓰는거죠?" 물론, 퀵이 빠르다만, 프로그래밍이라는 것은 Case By Case.상황에 맞춰서 적절한 알고리즘을 사용해야 하는 것이다. 퀵 정렬은 재귀적 구조이므로, 재귀의 이해가 문제없다면금방 이해를 할 수 있으리라 생각한다. 대강 알고리즘의 원리는 이렇다.1. 기준값(Pivot)을 정한다.(Pivot을 정하는 기준은 자기 마음이다)2.. 삽입정렬 (Insertion Sort) 삽입 정렬(Insertion Sort) -이미 정렬 돼있는 배열에 추가 요소를 적절한 위치(?)에 삽입(Insertion) 하여 정렬하는 방식- 평균 시간복잡도, 최악 시간복잡도 모두 O(n^2)인 느린 알고리즘..다만 구현이 용이하며 인플레이스(in-place) 알고리즘이라 한다. 여기서 "적절한 위치"라는 말은,오름차순이냐 내림차순이냐에 따라 비교하는 조건이 달라질 것인데,그 조건에 맞게 비교하고 교환을 하라는 뜻이다. 또한 "이미 정렬 돼있는 배열"이라는 말은 첫 Loop때 배열의 첫 번째 요소와 두 번째 요소는 무조건 정렬을 시키고이후 Loop 부터는 그 정렬된 배열과 비교하며 교환을 하는 방식이라서 그렇다. -Sample Source- 선택정렬 (Selection Sort) 선택 정렬(Selection Sort) -배열의 요소 중 최댓값 or 최솟값을 골라서(Selection),배열의 가장 끝의 요소와 교환 하는 정렬 - 총 n개의 데이터가 있다면, 교환 횟수는 많아야 n-1번 비교 횟수는 n(n-1) / 2번, 시간 복잡도는 O(n^2)이다.비교 횟수가 버블 정렬과 같다는 특징이 있다. -Sample Source- 버블 정렬 (Bubble Sort) 버블 정렬 (Bubble Sort) -서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 맨 뒤로 보내며 정렬하는 방식- 최악의 경우 시간복잡도는 O(n^2),최선의 경우 시간복잡도는 O(n),평균 시간복잡도는 O(n^2)이다. (시간 복잡도의 개념을 알고 싶다면 위키보다는 이 블로그를 추천한다.) 평균이 O(n^2)인 느린 알고리즘이지만, 병렬 처리에 적합하며 코드가 간단하다. 왜 느리냐 하면은, 모든 요소에 대해 비교하고, 해당 되는 요소에 교환을 하기 때문. 데이터들을 교환 시킬 때 거품이 수면 위로 올라오는 것 같다 하여버블 정렬이라고 한다.(실제로 버블정렬 애니메이션을 보면 그렇게 보이는 것 같다) -Sample Source- 이전 1 다음
