알고리즘

백준 1006번 - 습격자 초라기

https://www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net # Approach) 타일링문제와 상당히 흡사하다. 고로 DP를 떠올려보자. First Try(Failed) # Definition) $dp[i][j] :$ $min \ value \ when$ $inner \ circle \ is$ $filled \ to \ index \ i$, $and \ outer \ j$ $in[i] :$ $cost \ of \..

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