안녕

문제)

문제)

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개의 비트만 있으면..

문제)

1. 스케쥴링이란? The time in the system이란 기다리고, 수행하는 시간을 합친 시간이다. 시스템에서의 중요한 점은 이러한 시간의 합인 total time을 minimize 하는 것이 목표이다. 만약 deadline이 있는 스케쥴링이고, 각 작업은 동일한 complete time을 가진다고 가정합니다. 또한 데드라인 안에 끝내는 작업은 이익을 얻습니다. 만약 어떤 작업을 해당 작업의 데드라인 이후에 스케쥴링된다면 이 스케줄을 impossible이라고 합니다. 이때 impossible한 스케줄은 고려하지 않는데, 이유는 데드라인 이후에 실행되는 작업에 대해서는 이익을 얻지 못하기 때문입니다. 따라서 목표는 이익의 총합이 극대화되게 하는 것입니다. Job Deadline Profit 1 2 ..

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..

문제)