농부공학자

BFS 알고리즘은 너비 우선 탐색 방법으로, 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. 주로 Queue 자료구조를 이용하여 모든 노드를 탐색한다. 예시를 살펴보자 예시 그래프~~!! 방문 기준은 번호가 낮은 인접 노드부터, 시작 노드는 1이라고 하자. 큐에 1 넣음 큐에 있던 1을 꺼내주고 인접 노드 2 3 8 을 넣어준다. 2 3 8 에서 2를 꺼내주고 2와 인접한 노드 7을 넣어준다. 큐 : 3 8 7 3 8 7 에서 3을 빼주고 3과 인접한 노드 4, 5를 넣어준다. 큐 : 8 7 4 5 8 7 4 5에서 8을 빼주고 8과 인접한 노드는 모두 방문했으므로 추가x 큐 : 7 4 5 7 4 5에서 7을 빼고 인접 노드 6을 들르면 모든 노드를 탐색하게 된다. 따라서 노드를 탐색하는 순서는 1 -..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net DFS로 풀었다. 딴건 몰라도 자바는 null때매 넘 짜증남... 특히 배열...... 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; public class Baek2667 { pu..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 위의 문제는 DFS, BFS 모두 사용할 수 있을 것 같다. 나는 DFS를 먼저 연습할 거라서 DFS로 풀었다. DFS를 사용하면 순서는 1 - 2 - 3 - 5 - 6 이 되어 4가 return될 것이다. (1은 포함x) 이전에 풀었던 1260번과 아주 유사한 문제이다 (https://ticssfm.tistory.com/67) 코드 import java.io.BufferedReader; import ..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS, BFS 알고리즘을 구현하는 문제이다. 여기서 주의해야할 것은 정점 번호가 작은 것을 먼저 방문 한다는 것과 예를 들어 예제 입력이 3 5 라면 5 3 으로도 넣어줘야 한다는 점이다. 2중 ArrayList를 사용할 것인데 행 번호가 노드 번호이므로 3번째 행에 5를 넣고, 5번째 행에 3을 넣어줘야 한다. 코드 import java.io.Buffere..

DFS(Depth-First Search) 알고리즘은 깊이 우선 탐색 방법으로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조 혹은 재귀 함수를 주로 이용하며 모든 노드를 탐색한다. 예시를 살펴보자 위와 같은 그래프가 있다. 시작 노드는 1이며, 방문 기준은 번호가 낮은 인접 노드라고 가정하자. 시작 노드 1에서 인접한 노드는 '2', '3', '8' 이다. 우리는 방문 조건에 따라 번호가 작은 2번 노드에 방문할 것이다. 이 때 스택에 1 - 2 를 차례로 담아준다. 노드 2에서 방문하지 않은 인접 노드 '7'에 방문해준다. 이 때 스택은 1 - 2 - 7 이 된다. 노드 7의 인접 노드 '6', '8' 중 작은 번호인 노드 6에 방문한다. 이 때 스택은 1 - 2 -..

https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 문자열 문제는 증말 어렵다.. 30의 배수임을 알아볼 때의 조건 1. 1의 자리가 0으로 끝남 2. 10~n의 자리가 3의 배수임 3. 3의 배수라는 것은 모든 자리의 수를 더했을 때 값이 3의 배수임을 뜻한다. 여기서 3번이 제일 중요함. 1의 자리가 0이고 각 자리 숫자의 합이 3의 배수이면 입력받은 수를 내림차순으로 정리한게 가장 큰 수가 된다. 어차피 1의 자리가 0이어야 하므로... 걍 내..

https://www.acmicpc.net/problem/10162 10162번: 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 www.acmicpc.net 위의 문제는 전에 풀었던 거스름돈과 비슷한 문제이다. 좀 더 깔끔하게 짜보려고 했는데 조건이 몇 번씩 누르는지 각자 출력이고, 나누어지지 않으면 -1 출력이기 때문에 또다시 노가다로 표현했다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class B..

재귀 함수란 자기 자신을 재 호출하는 함수를 말한다. 예를 들어 코드를 보자 package algorithm; public class recursive_fun { public static void main(String[] args) { recursive_function(); } public static String recursive_function() { System.out.println("재귀 함수 호출"); return recursive_function(); } } 위와 같은 코드가 있다면 recursive_function() 함수를 호출한 뒤 "재귀 함수 호출"을 print 하고 다시 recursive_function() 함수를 재호출하여 "재귀 함수 호출"을 print 하는 방식을 반복한다. 그 ..

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제를 보면 로프의 개수를 마음대로 사용할 수 있고 최대 하중을 구하는 문제이다. 예를 들어 10 15 30 50 4개의 줄이 있으면 밧줄 1개를 사용하면 50 이 최대이고 2개를 사용하면 50 30을 사용하여 30 x 2 = 60이 최대 3개를 사용하면 50 30 15를 사용하여 15 x 3 = 45가 최대 4개를 모두 사용하면 10 x 4 = 40이 최대이므로 최대 하중은 60이 된다..

https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 아ㅠ 이거 여러번 풀어본건데 코드 너무 구데기로 짰다... 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Baek5585{ public static void main(String[] args) throws IOException{ ..