승형님의 블로그

https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 요약 바다와 육지로 이루어진 지도에서, 육지에서 육지로 이동하는 최대 최단거리를 구한다. 1. 육지에서 인접한 육지로 이동하는 비용이 1이므로, 모든 가중치가 동일한 무방향 가중치 그래프를 떠올릴 수 있다. 2. 모든 가중치가 동일하고, 최단거리를 구해야 하므로 BFS(너비 우선 탐색) 기법으로 최단거리를 구할 수 있다. 3. 최단거리의 최대 값을 구하기 위해 지도 상의 Brute Force 기법을 ..

https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 요약 초기에 다른 모든 정점과 단절된 한 정점이 존재한다. 그 정점에서 다른 모든 정점에 간선을 잇는 비용이 주어질 때, 연결그래프를 만들기 위한 최소 비용을 구한다. 1. 이미 연결되어 있는 M개의 간선 정보가 주어진다. 단절된 정점에서 한 정점과 간선을 연결하면 그 정점과 연결된 모든 정점과도 연결되기 때문에, 이미 연결된 두..

https://atcoder.jp/contests/abc280 Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280) - AtCoder AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp A. Pawn on a Grid 요약 주어진 격자에서 '#'의 개수를 세어 반환한다. #include using namespace std; int H, W, cnt; int main(void) { ios::sync_with_stdio(false); cin.tie(..

정수 K를 소인수분해하여 다음과 같이 나타낼 수 있다. $K = p_{1}^{q_{1}}\times p_{2}^{q_{2}}...\times p_{i}^{q_{i}}\times M$ 이때, $p_{1}, p_{2} ... p_{i} \leq \sqrt{K}$ 이고, M은 소수이다. int K; vector primeFact; int main(void) { cin >> K; for (int i = 2; i * i

https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 요약 한 정점에서 임의의 정점으로 향하는 K번째 최단경로를 구한다. 1. N개의 도시와 M개의 도로로 이루어진 가중치 방향 그래프가 주어진다. 2. 다익스트라 알고리즘의 아이디어와 우선순위 큐를 활용하여 풀이한다. 3. 기존의 다익스트라 알고리즘에서는 오직 1번째 최단경로만이 중요하므로 한 정점을 방문했을 때의 값이 dist[vertex] ..

https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 요약 임의의 두 정점간의 최단거리를 묻는 K개의 쿼리를 처리한다. 1. 초기의 학교의 상태가 주어진다. 이때, 일방통행 도로를 1번의 조작을 통해 양방향 도로로 바꿀 수 있다. 따라서, 양방향 도로의 경우에는 가중치가 0이고 일방통행 도로인 경우에는 순방향일때 가중치가 0, 역방향일때 가중치가 1인 가중치 방향 그래프로 바꾸어 생각할 수 있다. 2. 임의의 정점 S와 E간의 최단거리를 묻는 K개..