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초정도 걸린다고 생각 - 시간복잡도)
'⚖️Algorithm' 카테고리의 다른 글
[코딩테스트] 자주 사용하는 함수(조합/순열/중복조합/중복순열) c++ (0) | 2022.11.03 |
---|---|
[Java] 코딩테스트 함수 (0) | 2022.10.27 |
[SQL] 코딩테스트 준비 (0) | 2022.10.20 |
[Algorithm] 프로그래머스 - 여행경로 (C++) (0) | 2022.10.15 |
[java] 지식 (0) | 2022.09.23 |