[이것이 코딩 테스트다] 목차 정리

 

1. 그리디 ( =탐욕법)

: 현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘

> 그리디 알고리즘 유형 문제는 매우 다양하기에 암기만 한다고 해서 

문제를 다 풀 수 있는 건 절대 아니다

 

* 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이기에

문제에 알게 모르게 기준을 제시해준다

(예를 들면, 가장 큰 순서대로 또는 가장 작은 순서대로 ...)

 

이 기준들은 정렬 알고리즘을 사용할 때 만족시킬 수 있으므로

주로 그리디 알고리즘은 정렬 알고리즘과 짝을 지어 문제가 출제 된다.

 

---

2. 구현

: 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하는 방법이다.

구현이란 머릿속에 있는 알고리즘을 소스 코드로 바꾸는 과정을 의미함

완전 탐색, 시뮬레이션 유형을 모두 구현 유형으로 묶어서 다룬다.

 

완전 탐색

: 모든 경우의 수를 주저 없이 다 계산하는 방법

시뮬레이션 유형

: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제

 

---

3. DFS/BFS

: 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘

DFS (Depth-First-Search) 

> 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

 

- BFS ( Breadth First Search)

> 너비 우선 탐색이라고 하며, 가까운 노드부터 탐색하는 알고리즘이다.

선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다.

 

---

4. 정렬

: 연속된 데이터를 기준에 따라서 정렬하기 위한 알고리즘

> 데이터를 특정한 기준에 따라서 순서대로 나열하 알고리즘이다.

참고로 정렬 알고리즘은 이진 탐색의 전처리 과정이다.

(ex. 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 ...)

 

 

---

5. 이진 탐색

: 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘

> 내부의 데이터가 정렬되어있어야만 사용이 가능하다.

이진 탐색은 코딩 테스트에서 단골로 나오니까 가급적 외워두기!

 

 

---

6. 다이나믹 프로그래밍 (동적 계획법)

: 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘

> 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시가 피보나치 수열이다.

 

---

7. 최단 경로

: 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘

길 찾기 문제라고 불린다.

(최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 

플로이드 워셜,

벨만 포드 알고리즘 이렇게 3가지가 있다.

그 중 다익스트라와 플로이드 워셜 알고리즘이 코테에 자주 나옴)

 

---

8. 그래프 이론

: 코테에서 자주 등장하는 기타 그래프 이론 공부하기

> 앞에서 다루지 않은 그래프 알고리즘을 추가로 다룬다.