안녕

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

https://algospot.com/judge/problem/read/JUMPGAME algospot.com :: JUMPGAME 외발 뛰기 문제 정보 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상 algospot.com import sys input = sys.stdin.readline testcase = int(input()) # 테스트 케이스의 수 def func(start, end): W[start][end] = [0, 0] # 0, 0은 0, 0으로 초기화 C[start][end] = 0 # 0, 0의 count는 0 for i in range(start, n): # ..

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

문제)

Prin's Algorithm은 Minimum Spanning Tree를 찾는 가장 기초적인 알고리즘입니다. 1. Minimum Spanning Tree란? 우선, Minimum Spanning Tree를 알아보겠습니다. G(graph)에 대한 Spanning Tree는 G의 모든 vertex를 포함하고, 트리인 connected 된 그래프입니다. 만약 G = (V, E)로 이루어져 있다면, Spanning Tree인 T = (V, F)가 되어야 합니다. 이때 F는 V-1과 같습니다. 만약 F가 V-1보다 크다면 cycle이 생겨서 Tree가 되지 않습니다. 아무튼 우리가 찾아야 하는 (V, F)는 Edge의 weight의 합이 최소가 되는 집합을 찾아야 합니다. edge의 weight가 최소가 되는 S..