알고리즘 공부방

https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 알고리즘 분류: Math, 유클리드 호제법 문제 풀이 먼저 입력 값과 시간을 보면 일일이 다 확인하는 브루트포스로는 풀 수 없다는 것을 알 수 있다. n이 100이고, 최대로 입력되는 값이 10억이므로 브루트포스로는 풀 수 없음을 알 수 있다. 그러면 이 문제는 수학적으로 접근을 해야한다는 것인데, 이 문제를 수식으로 써보면, 먼저 모든 수의 나머지가 같은 경우를 간단히 생각해보면 모든 수가 나누어 떨어지면 된다..

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 알고리즘 분류: 그리디 알고리즘, 정렬 문제 풀이 먼저 이 문제를 보자마자 생각난 문제가 있었는데, 백준 1461 문제와 비슷하다 생각했다. https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전..

https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 문제 풀이 이 문제를 보고 바로 떠올린 것은 폴로이드 워샬 알고리즘이었다. 하지만, 폴로이드 워샬을 썼을 때 첫번째 경유지를 어떻게 처리해야할지 고민하고 있었는데, 이 문제의 범위를 보니 시간 복잡도 O(E log V) 다익스트라 알고리즘으로 풀릴거라 생각이 들었다. 먼저 Node 클래스를 정의해 다음 정점과 가중치, 처음으로 들렸던 정점을 정의해주었다. static class Node implements..