자료구조 + 알고리즘 키워드

자료구조와 알고리즘을 공부할때 중요한 키워드를 정리해보았습니다.

 

자료구조
선형자료구조
배열, 스택, 큐, 리스트
비선형 자료구조
트리, 그래프, (연관 컨테이너)
알고리즘
(선형에서 주로 사용)
정렬 > N^2 > 버블...
NlogN > merge sort : divide conquer combine
quick sort ..
투 포인터

그리디

탐색
완전탐색(brute force)
DFS
이진탐색
shortpath 
1. 가중치가 없을 때 
BFS, 
2. 가중치가 있고, 음의 가중치가 없는데 시작점이 주어지면
다익스트라
3. 가중치가 있고, 음의 가중치가 있을때
벨만 포드
4. 가중치가 있고, 모든 시작점에서의 최소값(음의 가중치가 있어도 됨)
플로이드워샬 

트리를 만드는 알고리즘 
서로소집합, 세그먼트 트리
최소신장트리 (mst)
프림, 크루스칼

순서를 정하는 알고리즘 
위상정렬

문자열
KMP(중요), rabin-carp, boyer-more


확률통계
DP
하향식 : 재귀 + memoization
상향식 : (테이블러 + 점화식)
Graph min-cut
median 찾기
소수판별
자원줄이기 

max-min 알고리즘
alpha-beta Pruning




구현기법 : 재귀, 인접행렬, 인접리스트, 간선리스트