코테 알고리즘 정리

[코딩테스트 빈출 문제유형] 1. BFS, DFS 2. 구현 / 시뮬레이션 3. DP(Dynamic Programming) 4. Union-Find 5. 그리디 6. 백트래킹 7. 브루트포스 8. 정렬

 

꼭 해야되는거 

dfs : 깊이우선탐색으로 완전탐색을 할때 사용

백트래킹 : dfs에서 더이상 정답이 아니라고 판단되는 부분은 탐색하지 않도록 가지를 치며 탐색하는 방법

bfs : 너비우선탐색으로 완전탐색이나 최단경로를 찾을때 유리

투포인터 : 특정 구간에서 작업을 할때 효율적

누적합 : 구간합을 빠르게 구하기 위한 방법

에라토스테네스의체 : 특정 범위에서 소수판별을 빠르게 할 수 있음

이분탐색 : 시간복잡도를 볼때 n보다 짧게 처리가 되야할때 사용, 정답을 두고 탐색범위를 반절씩 버리면서 탐색

구현 및 시뮬레이션 문제 : 요구사항 구현, 문자열 관련 문제 등

유클리드호제법 : 최대공약수, 최소공배수 구하기

큐, 스택, 힙, 디큐, 해시를 이용한 문제풀이

 

하긴 해야되는거 

다익스트라 : 한 출발점에서 모든 다른지점까지의 최단거리

플로이드와샬 : 모든 지점간의 최단거리를 찾을때 사용

유니온파인드 : 같은 부모에 속한 그래프인지 체크하기 위해 사용

크루스칼 : 최소신장트리를 만들때 사용, 엣지를 정렬하여 연결

프림 : 최소신장 트리를 만들때 사용, 노드를 선택 후 가장 적은 비용을 가진 엣지를 연결

LCS : 최장 공통 부분 수열

LIS : 최장 증가 수열

진법변환 : 2진법, 8진법, 16진법 등

 

안 해도 되긴 함

트라이 : 빠른 문자열 검색에 사용

라빈카프, KMP, 보이어-무어 : 문자열 검색 알고리즘

위상정렬 : 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것

 

그 외

비트마스킹

DP

그리디

세그먼트트리

 

 

 

https://mungto.tistory.com/516

코딩테스트 (알고리즘) 준비하기(알고리즘 종류, 방법)