Algorithm/Algorithm Problem

[백준 - JAVA] 4375번 : 1

https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 문제 조건 파악 및 접근 문제를 보고 이해하는데 살짝 시간이 걸렸는데 결국 주어진 n의 배수 중에서 1로만 이뤄진 n의 배수를 찾는 문제였다. 우선 2와 5로 나누어 떨어지지 않는다는 조건이 왜 붙었냐면, 소인수분해 시 2와 5가 있을 경우 그 중 작은 수 만큼 수의 낮은 자리수에 0이 생겨서 1로 나누어떨어지지 않게 된다. 즉, 위 조건은 언젠가 1로만 이루어진 n의 배수가 나타나는 것이 보장되었다고 얘기하는 부분이다. 해당 문제는 나머지 연산의 법칙을 ..

[백준 - JAVA] 2606번 : 바이러스

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 조건 파악 및 접근 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 컴퓨터는 100 이하는 갖지만 최대 간선 수는(n*(n-1)) / 2 이므로 4,950개까지 가능. 그래프 문제고 DFS, BFS을 활용하면 된다. 결국 1에 연결된 노드의 개수를 파악하라는게 문제의 최종적인 질문. 풀이 1. BFS 풀이 2. union-find를 활용 union으로 "동일 집합..

[백준 - JAVA] 2470번 : 두 용액

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제를 파악하면서 투 포인터라는 것을 알고 분석을 해봤다. 2