알고리즘에 자주 나오는 키워드

수학

에라토스테네스의 체

소수를 구하기 위한 알고리즘

int[] prim=new int[10001];
for(int i=2;i<n;i++){
	for(int j=2;i*j<n;j++){
    	prim[i*j]=1;
     }
 }

유클리드 알고리즘

gcd(a,b)=gcd(b,a mod b)

lcm(m,n)=m*n/gcd(m,n)

모듈러 연산의 특성

문자열, 패턴매칭

카프-라빈 알고리즘

문자열 검색을 위해 해쉬값 함수를 이용. O(M) (M:문자열 길이,N:패턴)

KMP 알고리즘

불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로 불일치가 발생한 앞 부분에 대하야 다시 비교하지 않고 매칭을 수행. O(M+N)

보이어-무어 알고리즘

O(N)

Tree

Trie

-응용: 사전적 순서로 정렬된 k번째 접미사 찾기

Suffix Trees

하나의 문자열의 모든 접미어들을 포함하는 트라이의 압축된 표현이다

-문자열 매칭

-부분문자열 매칭

-최장공통 부분문자열

Suffix Arrays

하프만 코드

이진트리의 순회

전위

중위

후위

세그먼트 트리

팬윅트리

그래프

Union-Find

최소비용신장트리(MST)

프림 알고리즘

임의의 정점에서 시작. 선택한 정점과 인접하는 정점들 중의 최소비용의 간선이 존재하는 정점을 선택

크루스칼 알고리즘

모든 간선을 가중치에 따라 오름차순으로 정렬 모든 정점이 연결될때까지 간선을 추가

최단경로

다익스트라 알고리즘

음의 가중치 x. 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최간 경로를 구하는 방식. 프림 알고리즘과 유사.

Repository