Doby's Lab

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

https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 문제를 읽고, 그래프가 양방향 그래프인 것을 알고 다익스트라를 돌리면 된다. #include #include #include #include #define MAX 50000 + 1 #define INF 987654321 #define pii pair using namespace std; int n, m; vector graph[MAX]; int dist[MAX]; struct cmp { bool opera..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 이 문제 또한 다익스트라를 통해 최소 비용을 구하고, 다익스트라에서 경로 역추적을 하여 최소 비용을 발생시키는 노드들의 배열을 담아서 main에서 이 노드들을 while을 통해 result배열에 담아 출력해주면 되는 간단한 문제였다. 하지만, 주어진 예제와 내 답이 달라서 틀린 건가 싶었지만 직접 그림을 그려보니 내 답도 만족하는 경우라서 혹시나 하는 마음에 제출을..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 0 이후에는 0~9 사이의 수 1 이후에는 1~9 사이의 수 ... 이와 같은 규칙이 존재하는 것을 알고 2차원 배열을 선언하여 cache[n번째 자릿 수][0~9사이의 수]로 선언하고, [n - 1번째 자릿수]가 [0~9사이의 수 중 하나]일 때 몇 가지 수가 나올 수 있는지 계산해주면 된다. [점화식] (n != 1 && n != 2)일 때 다음을 만족한다...

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분 매칭 알고리즘을 배우기 앞서 이분 그래프를 알아두면 좋을 거 같아 공부해보았다. 처음에는 BFS나 DFS로 어떻게 탐색해낼까 생각도 못 했다. (DFS나 BFS가 그래프 탐색 알고리즘이기 때문에) 솔루션을 참고했다. (https://jdselectron.tistory.com/51) 우선 이분 그래프를 보고, 이분 그래프의 특징 하나를 파악할 수 있어야 한다. [문제에 있던 글] 그래프의 정점..