코딩 테스트를 위한 최소한의 지식

코딩 테스트를 준비하는데에 있어 필요한 최소한의 지식에 대해서 열거하여 봤습니다.

1. 자료구조

• Linked List(vector, deque, stack, que)
• tree
• heap
• graph

2. 정렬

1. 알고리즘의 성능은 시간복잡도로 나타내고 Big-O 표기법을 따릅니다. 어렵지 않으니 모른다면 반드시 찾아서 공부하는 것이 좋습니다.
2. 아래에 나열 된 알고리즘들은 모두 구현하기 쉬운 편에 속하므로 우선순위를 높게 두고 공부하는 것이 좋습니다. 언젠가 막혀서 공부하게 되는 날이 찾아오게 될 것이기 때문입니다.
3. 만약 헤더파일을 사용할 수 없는 코딩테스트를 본다고 할 때,고급 정렬 알고리즘을 모른다면 시간 내에 문제를 통과하는 것 자체가 불가능합니다.
4. 예외는 존재하지만, 성능이 좋다 == 난이도가 높다 라고 생각하시면 됩니다.

• Bubble sort, Selection sort, Insert sort
  • 매우 기초적인 알고리즘입니다.
  • 모두 평균 시간 복잡도 O(n^2)의 성능을 가집니다.
  • 정렬에 있어서 기본 소양이기 때문에 넣었습니다. 쉬운 만큼 성능이 가장 안 좋은 알고리즘들이기 때문에 웬만하면 쓰지 않는 것이 좋습니다. 성능과 무관하게 간단한 구현을 위해 쓰신다면 그래도 Insertion sort를 사용하는 편이 좋습니다.
• Heap sort, Quick sort, Merge sort 
  • 시간 복잡도 O(n log n)의 성능을 가집니다.
  • 직접 구현을 위해서는 자료구조 heap과 tree에 대한 이해가 필요합니다.
  • 세개 다 하긴 어렵다면 quick sort만이라도 공부하는 것이 좋습니다..
• Radix sort
  • 시간 복잡도 O(dn)의 성능을 가집니다.

알고리즘

• recursion (재귀)
• permutation (순열)
• combinaation (조합)
• DFS: Depth-First Search (깊이 우선 탐색)
• BFS: Breadth-First Search (너비 우선 탐색)
• bitmask
• Dynamic Programming