[코딩테스트] 알고리즘 정리

1. 알고리즘 설계 기법

- 구현

- 그리디 : 탐욕스럽게 당장 최적해를 쫓다보면 최적해가 나오는 알고리즘 ex) 동전 문제

- 완전탐색(브루트포스) : 무식한 알고리즘. 즉, 모든 경우의 수 대입 ex) 소수 찾기

- 이진탐색 : 이미 정렬되어 있는 문제, 결정 문제로 치환 가능 

- 동적계획법(DP)  : 최적해 구하기 위해 메모

2. 정렬

3. 그래프

1) 그래프 순회

- DFS : 깊이 우선 탐색

- BFS : 넓이 우선 탐색

 

2) 최단 경로 

- BFS : 가중치가 1인 문제에서의 최단 경로 찾기

- 다익스트라 : 시작 정점 하나로부터 최단 경로 찾기

- 플로이드 : 모든 정점에서 최단 경로 찾음 O(N^3) 구현 간단

 

3) 최소 신장 트리(MST)

- 크루스칼 : 간선 선택, Union-Find로 구현

 

4) 순서에 따라 (선수강)

- 위상정렬

 

4.  해시(key-value 쌍)

- 해시 : 탐색 O(1), unordered_map 사용, 해쉬 충돌 주의

5.  힙 

6. 기타

- 백트래킹 : 뒤로 돌아가서 다른 시도 해보는 알고리즘

- 비트마스크 : 입력값이 0과 1로 이루어질 때 빠른 탐색 가능

- 순열 & 조합

- 투포인터

 

(📍 연산 횟수가 1억번 정도일 때 약 1초정도 걸린다고 생각 - 시간복잡도)