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. 위상정렬 가볍게 복습 그래프의 노드를 정렬하는 위상정렬 정복하기 (tistory.com) 그래프의 노드를 정렬하는 위상정렬 정복하기 1. 개요 위상 정렬(topology sort)은 정렬 알고리즘의 일종 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야할 때 사용할 수 있는 알고리즘 이론적으로, 위상 정렬은 방향 그래프의 deepdata.tistory.com 1) 그래프를 만들면서, 각 노드의 진입차수(indegree)를 세준다. 2) 진입차수가 0인 노드를 큐에 모두 넣는다. 3) 큐가 빌때까지 다음을 반복 3-1) 큐에서 노드를 하나 빼고, 결과 리스트에 넣어준다. 3-2) 3-1)에서 뺀 노드에서 출발하는 모든 간선을 제거 3-3) 3-2) 후에 노드의 진입차수가 0이 된 노드는..
1. 문제 D - Unicyclic Components (atcoder.jp) D - Unicyclic Components AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 주어진 그래프에서 모든 연결요소가 정점의 개수와 간선의 개수가 같은지 판단하는 문제 2. 풀이 연결요소 하니까 BFS로 찾아볼려고 했는데.. 이게 간선을 관리하기가 만만치 않다 심지어 이 문제는 두 정점 사이 간선이 여러개 있어도 상관없고, 동일한 정점에 간선이 있는 루프도 있다 editorial 피셜로 "One can manage the connect..
1. 연결요소 연결 요소(Connected Component) (velog.io) 연결 요소(Connected Component) 그래프 중에서는 위 그림과 같이 여러 개로 나누어져 있을 수도 있다. 위 그림을 보고 두 개의 그래프라고 볼 수도 있지만, 하나의 그래프에 두 개의 연결 요소를 가진다고 볼 수도 있다. 그 이유 velog.io 위 그래프가 2개의 그래프로 볼 수도 있지만, 1개의 그래프가 2개의 연결요소를 가진다고 볼 수 있다. 연결요소(connected component)는 해당 요소에 속하는 모든 정점을 연결하는 경로가 있어야하고 또 다른 연결요소에 속한 정점과 연결하는 경로가 없어야한다. 2. 문제 11724번: 연결 요소의 개수 (acmicpc.net) 11724번: 연결 요소의 개수..
1. 문제 16168번: 퍼레이드 (acmicpc.net) 16168번: 퍼레이드 첫 번째 줄에 지점의 개수 V, 연결 구간의 개수 E가 주어진다. (1 ≤ V ≤ E ≤ 3000) 이후 E개의 줄에 걸쳐 각 연결 구간이 연결하는 두 지점의 번호 Va, Vb가 공백을 사이에 두고 주어진다. (1 ≤ Va, www.acmicpc.net 2. 오일러 경로(eulerian trail) "모든 변을 단 한번만 지나서 주어진 그래프를 완성할 수 있는가" 그래프의 모든 간선을 1번만 지나서 모든 정점을 방문하는 연속된 경로를 오일러 경로라고 부른다 혹은 한붓그리기라고도 불린다. 위와 같이 정점은 여러번 지나도 상관없다 위와 같은 그래프는 오일러 경로가 존재하는 그래프이다. 특히 시작점과 끝점이 같은 오일러 경로는 ..
1. 문제1 13023번: ABCDE (acmicpc.net) 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 2. 풀이 A는 B의 친구이다 B는 C의 친구이다 C는 D의 친구이다 D는 E의 친구이다 이 말은 무슨말일까? A에서 시작해서 B로 가고, B에서 C로 가고 C에서 D로 가고 D에서 E로 갈 수 있는 경우가 존재하는지 아닌지를 판단하라는 말 주어진 그래프에서 DFS 탐색으로 깊이 4까지 갈 수 있다면 1을 return하면 될 것 깊이가 4이면 1을 return하고.. 깊이가 4가 아니면.. 탐색을 수행 현재 방문하는 점 x에 대한 방문처리 visited[x] = 1 x와 연결된 점 graph[x]에서 순회해..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
