알고리즘

[백준] 1697 숨바꼭질 (JAVA)

✉️문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 📝 접근 최단거리를 구하는 문제이다. DFS로 풀 수 있을 것 같지만, DFS로 구현하면 커팅 기법을 사용해도 지수 시간 복잡도를 가지기 때문에 시간 내에 통과하기 어렵다. 따라서 BFS를 이용해야 한다. 🗝 문제풀이 package baekjoon; import java.util.LinkedList; import java.util.Queue; import jav..

[백준] 7569 토마토 (JAVA)

✉️문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 📝 접근 7576번과 똑같은 BFS 문제이다. 여기서 배열이 2차원 -> 3차원으로 변경된 문제라고 생각하면 된다. https://brightmango.tistory.com/323 [백준] 7576 토마토 (JAVA) ✉️문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주..

[백준] 2606 바이러스(JAVA)

✉️문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 📝 접근 이 문제를 풀기 위해서는 2가지를 알아야 한다. DFS 또는 BFS -> 본인은 DFS를 통해 문제를 풀었다. -> DFS의 핵심은 재귀이며, 똑같은 정점을 방문하지 않도록 추가적인 체크배열이 필요하다. public static void DFS(int idx) { ch[idx] = 1; for(int n : graph.get(idx)) { if(ch[n] == 0) { answer++..

[백준] 1629 곱셈 (JAVA)

✉️문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 📝 접근 for문을 이용한 방법 가장 간단한 방법이 for문을 이용하여 a를 b번 곱해주는 것이다. for(int i = 0; i < b; i++) a *= b; 하지만, 이 방법은 b가 50,000,000이 넘어가면 시간초과가 되어 버린다. (시간 제한 : 0.5). 따라서, O(N)보다 빠른 알고리즘을 고려할 필요가 있다. 분할 정복(Binary Search) 분할 정복은 숫자의 1/2를 반복해서 구하는 것이다. 10^8을 분할 정복으로 구해보자. ..

[알고리즘] 동전 교환 알고리즘

동전 교환 알고리즘 최소의 갯수로 거스름돈을 주는 방법에 대해 알아보자. 그리디 알고리즘 동전교환 문제를 풀기 위해 그리디 알고리즘을 사용할 수 있다. 하지만 그리디 알고리즘은 가장 적은 동전 수의 최적해를 항상 찾는 것은 아니다. 예를 들어보자, 동전의 종류가 [1, 3, 4] 이렇게 존재하고 9원을 거스름돈으로 준다고 하면, 그리디 알고리즘은 4원 1개, 3원 1개, 1원 2개를 선택할 것이다. 하지만 3원 3개를 거스름돈으로 주는 방식이 가장 적은 동전의 개수를 이용한 최적해이다. 그렇다면 항상 최적해를 찾기 위해 어떤 알고리즘을 이용해야 할까? DFS DFS 알고리즘을 이용할 수 있다. 위와 같이 [1,3,4] 동전 종류가 있고, 9원을 거스름돈으로 거슬러 준다고 해보자. 각 코인마다 3개의 가지..