📠

알고리즘

태그

Major

Table

이름

Hash Function

쓰이는 곳

•

De-Duplication

•

the 2-sum problem

성능

•

alpha에 따라 다름. 이걸 적절히 해줘야함.resizing 가능. 좋은 hash function 쓰면 됨.

•

modular일 때는 소수 근처로 하는 거 추천

Bloom Filter

•

False Negative는 없음

◦

실제로는 있는데 없다고 하는 경우 없음.

array of n bits → insert & look up.

k개 hash function 써서 적당한 비트에 1로 표시하기

lookup 시, 모든 k hash function에 대해서 1인지 체크하기

하나의 array bit가 1로 체크 안 될 확률 → (1-1/n)^k|S|

1로 될 확률 → 1 - ~~

적당히 바꾸기, k = ln2 * b

BST

Operation

•

Insert, Delete

•

Delete가 문제임

◦

leaf → 그냥 삭제

◦

middle →child 하나: 그냥 삭제 후 대체

◦

middle → child 둘: predecessor 찾기(자기랑 바꾸기)

•

Rank

◦

size = # of tree nodes in subtree rooted at x

◦

left, right가 있는데, i에 대해서 왼쪽 오른쪽을 각각 비교해봄

▪

왼쪽이랑 비교했는데 i가 크면 오른쪽으로 이 때 i - a - 1로 가기. (i - 왼쪽 갯수 - 루트 갯수)

▪

왼쪽이랑 비교했는데 i가 작으면 왼쪽으로 i로 가기

▪

i-1이랑 왼쪽이랑 같으면 그냥 지금꺼 반환

레드-블랙 트리

•

항상 정렬 맞추기

•

모든 노드는 블랙/레드

•

루트는 블랙

•

블랙 다음에 블랙은 되지만, 레드가 연속으로 나올 순 없음

•

모든 root-NULL에는 블랙 개수가 같아야함.

따라서 레드는 갯수에는 포함이 안 되지만 연속으로는 못 쓰기 때문에 가장 미니멈한 갯수에 대해서 뻗어나가는 제한이 생길 수 밖에 없음.

root-NULL 패스가 k 노드를 가지고 있다 → 미니멈하게 2^k -1개 노드임

n ≥ 2^k - 1인데, k는 그래서 log(n+1)보다 작음. 이 말은 최대 log(n+1)의 노드가 있다는 뜻임. 따라서 최대 길이는 이거 2배

•

로테이션이 있음

•

Insertion

◦

coloring red

◦

연속된 red이다. 

◦

y는 블랙 parent w가 있음

◦

이 과정에서 다른 자식z을 봐야함

▪

블랙

•

rorate and recolor를 해야함.

•

▪

레드

•

y,z는 블랙으로 w는 레드로 만들기

BFS

→ queue 사용

→ layer 별 접근

→ O(m+n)

DFS

→ stack 사용

→ O(m+n)

Topological sort

•

directed graph에서 순서 메기기

•

sink node부터 거꾸로 메기기

•

DFS를 해서 set f(s) = current_label

•

current_label 1씩 줄여가기

SSC and Kosaraju

•

모든 v→v가 성립되면 strongly connected

kosaraju

•

ssc를 추상화해서 metapath로 만들 시, 우리는 sink 노드부터 공략해야햠.

•

sink 노드부터 넘버링이 잘 되어있어야함.

2-pass임

G_rev에 대해서 DFS를 돔. 이 때, 끝나는 시간에 맞춰서 넘버링을 진행해야함. 뒤에서부터 1,2 이렇게 매긴다는 듯

이 번호를 자기 번호로 매김

원래 G에서 그 번호가 큰 순서대로 DFS를 돔

두 번 DFS → O(m+n)임.

proof

→ adjacent SSC에 대해서 C1, C2

G_rev에 대해서 생각했을 때 첫 방문이 어디로 되어도 C1 → C2이면 C2의 finishing time이 항상 더 큼.

C2→ C1일 때, C1부터 떨어지면, 확실히 C1의 모든 값이 C2보다 작음

C2→C1일 때 C1부터 떨어지면, 어떻게든 C2에서 일단 시작을 하니까 C1의 모든 값보다 큰 거 무조건 하나는 있음

Dijkstra

•

source가 주어질 때, 모든 노드에 대한 최단 경로를 저장 + 복원할 수 있음

발견한 노드와 아닌 노드를 X랑 V-X로 놓음

모든 노드를 돌면서

•

그 둘 사이를 건너는 엣지들에 대해서 minimize할 수 있는걸 고름

proof

•

induction + 모순

•

특정 시점에 A[v] = L(v)로 잘 저장이 되었다고 할 때,

•

그 다음 노드 w를 고를 거임.

•

근데 우리는 이 때 최소 엣지를 pick할 예정임.

•

s→w*에 대해서 일반화를 해보자면 s → v* → w*는 s →  y → z → w*으로 표현할 수 있는데

•

이 때 길이는 A[y] + l_yz임. 근데 우리는 pick을 할 때 이미 s→z에 대해서 최소가 되는 걸 뽑기 때문에 z→w*가 0보다 무조건 크니까 우리가 뽑은게 최소임. 다른 것들은 이것보다 다 같거나 큼.

O(nm)인데 heap 쓰면 더 빠름

•

heap에서 key는 score가 되도록 설정함.

•

value는 vertex임.

•

매번 heap에서 뽑을 때, score 기준으로 뽑혀 나오게끔. 나오고 나면 업데이트 해줘야함.

