Dijkstra 알고리즘 다익스트라(Dijkstra) 알고리즘은 방향성을 가지는 그래프에서 최단거리를 구할 때 자주 쓰인다. 방향성을 가지는 그래프란 A에서 B노드로 이동은 가능하지만, B노드에서 A노드로는 이동할 수 없는 경우가 있는 그래프를 말한다. 즉, 노드 간의 연결된 간선이 방향과 거리 비용을 가지고 있고, 시작 노드에서 다른 노드들까지의 최단거리 비용을 구할 때 사용할 수 있다. Process 1. 거쳐 갈 혹은 시작할 노드를 방문 후 방문 처리한다. 2. 방문한 노드에서 이동할 수 있는 노드들을 탐색한다. 3. 탐색된 노드들의 계산된 거리 비용이 현재까지 저장된 최단거리보다 적을 경우 최단거리를 갱신한다. 4. 최단거리가 갱신된 노드들 중 가장 적은 거리를 가지는 노드로 이동 후 방문 처리한..

Quick Sort란? 이름에서도 보이듯이 빠른(Quick) 정렬이다. 퀵 정렬의 메커니즘은 크게 다음과 같다. 하나의 리스트를 pivot(피벗)을 기준으로 두 개의 부분리스트로 나누어 하나는 pivot보다 작은 값들의 부분리스트, 다른 하나는 pivot보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위처럼 재귀적으로 수행하여 정렬하는 방법이다. 알고리즘의 '분할 정복(Divide and Conquer)'을 기반으로 정렬되는 방식이다. 다만, Merge Sort(병합 정렬)과 다른 점은 병합정렬의 경우 하나의 리스트를 절반으로 나누어 분할 정복을 하고, Quick Sort(퀵 정렬)의 경우 pivot(피벗)의 값에 따라 pivot보다 작은 값을 갖는 부분리스트와 pivot보다 큰 값..

Insertion Sort란? 손 안의 카드를 정렬하는 방법과 유사하다. Insertion Sort는 Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘이다. Insertion Sort는 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘이다. 최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다. Process (Ascending) 정렬은 2번째 위치(index)의 값을 temp에 저장한다. temp와 이전에 있는 원소들과 비교하며 삽입해 나간다. '1'번으로 돌아가 다음 위치(index)의 값을 temp에..

Bubble Sort란? Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다. 이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다. Process (Ascending) 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 ..