따뜻한 베지밀

그래프에서 최단 거리를 구할 때 자주 쓰이는 알고리즘이다. 벨만-포드 알고리즘의 장점부터 먼저 알아보자. 1. 거리의 가중치가 음수여도 사용이 가능하다. 2. 음수 사이클 여부의 존재를 알 수 있다. 위의 두 가지만 봐도 벨만포드 알고리즘의 실질적 필요성을 느낄 수 있다. 왜냐면 전에 배운 다익스트라 알고리즘은 음의 가중치가 있으면 사용이 불가능했기 때문이다. 그럼 작동과정을 살펴보자. 작동 과정 1. 시작 노드부터 "노드와 연결된 모든 간선"을 탐방하면서 데이터를 갱신한다. 2. 그 다음 노드와 연결된 모든 간선을 탐방하면서 데이터를 갱신한다. 3. 그 다음 노드의 다음노드와 연결된 모든 간선을 탐방하면서 데이터를 갱신한다. 4. 반복한다. 되게 간단하다. 처음 노드에 연결되어있는 모든 간선을 확인하고..

그래프에서 최소 비용을 탐색하는 알고리즘으로는 다익스트라 알고리즘, 벨만 포드 알고리즘, 플로이드 와샬 알고리즘, SPFA 알고리즘 등이 있다. 이 글에서는 다익스트라 알고리즘에 대해 다룬다. 다익스트라 알고리즘은 정해진 노드에서 다른 모두의 노드까지 최소 비용을 구하는 알고리즘이다. 다익스트라는 Greedy하게 작동한다고 생각하자. 작동 과정 1. 정해진 노드가 들어가있는 모든 간선 중에서 제일 비용이 낮은 간선을 선택하여 다음 노드를 활성화 시킨다. 2. 정해진 노드와 다음 노드가 포함되어 있는 모든 간선 중에서 제일 비용이 낮은 간선을 선택하여 또다른 노드를 활성화 시킨다. 3. 이를 계속해서 반복한다. 다익스트라는 생각보다 간단하다. 단순하게 "활성화 되어 있는 간선 중 제일 비용이 낮은 간선"을..

JAVA 라이브러리의 (java.util.Array.sort)가 사용하는 알고리즘이다. 먼저 퀵 정렬에 대해서 모르면 이 글을 읽기전에 퀵 정렬의 개념을 공부하고 이 글을 읽는것을 추천한다. Arrays.sort가 구현된 모습은 블로그에서 얘기해 주셨다. Merge Sort는 시간 복잡도 O(N logN)을 가지지만, 실제로는 느린 모습을 보여 자주 쓰이지 않게 되었다. 사람들은 Sort알고리즘을 더 발전시킨 Dual-Pivot Quick Sort와 Tim Sort를 사용한다. Dual-Pivot Quick Sort는 삽입 정렬(Insertion Sort)와 Quick Sort를 합친 것이고, Tim Sort는 Insertion Sort와 Merge Sort를 합친 것이다. 그 전에 하나 확인하고 넘어가..

Merge Sort는 분할해서 정렬하는 대표적인 알고리즘 중 하나이다. Quick Sort는 최악의 경우 시간 복잡도 O(N^2)이 되는 반면, Merge Sort는 최악의 경우에도 시간복잡도가 O(N * logN)을 유지한다. 하지만, 실제로 O(N * logN)인 상황에서는 Quick Sort가 제일 빨라서 최악의 경우를 만나지 않게끔 코드를 짠다. 이는 다른 게시글에 업데이트 하겠다. Merge Sort의 아이디어는 "반으로 먼저 쪼개고, 정렬한다." 반으로 쪼개는 것은 어렵지 않다. 다음과 같이 수행해보자. 기존에 {35, 13, 2, 7, 11, 44, 12} 배열이 있으면 반으로 계속해서 쪼개 나가는 것이다. 3단계에 걸쳐 모든 부분집합의 크기를 1로 만들었다. 그렇다면 반대로 부분집합들을 모..