알고리즘/Baekjoon

[백준] 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이 주..

[백준] 7576 토마토 (JAVA)

✉️문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 📝 접근 Queue를 이용한 BFS를 이용한다. 🗝 문제풀이 1. 입력을 받을 때 input == 1이면 큐에 집어넣는다. // 입력을 받을 때 input == 1이면 큐에 집어넣는다. for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { int input = sc.nextInt(); box[i][j] = input; if..

[백준] 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++..

[백준] 10830 행렬 제곱 (JAVA)

✉️문제 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 📝 접근 1. B의 범위를 보면 int형 범위가 넘어간다. 따라서 long으로 선언해야 한다. 2. 행렬 배열은 int형으로 선언해도 된다. (제곱하고 각 원소를 1000으로 나누기 때문) 3. 제곱을 100,000,000,000번 하면 시간제한인 1초 안에 풀 수 없다. 따라서 분할 정복법을 이용한다. 🗝 문제풀이 package baekjoon; import java.util.Scanner; publ..

[백준] 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을 분할 정복으로 구해보자. ..