Doby's Lab

https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 이번 문제의 핵심이 플로이드 와샬이긴 하지만 개인적인 느낌으로는 플로이드 와샬을 끝내고, 회장 후보 수와 회장 후보들을 출력하는 게 더 핵심처럼 와닿았다. 그래서 이번 문제는 '구현' 키워드에 넣어두었다. 왜냐하면 이런 식으로 최솟값을 구하고, 그 최솟값을 유발하는 인덱스 or 노드들을 처리하는 방법은 볼 때마다 헷갈렸었기에 이번 기회에 직접 구현해보았다. [구현] score가 나왔을 때, 그것이..

https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 또 똑같은 키워드다. (https://draw-code-boy.tistory.com/151) (https://draw-code-boy.tistory.com/153) 다만, 시간 초과가 나와서 ios_base::sync_with_stdio(false); cin.tie(NULL); 를 해주고, 값을 복사해주는 cache의 역할이 사실상 의미가 없기 때문에 graph에 입력받은 값을 복사하지 않..

https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 개인적으로 (https://draw-code-boy.tistory.com/151) 이 문제와 똑같다고 느껴졌다. 저 문제를 풀지 않고, 이 문제를 시도했으면 어렵게 느껴졌을 거 같다. 플로이드 와샬로 나올 수 있는 문제 키워드 중 하나일 거 같다. #include #include #define MAX 500 + 1 #define INF 987654321 using name..

https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 사이클 최소 비용 경로 길이를 찾는 문제다. 플로이드 와샬을 사용하면 풀린다. 풀리는 이유는 플로이드 와샬을 이용하면 자기 자신을 향한 최소 비용 경로도 무조건 다른 노드를 거쳐서 할당되기 때문에 가능하다. (물론 최소 비용 경로를 묻는 문제에서는 자기 자신을 향한 경로는 플로이드 와샬이 끝나고 0을 할당해줘야 함) >> 플로이드 와샬의 특성을 이용하는 문제였다...

https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 단방향 BFS로 풀 수 있을까도 했지만 코드가 더러워질 거 같아서 플로이드 와샬로 풀었다. >> 플로이드 와샬은 한 번만 돌려도 모든 노드로부터 모든 노드까지 구할 수 있기 때문이다. >> BFS나 다익스트라는 한 노드로부터 모든 노드로의 최단 경로를 구하기 때문에 N번(노드 개수) 돌려야 한다. [솔루션] 1) 모든 가중치는 1로 설정한다. 2) 최단 경로가 0이면 자기 자신, INF이면 갈 수 ..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 최단 경로를 구하는 알고리즘 두 번째, 플로이드 와샬(Floyd Warshall)이다. 나동빈 님의 블로그(https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234427842&proxyReferer=https:%2F%2Fwww.google.com%2F)를 통해 공부했고, 나동빈 님의 글을 토대로 정리하는 글이다. [플로이드 와샬 정리] 1..