공부하는 블로그

11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이� www.acmicpc.net 최대 힙을 구현하는 문제이다. 직접 최대 힙을 구현해서 풀어보는 방법과 우선순위 큐도 힙의 자료구조를 가지고 있으므로 자바에 이미 구현되어있는 PriorityQueue를 이용하여 푸는 방법이 있다. 공부를 위해 직접 구현해보는 방향으로 문제를 풀어보았다. import java.util.ArrayList; import java.util.Scanner; public class Main { public static class MyMaxHeap { p..

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 익은 토마토와 인접한 토마토는 하루의 시간이 지나면 익게 된다. 박스에 토마토가 전부 익는데 걸리는 시간을 구하는 문제이다. import java.util.ArrayDeque; import java.util.Queue; import java.util.Scanner; class Main { static int N; static int M; static int[][] tomatos; static int[] dx = {-1, 0, 1, 0}; sta..

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net N x M 행렬로 주어진 미로를 탐색하는 문제이다. (1, 1)에서 출발하여 (N, M)까지 도달하는데 필요한 최소 칸 수를 찾아내야 한다. import java.util.ArrayDeque; import java.util.Queue; import java.util.Scanner; class Main { static int[][] maze; // 미로 static boolean visit[][]; // 방문 여부 체크 static int[] dx = {-1, 0, 1, 0}; // 시계방향으로..

1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS와 BFS를 이용하여 그래프를 탐색하는 과정을 출력하는 문제이다. import java.util.ArrayDeque; import java.util.Queue; import java.util.Scanner; class Main { static int n, m, v; static boolean[][] linked; static boolean[] visit; static StringBuilder sb = new String..

5052번: 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없� www.acmicpc.net 전화번호 목록 중 한 번호가 다른 번호의 접두어가 되는지 판단하는 문제이다. import java.util.Arrays; import java.util.Scanner; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int tc = sc.nextInt(); for (int i = 0; i < tc; i++) { int n = sc.nextInt(); S..

11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5 www.acmicpc.net 세 개의 장대의 첫 번재 장대에는 반경이 서로 다른 n개의 원판이 쌓여있고 각 원판은 반경이 큰 순서대로 쌓여있다. 한번에 한 개의 원판만을 옮기며 어느 장대든 반경이 큰 순서대로 쌓여있어..

10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 www.acmicpc.net 재귀함수를 이용하여 n번째 피보나치 수를 구하는 문제이다. import java.util.Scanner; public class Main { public static void main(Strin..

1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 입력 받은 수가 소수인지 아닌지 판별하는 문제이다. 소수란 1보다 큰 정수 중 1과 자기자신으로만 나누어 떨어지는 수이다. (1은 소수가 아님) import java.util.Scanner; public class Main { static boolean isPrime(int num) { if(num == 1) return false; int w = 2; while(w < num) { if(num % w == 0) { return false; } w++; } return true; } public static void main(St..