•

key[v] = min{key[v], A[w]+I_wv}가 되도록 log n

•

생각해보면 삭제/삽입 2번이고 각각 log n이고, 모든 노드에 대해서 돌면서 진행하는데 이 때 간선을 무조건 한 번만 건들기 때문에 O(nlogn + 2m log n) ⇒ O(mlogn)임

Dynamic Programming

•

부분 문제 잘 찾는게 중요함.

•

부분 문제의 정답이 큰 문제의 정답이 되어야함.

•

어떤 요소를 induction하면서 큰 문제로 나아갈지 생각해야함.

WIS

•

마지막 요소에 대해서 생각하기

•

마지막 요소가 포함되면 그 정답은 그 set에서 전 요소, 전전 요소 뺀 상황에서도 정답임

•

마지막 요소가 포함이 안 되면, 그 set이 그 요소 없는 전 단계에서도 정답임.

reconstruction 어케하냐

•

각 단계별 요소를 보면서 판단하기

•

A[i-1]이거나 A[i-2] + wi거나인데

•

전자가 크면 그 요소가 포함이 안 됬다는 뜻이고, 후자가 크면 포함이 됬다는 뜻이니까, 각 단계에서 두 개를 비교해가며 포함할지 안 할지 right→left로 확인

냅색

•

weight, value에 대해서 최대화. weight에 대한 제한이 존재함.

•

WIS랑 똑같이 풀거임.

•

다만 이번엔 weight라는 요소가 추가되어서 2차원 배열로 풀거임.

•

모든 n에 대해, 모든 weight에 대해서

◦

weight가 x보다 크면 A[i,x] = A[i-1,x]임

◦

그렇지 않으면 A[i,x] = max{A[i-1,x], vi + A[i-1, x-wi]} ⇒ 이거 담았을 때랑 안 담았을 때 나눠서 생각

O(nW)

벨만 포드

•

single-source shortest path

•

negative edge에 대해서도 working 하도록 하고 싶음

•

DP로 풀건데, 어떻게 subproblem을 정의하냐

◦

i-hop으로 정의

•

proof

◦

induction으로 풀기

•

구현

◦

A[i,v]로 구현

◦

for i = 1 to n-1

▪

for each v

•

A[i,v] = min(A[i-1,v], min(A[i-1, w] + l_wv))

•

O(mn)

•

B[i,v]를 만들어서 전단계 저장하기.

•

O(n) space만 있으면 됨. 전 단계만 저장

•

A[i-1,w] + l_wv 인 경우에 w로 저장하면 됨.

Floyd-Warshall algorithm

O(n3)로 가자

Dense인 경우 Bellman-Ford는 O(n2m)이라 O(n^4)가 됨.

optimail substracture

•

node 1 → n으로 갈 때

◦

internal node를 i 노드까지로 구성할 수 있느냐.

•

만약에 k가 없으면 V(k-1)에서 shortest path임

•

K가 있으면 i-k랑 k-j가 각각 shortest path임.

A[3-D]

A[i,j,k]

i,j 는 포지션

k는 subproblem 나타냄

A[i,j,k] = min A[i,j,k-1, A[i,k,k-1] + A[k,j,k-1]이거나.

Greedy Algorithm

Scheduling

•

optimal한 순서가 있어. 내림차순으로 해서 1→n이 있다고 할 때

•

임의의 다른 optimal한 순서가 있다고 하면, inversion이 존재→ 이걸 바꾸면, 무조건 작아짐

•

근데 작아지는 이유가, 우리가 나열한 그 순서에 입각해서, cost benefit을 계산

MST1

MST2 - clustering

•

Prim

◦

임의의 s

◦

모든 edge에 대해서 가장 싼거 찍어서 추가

◦

correctness

▪

spanning Tree가 됨을 보이고

•

이거는 근데 연결될 때까지 하는 거라서 spanning이고.

•

모든 상황에서의 cut이 안 지나가게끔 할 수 있음

▪

T*이 MST가 됨을 보이고

•

특히 T를 구성하는 각각이 MST의 한 요소가 됨을 보임 → cut property

•

만약 싸지만 MST가 아닌 게 있다고 할 때 어떻게 되는지

◦

교환을 하면 어떠냐

◦

교환을 할 때, 내가 추가를 해서 나오는 cycle에 대한 걸 지우면 항상 spanning함

▪

lemma

•

not connected  건너는 엣지가 없다

•

두 번 건너면 사이클 있는거임

•

없으면 사이클이 없는거임

◦

구현

▪

O(mlogn)

▪

일단 initialize하고 추가될 때 마다 업데이트하는 식

▪

Dijkstra 처럼

•

크루스칼

◦

그냥 모든 m에 대해서 사이클이 안 생기게끔 추가하면 됨.

◦

correctness

▪

cut이 고정되있을 때 크루스칼은 가장 작은 첫 번째 crossing edge 뽑는거라 그럼

▪

근데 매번 작은 걸 뽑으니까 당연한거임..?

◦

implementation

▪

union-find

•

속한 그룹의 리더를 지정함

•

머지할 때, 이제 하나의 vertex에 대해서는 O(logn)만큼 일어남

•

mlogn + o(m) + o(nlogn)

•

클러스터링

◦

그리디 알고리즘

◦

p,q가 있는데 이미 머지 된 경우 → 이미 머지가 되었으니까 d(p,q)가 S보다 작다.