Algorithm

Fast Fourier Transform(FFT) - 고속 푸리에 변환

# About Fast Fourier Transform is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa. The DFT is obtained by decomposing a sequence of values into components of different frequencies. (reference) # Concept ..

Flow network - 네트워크 플로우

# Definition A flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge reference 플로우 네트워크 G는 모든 간선이 용량과 유량의 속성을 가지는 그래프이며 유량은 항상 용량을 초과할 수 없다. # Term Definition ## Flows ## flow를 정의하는 방법(notation)은 다양하다. 이 중 가장 직관적이며 대표적인 의사-유량(pseudo-flow라서 대충 의사-유..

Max-flow min-cut theorem - 최대 유량 최소 컷 정리

# Definition the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in a minimum cut, i.e., the smallest total weight of the edges which if removed would disconnect the source from the sink. reference $flow(s,t)_{max} = cut(s,t)_{min}$ 그래프 $G$에서 최대유량 $flow(s,t)_{max}$는 항상 source와 sink의 최..

Floyd-Warshall Algorithm - 플로이드 워셜 알고리즘

# Expression $ \forall u,v \in G: \ \ cost(u,v)$ 그래프 G에 대해서 모든 정점간의 최소 비용을 계산할때 쓰이며 음의 가중치 간선이 있어도 동작한다. 이러한 최소 비용 문제를 일반적으로 Shortest Path Problem 으로 분류한다. # Algorithm let cost[V+1][V+1] // cost[i][j]: cost of the shortest path from i to j //init for(i: 0~V) for(j: 0~V) if(i == j) cost[i][j] = 0 else cost[i][j] = w[i][j] ? w[i][j] : INF //relaxation for(mid: 0~V) for(start: 0~V) for(end: 0~V) if..