서론오늘은 최단거리 알고리즘의 대명사 다익스트라 알고리즘에 대해서 알아보도록 하자. 지루하고 현학적인 이론을 설명하기에 앞서 EBS에서 누구나 다익스트라 알고리즘의 원리에 대해 아주 쉽게 시청각 자료를 곁들여서 설명을 해주었다(영상의 40초부터). 따라서 영상을 먼저 보고 온다면 이해해 큰 도움이 될 것이다.다익스트라를 아주 쉽게 설명해준 EBS의 은혜다익스트라 알고리즘(Dijkstra algorithm)이란?다익스트라 알고리즘은 그래프에서 한 노드에서 모든 노드까지의 최단거리를 구하는 알고리즘이다. 영상을 보면 알다시피 Min distance table(MDT)로 불리는 최단거리배열을 갱신하며 최단거리를 구한다. 다익스트라의 핵심은 노드간의 탐색을 할때 현재 도달할 수 있는 간선의 비용중 가장 비용이 ..

서론이전에 IntroSort에 대한 설명글에서 퀵 정렬(Quick sort)에 대한 슈도코드와 간략한 설명을 다루었다. 이번 글에서는 퀵 정렬에 대한 구체적인 동작 방식과 효율성에 대해서 알아보도록 하자.퀵 정렬(Quick sort)퀵 정렬은 분할 정복(Divide and Conquer) 방식의 정렬 알고리즘이다. 기준이 되는 피벗(Pivot)을 하나 선택하고, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할해가며 정렬을 수행한다. 평균적으로 매우 빠르며($O(n log n)$), 제자리 정렬(추가적인 임시 배열을 사용하지 않음)이기 때문에 공간 효율성도 좋다.Quick sort 과정 (namu wiki) 분할 정복퀵 정렬은 앞서 설명했듯이 분할 정복을 사용해서 피벗을 기준으로 피벗보다 큰쪽, 피벗보..

서론분할 정복(Divide and conquer)은 커다란 문제를 작은 sub 문제로 나눈다음에 그것들을 다시 합쳐서 해결하는 개념이다. 일반적인 분할정복의 시퀀스는 다음과 같다:function solve(problem): if (problem is small enough): // base case return trivial solution else: divide problem into subproblems solve each subproblem recursively combine the results Divide: 문제를 더 작게 쪼갠다.Conquer: 하위 문제를 재귀적으로 해결한다.Combine: 하위 문제의 답을 바탕으로 최종 결과를 얻..