1. 문제 28131번: K-지폐 (acmicpc.net) 28131번: K-지폐 첫째 줄에 $N$, $M$, $K$가 주어진다. $(2\leq N\leq 10\,000; 1\leq M\leq \min\left(100\,000, N(N-1)\right); 1\leq K\leq 50)$ 둘째 줄에 $S$와 $T$가 공백으로 구분되어 주어진다. $(1\leq S,T\leq N;S\neq T)$ 셋째 줄부터 $M$개의 www.acmicpc.net 2. 풀이 문제 자체는 간단하다 s에서 t로 이동하는데 가중치의 합이 k의 배수가 되는 최단 경로를 찾는 문제 어떤 수가 k의 배수라는 것은, k로 나눈 나머지가 0이라는 사실을 이용해서 찾는다. D[i][j]를 s에서 출발해서 i 정점으로 가는 경로의 가중치 합을 ..
1. 문제 그래프 G가 V개의 정점과 E개의 간선으로 이루어지며 간선의 가중치가 0 또는 1이다. 이때 두 정점 사이의 최단 경로를 찾는 효율적인 코드를 작성해야한다면? 2. 다익스트라 알고리즘이 항상 정답인가? 많은 경우에 다익스트라 알고리즘을 선택하지만, O(E+VlogV)가 최상의 구현이지만, 최악의 경우 효과적이지 않다. 많은 사람들이 이 문제를 보면 다익스트라 알고리즘을 선택하고, 효율적이지 않을때, 최적화할려고 노력하지만, 다익스트라 알고리즘이 최상이라고 생각한다면.. 매우 간단하면서 BFS를 이용한 아주 아름다운 0-1 BFS라는 기법을 알 필요가 있다 보조정리(Lemma) : "BFS 수행중에 정점을 포함하는 큐는, BFS 트리의 최대 2개의 연속한 레벨의 원소만을 포함할 수 있다" Lem..
1. 문제 14221번: 편의점 (acmicpc.net) 14221번: 편의점 처음 줄에는 정점의 개수 n, 간선의 개수 m이 주어진다.(2 ≤ n ≤ 5,000, 1 ≤ m ≤ 100,000) 다음 m줄에는 a,b,c가 주어지는데 이는 a, b를 잇는 간선의 거리가 c라는 것이다.(1 ≤ a, b ≤ n, 1 ≤ c ≤ 10,000) www.acmicpc.net 2. 풀이 집에서 편의점까지 거리가 가장 가까운, 집의 번호를 출력하는 문제다. 간단하게 생각하면, 집이 p개 있고 편의점이 q개 있는데.. p개의 점 각각에 대하여, 다익스트라 알고리즘을 수행하면 p개의 다익스트라 배열이 나오고.. 여기서 편의점 q개의 점에 대해 거리를 구해보고 거리가 가장 가까운 점을 찾으면 될것이다 근데 이렇게 하면 다익..
1. 문제 20007번: 떡 돌리기 (acmicpc.net) 20007번: 떡 돌리기 첫째줄에 N, M, X, Y가 공백으로 구분되어 입력된다. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000, 1 ≤ X ≤ 10,000,000, 0 ≤ Y < N) 두번째 줄부터 M+1번째 줄까지 A와 B 그리고 A집과 B집 사이의 도로의 길이 C가 주 www.acmicpc.net 2. 풀이 다익스트라는 기본 구현 그대로.. 하면 되는데.. 문제 조건을 올바르게 생각해야한다 1) "하루에 x보다 먼 거리를 걷지 않고, 거리가 가까운 집부터 방문한다" 거리가 가까운 집부터 방문한다고 하니까, 그래서 다익스트라로 얻은 최단거리 배열을 오름차순으로 정렬해줘서, 작은 거리부터 방문해줘야한다. 2) "잠은 꼭 본인 집에..
1. 문제 1238번: 파티 (acmicpc.net) 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 2. 풀이 이 문제의 핵심은 x번 마을에서 다시 i = 1,2,...번 마을로 되돌아오는 최단 거리가 필요하다는 점이다. 다익스트라 알고리즘은 출발 정점 start에서 다른 정점 1,2,...,n번 까지 가는 최단 경로를 구해주는 알고리즘이지 1,2,...,n번 각각의 정점에서 start로 되돌아오는 최단 경로를 구해주는 알고리즘은 아니다 이걸 할려면 다익스트라를 n번 해야하는데..
1. 문제 8347번: Bug (acmicpc.net) 8347번: Bug The first line of input contains two integers n and m (2 ≤ n ≤ 200 000, 0 ≤ m ≤ 500 000), separated by a single space and denoting the number of cities and the number of roads in Byteland. The cities are numbered from 1 to n; Bytetown has number www.acmicpc.net 2. 풀이 목적지까지 최단경로를 구해야하는데 문제는 홀수길이를 가지는 최단 경로를 구해야한다 그냥 사용하면 2를 답을 내는데.. 문제에서 원하는건 7로 가는 경로이다 쉬..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
