본문 바로가기

프로그래밍/알고리즘

 (45)
압축 (1) Compression (1) Huffman Coding- 가장 대표적인 데이터 압축 알고리즘 중 하나이다. 또한 무손실 압축 알고리즘이기도 하다.- 압축의 방식에는 무손실과 손실 압축이 있다.- 이미지나 소리, 동영상 등의 멀티미디어 데이터들은 원본에 비해 약간의 손실이 있더라도 사람이 인지하기 힘들기 때문에 손실 압축 기법을 주로 이용하며 이 방식은 압축률 측면에서 효율적인 알고리즘이다.- 텍스트나 수치 데이터의 경우에는 데이터의 손실이 있으면 의미가 완전히 달라지기 때문에 무손실 압축 기법을 사용해야만 한다.위 그림은 문자가 5개 있을 경우를 가정하였으며 각 문자는 빈도의 퍼센티지로 표현하고 있다. 이렇게 표현해도 상관이 없는 이유는 허프만 코드 자체가 실제 빈도가 아니라 상대적 빈도에 의해 결정되는..
최단 경로 (3) Shortest Path (3) Floyd-Warshall Algorithm- all-to-all 최단 경로 알고리즘들 중 가장 유명하다.- Floyd 알고리즘은 동적 계획법(Dynamic Programming) 전략에 기반하고 있다.- 가중치 방향 그래프 G = (V, E) (V = {1, 2, ... , n})- 모든 노드 쌍들간 최단 경로의 길이를 구한다.- $d^k$[i, j]중간에 노드 집합 {1, 2, ... , k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단 경로의 길이를 뜻한다.1) $d^0$[i, j]는 k가 0인 경우로 공집합을 의미한다. 또한 중간에 지날 수 있는 노드가 없다는 것으로 직접 연결된 엣지가 있지 않다면 길이를 ∞로 생각한다.2) $d^n$[i, j]는 k가 n..
최단 경로 (2) Shortest Path (2) Bellman-Ford Algorithm- 벨만 포드 알고리즘은 엣지들의 relax 순서가 고정되어 있지 않아 이 순서에 따라 중간 과정이 여러 분기로 나누어지게 된다.- Worst Case에 근접한 실행 예- 슈도 코드 BELLMAN-FORD (G, w, s)INITIALIZE-SINGLE-SOURCE(G, s);for i = 1 to |V[G]| - 1 // |V[G]|는 n과 같은 의미이기 때문에 n - 1번 반복하라는 뜻과 같다.for each edge (u, v) ∈ E[G]RELAX (u, v, w); // 여기까지가 벨만-포드 알고리즘의 핵심 부분for each edge (u, v) ∈ E[G]if d[v] > d[u] + w(u, v) // 음수 사이클이 존..
최단 경로 (1) Shortest Path (1) 최단 경로- 가중치(방향) 그래프 G = (V, E), 즉 모든 엣지에 가중치가 있다.- 경로 p = $v_0$, $v_1$, ... , $v_k$)의 길이는 경로상 모든 엣지들의 가중치들 총 합이다.- 노드 u에서 v까지의 최단 경로 길이를 δ(u, v)라고 표시한다. 최단 경로 문제의 유형- Single-source (one to all)하나의 출발 노드 s로부터 다른 모든 노드까지의 최단 경로를 찾는 문제.Ex) Dijkstra algorithm- Single-destination모든 노드로부터 하나의 목적 노드까지의 최단 경로를 찾는 문제single source와 본질적으로 거의 동일한 문제이다.- Single-pair (실질적으로 가장 유용한 문제, one to ..
최소 비용 신장 트리 (2) Minimum Spanning Tree Kruskal Algorithm 서로소인 집합들의 표현- 각 집합을 하나의 트리로 표현한다.- disjoint 특성(두 집합이 공집합)을 가진 sets - find(u)=u가 속한 집합 찾기, union(u, v)=두 집합을 하나로 합치기- Ex) 2개의 집합- 리프 노드로부터 루트 노드까지 따라 올라가면서 연산을 수행한다. 이 때 각 노드는 자식 노드가 아닌 부모 노드의 주소를 가지기 때문에 링크 구조를 쓰지 않아도 좋다. 또한 부모 노드의 주소가 자신의 주소와 동일하다면 그 노드는 루트 노드라는 것을 뜻한다.- 트리의 모양은 크루스칼의 진행에 따라 얼마든지 바뀔 수 있다.- 여러 트리가 있어도 모두 한 개의 배열로 표현이 가능하다. 이때 배열은 상향식으로 표현하..
최소 비용 신장 트리 (1) Minimum Spanning Tree 최소비용 신장 트리 (MST)- 입력 : n개의 도시, 도시와 도시를 연결하는 도로의 비용- 출력 : 최소의 비용으로 모든 도시들이 서로 연결된 상태- 무방향 가중치 그래프이며 가중치들은 전부 양수라고 가정한다.- (b, c) 엣지대신 (a, h) 엣지를 연결하는 등 문제에 대한 해가 유일하지 않다. - 무방향 가중치 그래프 G = (V, E) / 가중치들은 양수들이다.- 각 엣지 (u, v) ∈ E에 대해 가중치 w(u, v)Ex) 아래와 같은 조건을 만족하는 엣지들의 부분집합인 T ⊆ E를 구해라.1) T에 속한 엣지들에 의해 그래프의 모든 정점들이 서로 연결된다.2) 가중치의 합 $\sum _{ (u,v)∈T }{ w(u,v) } $이 최소가 된다. 트리라고 ..
DAG와 위상 순서 DAG (Directed Acyclic Graph) Directed Acyclic Graph- DAG는 방향 사이클 (directed cycle)이 없는 방향 그래프이다.- 유효한 순서의 그래프가 되려면 그래프 상의 엣지들의 방향이 항상 왼쪽에서 오른쪽의 방향으로 진행되어야 한다.- ex) 작업들의 우선 순위 등 위상 정렬 (topological ordering)- DAG에서 노드들의 순서 $v_1$, $v_2$, ... , $v_n$ (단, 모든 엣지 ($v_i$, $v_j$)에 대해 i < j가 되어야 한다.)- indegree : 노드를 기준으로 들어오는 엣지의 개수, outdegree : 나오는 엣지의 개수, incoming : 들어오는 엣지, outgoing : 나가는 엣지첫 번째 위상 정렬에서..
그래프에서의 DFS 깊이 우선 순회 (DFS)1) 출발점 s에서 시작한다.2) 현재 노드를 visited로 마크한 후 인접 노드들 중 unvisited 노드가 존재한다면 그 노드로 이동한다. (노드는 임의로 결정.)3) 2번 작업을 반복한다.4) 만약 unvisited인 이웃 노드가 존재하지 않는다면 발견할때까지 직전에 방문했었던 노드를 따라 되돌아간다.5) unvisited 노드를 발견하게 된다면 2번 작업을 다시 반복한다.6) 시작 노드 s로 돌아온 후 더 이상 갈 곳이 없다면 순회 작업을 종료한다. - 다른 예시- 슈도 코드 DFS (G, v)visited[v] n : 노드의 개수

티스토리툴바