다익스트라 알고리즘이란? 다익스트라 알고리즘은 하나의 시작 지점으로부터 모든 다른 지점까지의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘은 기본적으로 그리디 알고리즘 으로 분류된다. '매번 경로의 길이가 짧은 노드를 선택하는 과정'을 반복하기 때문이다. 다익스트라 알고리즘의 과정 시작 정점을 설정하고, 시작 정점의 거리 값을 0으로 설정한다. 시…

BFS에 대해 알아보기 전에 우선 그래프(graph), 큐(queue)에 대한 이해가 필요하다. 그래프에 대한 설명은 [자료구조] 그래프(Graph)란? , 큐에 대한 설명은 [자료구조] JavaScript로 구현하는 큐 에 자세히 정리해두었다. BFS란? BFS(Breadth First Search) 는 너비 우선 탐색이라고 하며 시작 노드로부터 가…

dfs에 대해 알아보기 전에 우선 그래프에 대한 이해가 필요하다. 그래프에 대한 설명은 여기 에 자세히 정리해두었다. DFS란? DFS(Depth-First-Search) 는 깊이 우선 탐색 이라고 하며 그래프에서 깊은 부분을 우선으로 탐색하는 알고리즘이다. DFS는 트리에서 생각하면 이해하기 쉽다(트리도 그래프의 일종이다). 트리를 탐색할 때 시작 …

이진 탐색이란? 이진 탐색(binary search) 은 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 이진 탐색은 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위일 때는 사용할 수 없지만, 정렬된 데이터에서 매우 빠르게 데이터를 찾을 수 있다. 이진 탐색은 실제로 우리가 일상생활에서 많이 이용하고 있는 방법…

병합 정렬(Merge Sort)이란? 병합 정렬(Merge Sort) 은 분할 정복 기법(Divide and Conquer) 과 재귀 용법 을 활용한 정렬 알고리즘이다. 병합 정렬은 정렬할 원소 목록을 원소가 하나 밖에 남지 않을 때까지 절반으로 잘라 비슷한 크기의 두 부분으로 계속 나눈다. 정렬할 때는 각 절반의 가장 작은 요소를 비교하여 수행된다.…

퀵 정렬이란? 퀵 정렬은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 알고리즘이다. 퀵 정렬은 병합 정렬과 비슷하게 전체 데이터 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵 정렬하는 분할 정복법(Divide-and-Conquer) 을 사용한다. 그러나 퀵 정렬은 병합 정렬과 다르게 데이터 리스트를 비균등하게 분할한다. 퀵 …

삽입 정렬(Insertion Sort)이란? 삽입 정렬은 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉬운 알고리즘이다. 삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬(Insertion Sort) 이라고 한다. 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬 되어 있을 때 훨씬 효율적이다. 선택 정렬은 현재 …

선택 정렬(Selection Sort)이란? 선택 정렬의 원리 정렬되지 않은 원소 중 가장 작은 원소를 찾아 정렬된 요소의 끝에 배치한다. 즉, 배열의 요소 중에서 최소값을 발견한 다음, 이 최소값을 배열의 첫번째 요소와 교환환다. 첫번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두번째 요소와 교환한다. 이 과정을 배열이 정렬될 …