안녕

문제)

문제)

1. 데이터 압축 문제 (The problem of data compression) 데이터 파일을 효율적으로 encoding 하기 위한 방법을 찾아내는 문제입니다. 데이터 파일은 통상적으로 이진 코드 (binary code)로 표현됩니다. 또한 각각의 이진 문자열은 코드 워드 (code word)라는 유일한 이진 코드로 표현됩니다. 이때 "ababcbbbc"라는 문자열이 있다고 가정하면, 문자의 집합은 {a, b, c}가 됩니다. 이때 이 문자열을 이진 코드로 표현하는 방법이 있습니다. 1.1 길이가 고정된 이진 코드 (fixed-length binary code) 길이가 고정된 이진 코드는 각각의 문자를 표현하는 비트의 개수가 일정합니다. {a, b, c}를 표현하기 위해서는 단지 3개의 비트만 있으면..

문제)

https://www.acmicpc.net/problem/1931 import sys input = sys.stdin.readline def func(case): i = 1 solved = True while solved: # 더 이상 들어갈 수 없다면 False임 solved = False case.append((s[i], e[i])) # i가 1로 시작하고, 나중에는 아래의 조건에 맞는 회의가 들어감 for j in range(i + 1, n + 1): if s[j] >= e[i]: # j번째 회의의 시작 시간이 i번째 회의의 끝나는 시간 이후라면 i = j # 해당 회의를 넣고 끝내버림 solved = True break n = int(input()) # 회의의 개수 s = [0] # 회의의 시작 ..

문제)

다익스트라 알고리즘은 단일 출발점에서의 최단 경로의 문제를 푸는 알고리즘입니다. 앞선 DP 알고리즘에서 Floyd's Algorithm을 이용해서 모든 출발점에서의 최단 경로의 문제를 풀었습니다. 하지만 하나의 특정 vertex에서 다른 모든 vertex로 가는 최단 경로만 알고 싶다면 프로이드의 알고리즘은 너무 과합니다. 시작하기에 앞서 프로이드의 알고리즘은 n^3인 것에 반해, 다익스트라 알고리즘은 n^2입니다. 다익스트라 알고리즘은 Prim's Algorithm과 매우 흡사합니다. 집합 Y를 최단 경로를 구하려고 하는 vertex만 포함한다. (v_1이라고 함) 그리고 F는 공집합으로 초기화한다. v_1과 가장 가까운 vertex를 찾아서, 이 vertex를 Y에 포함하고, edge를 F에 포함한다..

앞서 보았듯이 시간 복잡도는 다음과 같습니다. Prim's Algorithm : \(T(n)\,\epsilon\,\theta(n^2)\) Kruskal's Algorithm : \(W(m, n)\,\epsilon\,\theta(mlgm) \, or \, \theta(n^2lgn)\) 또한 \(n-1 \leq m \leq \frac{n(n-1)}{2}\)이 성립합니다. 따라서 프림 알고리즘과 크루스칼의 알고리즘은 다음과 같은 상황에서 비교할 수 있습니다. For a Sparse Graph edge의 개수인 m이 n-1과 가까운 희소 행렬의 경우에는 Kruskal's Algorithm is \(\theta(nlgn)\)이므로, Prim's Algorithm 보다 빠릅니다. For a Dense Graph e..

문제)

최소 비용 신장 트리를 풀기 위한 또 다른 알고리즘은 크루스칼 알고리즘입니다. 크루스칼 알고리즘은 각 vertex마다 본인만 포함하는 서로소 집합 (disjoint set)을 만드는 것부터 시작합니다. 이후, 가중치가 작은 것부터 차례대로 edge를 검사합니다. 만약 edge가 서로소 부분 집합들에 있는 두 개의 vertex를 연결한다면 edge를 추가하고, 두 개의 부분 집합을 하나의 집합으로 합칩니다. 이 반복은 모든 disjoint set이 하나의 set이 될 때까지 반복합니다. 슈도 코드로 작성하면 다음과 같습니다. F = 0 create disjoint set of V sort the edges in E in nondecreasing order while the instance is not so..