Algorithm

해쉬테이블은 효율적인 탐색을 위한 자료구조로서, key를 value에 대응시킨다.

그래프는 정점과 간선으로 이루어져 있는데 간선을 통해서 모든 정점을 방문하는 것을 그래프를 탐색한다고 한다. 그래프 탐색 알고리즘 중 하나인 깊이 우선 탐색(DFS)에 대하여 알아본다.

그래프 탐색 알고리즘 중 하나인 너비 우선 탐색(BFS)에 대하여 알아본다.

퀵 정렬은 기준값(pivot)을 사용하여 정렬을 한다. 어떤 값을 기준값으로 선정하는지에 따라서 퀵정렬 성능이 달라진다.

합병 정렬은 전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하는 정렬 방식이다.

정순회(Inorder traversal)를 시행하며 마지막으로 검사했던 노드를 저장해두고 다음에 그 다음 노드와 비교한다.

버블정렬과 선택정렬은 구현이 간단하지만 비효율적이다. 둘 다 시간복잡도는 O(n^2)이다.

이진탐색은 정렬된 리스트에만 적용가능하다. 시간복잡도는 O(logn) 이다.

이진탐색트리(Binary Search Tree)는 다음과 같은 속성이 있는 이진트리 자료구조이다. 이진탐색트리를 구현하고 삽입, 삭제, 중위순회(Inorder traversal)를 테스트하였다.

모든 작은 문제들은 한번만 푼다. 따라서 정답을 구한 작은 문제를 어딘가에 메모해둔다.