알아둘 만한 알고리즘들

개요

---

 

알아둘 만한 알고리즘 및 자료구조를 정리.

 

해당 알고리즘에 대해 자세히 알아보는 게 아니라 나중에 '아 이런 게 있었지. 하며 찾아볼 수 있도록 하는 용도.'

 

여기 나열된 게 최선의 알고리즘은 아닐 수 있으므로 어디까지나 구글링의 시작점으로 활용해야 한다. (ex. 경로의 가중치가 음수인 경로를 구하고 싶다면 벨먼 포드를 쓰는게 아니라 벨먼 포드보다 나은 알고리즘을 검색해본다.)

 

너무 기초적인 것(ex. KMP)은 다루지 않는다.

 

 

일반

---

펜윅트리, 세그먼트트리의 Lazy Propagation

구간 자체를 업데이트할때 쓸 수 있다. 백준 문제 (백준 2934 - LRH 식물)가 있다. 

 

세그먼트트리랑 비슷함. 

 

 

 

 희소 테이블 (Sparse Table)

어 대충 정적인 Array의 1,2,4,8,16... 번째 노드의 어떤 유용한 데이터를 캐싱해 둔다는 개념임. LCA 찾을때도 유용

 

 

 

 LCA (Longest Common Ancestor)

제곧네

 

 

 

---

 

 

문자열 처리

---

 

아호코라식

 

트라이(Trie)에 KMP와 비스무리한 개념 (FailNode)를 추가했다고 보면 된다. 일대 다 매칭을 처리할 수 있다. 

 

예) 비속어 처리 ("너 바보냐?" => "너 ****냐?")

 

 

 

Suffix Array, LCP(longest common prefix)

 

맨버 마이어스로 LCP배열과 Suffix Array를 O(nlogn)에 구할 수 있단다. LCP만 구한다면 O(n)까지도 있는 모양(https://en.wikipedia.org/wiki/LCP_array). 

 

 

 

라빈 카프 알고리즘

 

라빈 카프 핑거프린트란걸 만들어서 해쉬를 만들고 이걸로 문자열을 탐색한다는 아이디어. 

 

중요한 건 어떤 구간 (a,b)의 해쉬값을 알면 (a+1, b+1)의 해쉬값을 O(1)속도로 구할 수 있다는 것. 

 

 

 

---

 

경로&그래프

---

다익스트라

간선에 가중치가 있는 경우의 최단거리. 없다면? 굳이 안 써도 될 것.

시작점부터 인접노드를 큐(우선순위 큐)에 넣어가면서 값들을 갱신함. 

O((V+E)logV)

 

플로이드 워셜 

 

다익스트라와 달리 모든 노드끼리의 최단거리를 구할 수 있음

O(V^3)

 

 

벨먼 포드 알고리즘

 

경로의 가중치가 음수인 경우에 쓸 수 있다. (다익스트라는 안 됨)

O(VE) 

 

 

SPFA (Shortest Path Faster Algorithm)

벨만포드보다 빠르다? MCMF에서도 자주 쓰인다?

최악의 경우 O(VE) 대부분의 경우 O(V+E)

 

SCC (Strongly Connected Component)

https://en.wikipedia.org/wiki/Strongly_connected_component

두 노드 X,Y가 서로 도달 가능하다면 strongly connected임 

 

타잔알고리즘, 코사라주 알고리즘이 있음.

 

 

 

-- BCC

 

 

 

---

유량

---

알고리즘

우선 DFS를 쓰는 포드풀커슨이 있다. 그러나 유명한 단점이 존재함. 그래서 BFS를 쓰는 에드몬드 카프가 더 효율적. 추후 이걸 토대로 여러 알고리즘들이 개발됨

 

디닉 알고리즘

DFS쓰면 포드풀커슨, BFS쓰면 에드몬드 카프인데 .. 이거보다 빠르다. 

 

MCMF (Minimum cost Maximum Flow)

똑같은 유량네트워크 문제인데, 이제 간선의 비용이 추가되어서 이게 최소인것.

 

최소 컷(Min cut)

컷이란건 유량 네트워크를 2등분 하는 거임. 이때 컷과 컷 사이에 흐르는 유량이 가장 적은 애를 최소 컷이라고 함.

 

'최소 컷의 유량은 전체 네트워크의 최대 유량이다.' 라는 정리를 통해, 일반적인 유량 찾기 알고리즘으로 최대 유량을 구할 수 있고, 이를 이용하여 최소 컷의 비용을 알 수 있음. (종만북 국책사업 문제)

 

 

이분매칭(호프크로프트-카프)

대충 A그룹 B그룹에서 서로 호감가는 사람 지목하고 서로 지목한 애들끼리만 짝지어주는 상황에서 씀 ㅇㅇ. 용량이 1인 간선으로 연결되어있다고 가정한다면 유량 네트워크로 풀 수 있다. 

 

이걸 좀 더 빨리하면 호프크로프트-카프 알고리즘임. 

---

 

집합

---

유니온 파인드 트리

두 노드가 같은 그래프에 있는지 판별할 때 사용. Disjoint-Set이라고도 불린다. 노드끼리의 도달 여부를 판별할때 활용할 수 있다.