정렬(Sorting) 알고리즘 정리
면접에서 탈탈 털린 후 작성한 정렬 관련 알고리즘을 총정리 1. Bubble Sort (거품 정렬) 1.1. 동작 과정 1.2. 복잡도 1.3. Python 구현 2. Selection Sort (선택 정렬) 2.1. 동작 과정 2.2. 복잡도 2.…
최소 신장 트리(Minimum Spaaning Tree) 알고리즘
1. 개요 신장 트리(Spanning Tree)는 그래프 내의 모든 노드를 포함하는 트리를 의미하며, **최소 신장 트리(Minimum Spanning Tree)**란 간선의 가중치 합이 최소가 되는 신장 트리를 말한다. 최소 신장 트리는 Greedy…
이진탐색(Binary Search) 알고리즘
1. 개요 정렬된 데이터에서 검색 범위를 줄여 나가면서 목적 값을 찾는 알고리즘이다. 데이터가 정렬되어 있을 경우, 데이터를 크기가 같은 두 부분으로 나누고 유효한 데이터집합을 선 1.…
동적 계획법(Dynamic Programming) 알고리즘
…
깊이 우선 탐색(Depth-First Search) 알고리즘
1. 개요 상태공간이나 그래프를 출발점에서 시작하여 모든 리프노드까지 순서대로 탐색하는 완전탐색 기반의 알고리즘이다. 1.…
너비 우선 탐색(Breadth-First Search) 알고리즘
1. 개요 상태공간이나 그래프를 출발점으로부터 가까운 순으로 탐색해가는 완전탐색 기반의 알고리즘이다. 1.…
다익스트라(Dijkstra) 알고리즘
1. 개요 음의 가중치가 없는 그래프의 한 노드에서 다른 모드 노드까지의 최단거리를 각각 구하는 알고리즘. 대표적으로 사용되는 그리디 알고리즘이다.…
백트래킹(Backtracking) 알고리즘
1. 개요 상태공간이나 그래프의 노드를 모두 탐색하는 완전탐색 기반의 알고리즘이다. 다만, 가지 치기를 통해 탐색할 필요성이 없는 노드(상태)들을 탐색 대상에서 제외함으로써 효율을 높인다.…