Algorithm

해시 테이블(Hash table) 해시 테이블은 흔히 해시라고도 불리며, 저장 또는 검색 등에서 자주 사용되는 자료 구조로, 간단하게는 {key: value}의 형태로 데이터를 저장하는 자료 구조이다.

완전탐색은 간단하게 말해 가능한 모든 경우의 수를 다 확인하여 정답을 찾는 방법이다. 무식하게 정답을 찾는다고 하여 Brute force라고도 부르며, 직관적이어서 이해하기 쉽고 문제의 정확한 결괏값을 얻어낼 수 있는 가장 확실하면서도 기초적인 방법이다.

그리디 알고리즘은 간단히 설명하면 "매 선택에서 현재 당장 최적인 답"을 선택함으로써 전체 문제에 대하여 적합한 결과를 도출하는 알고리즘이다.

원하는 데이터를 찾기 위한 탐색 알고리즘 중 '그래프'를 탐색하는 대표적인 방법으로 깊이 우선 탐색(Depth-First Search, DFS)과 너비 우선 탐색(Breadth-First Search, BFS)이 있다.

'그래프' 그래프는 정점(Vertex)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료 구조로 각 정점이 간선을 통해 연결되어 있으면 이를 '인접했다(adjacent)'고 표현한다.

우선 힙에 대해 이해하기 전에 '완전 이진 트리' 자료 구조에 대해 알고 있어야 한다(이진 트리 자체에 대해서는 다음에 다루도록 하자).

동적 계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이는 분할 정복(Divide and conquer)과 비슷하지만, 한 가지 큰 차이는 '작은 문제의 중복이 발생하지 않도록 한다'는 것이다.

이진 탐색은 정렬된 일련의 값들이 주어지고, 그 값들 중 원하는 값을 찾는 알고리즘이다.

유니온-파인드 알고리즘은 그래프의 연결 여부를 확인하는 알고리즘으로, 노드를 연결하는 간선들의 정보가 주어졌을 때 특정 노드 두 개가 서로 연결되어 있는지, 즉 같은 그래프에 속하는지를 판별하기 위한 알고리즘이다.

크루스칼 알고리즘은 '최소 신장 트리'를 찾아내기 위한 알고리즘이다. 따라서 '신장 트리'와 '최소 신장 트리'가 무엇인지부터 이해해야 한다.