유자의 코딩모험

해당 순서에 원소를 넣을 위치는 이미 정해져 있고 어떤 원소를 넣을지 선택하는 알고리즘. 주어진 배열 중에 최솟값을 찾고 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. 시간 복잡도 (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1)/2만큼의 비교가 일어나기 때문에 n개의 주어진 배열을 정렬하는데 O(n^2)만큼의 시간이 걸린다. 최선, 평균, 최악의 경우 시간 복잡도는 O(n^2)로 동일하다. 공간 복잡도 주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되므로 O(n) 장점 알고리즘이 단순하다. 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자..

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘. 가장 큰 값을 배열의 맨 끝에 이동시키면서 정렬하고자 하는 원소의 개수 만큼을 두 번 반복하게 된다. 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 Bubble Sort라 지어졌다고 한다. 구현 시간 복잡도 (n - 1) + (n - 2) + ... + 2 + 1 = n(n-1)/2이므로 O(n^2) 정렬이 되어있든지 안되어있든지 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(n^2)으로 동일하다. 공간 복잡도 주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되므로 O(n) 장점 구현이 매우 간단하고 소스코드가 직관적이다. 추가적인 메모..

플로이드 와샬 알고리즘이란? '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하는 알고리즘 다익스트라 알고리즘과의 차이점 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘으로 가장 적은 비용을 하나씩 선택한다. 하지만 플로이드 와샬 알고리즘은 기본적으로 '거쳐가는 모든 정점'을 기준으로 알고리즘을 수행한다. 알고리즘 위와 같은 그래프가 존재한다고 할 때, D는 각각의 정점이 다른 정점으로 가는 비용을 이차원 형태로 저장해놓은 것이다. 처음에는 위와 같은 상태이다. 이때 무한대는 이동하는 경로가 없다는 뜻이고 자신 자신의 비용은 0이다. D[x][y] = x에서 y로 가는 최소 비용을 의미한다. 거쳐가는 정점을 K라고 하자. X에서 Y로 가는 최소 비용과 X에서 노드 K로 ..