알고리즘 학습 요약

-탄탄한 기본기를 갖출 것

총 9개의 기본 알고리즘을 내면화할것이다.

1. DFS

2. BFS

3. Quick Search

4. Binary Search

5. Dijkstra

6. FloydWarshall

7. Disjoint Sets

8. Kruskal

9. Topology Sort

상술한 알고리즘을 기본 형식으로 작성하는 데에는 막힘이 없어야 한다.
실제 문제에서는 위의 알고리즘을 적절하게 응용하는 것을 요구한다.

특정 알고리즘을 활용하는 문제임을 간파했음에도 불구하고 구현능력이 떨어져서 빠르게 문제를 풀어내지 못하는 상황은 절대 없어야 한다.

-알고리즘별 포인트

1. DFS :
재귀함수를 사용한다. 재귀 깊이 제한으로 인해 오류가 발생하는것에 주의. 
2. BFS :
큐 자료구조를 이용한다. 일반적으로 DFS보다 작동속도가 빠르다.

*DFS와 BFS는 기본 형식으로 알고리즘을 작성하더라도 그래프가 Adjecency List로 주어지는지, Adjecency Matrix로 주어지는지에 따라 조금씩 코드가 달라져야한다.

*DFS는 현재 노드에 대해 방문을 체크하지만 BFS는 자식 노드에 대해 방문을 체크함에 주의하자.

3. 퀵정렬 :
코드를 깔끔하게 작성할 때 신경쓸 포인트가 많다. 대소 비교 연산자에 등호가 들어가는지, pivot의 좌 우에 원소가 없을때에도 에러가 발생하지는 않는지, 인덱스 오류가 발생하지 않는지에 주의해야 한다.
4. 이진탐색 :
코드를 깔끔하게 작성할 때 신경 쓸 포인트가 마찬가지로 많다. 또한 이진탐색을 쓰면 풀 수 있는 상황임을 알아차리는 것 또한 중요하다.
5. 다익스트라 :
힙 자료구조를 활용한다. 여러 방식으로 변형이 가능하기에 기본 형식은 아주 시원시원하게 작성할 수 있어야 한다.
6. 플로이드 워셜 :
구현은 쉬우나 시간복잡도가 O(N^3)임에 주의하자
7. 서로소 집합 :
경로압축법을 활용하는 방식으로 빠르게 구현할 수 있도록 숙달하자
8. 크루스칼 :
힙을 활용한다. 구현도 어렵지 않은듯
9. 위상정렬 :
아직 충분히 공부하지 않았음