문제풀이/백준
-
[백준]2023: 신기한 소수 - JAVA문제풀이/백준 2021. 3. 8. 18:51
[백준]2023: 신기한 소수 www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이 N자리 수중에 소수를 모두 출력하는 DFS문제이다. 숫자를 자리수 별로 하나씩 뽑으면서 뽑았을 때 소수가 되는 경우만 수를 이어서 뽑는다. 뽑다가 N자리가 되는 순간 출력을 하도록 하였다. 소수를 판별하는 방법은 에라토스테네스의 접근 방식을 사용했다. 소수 판별식 코드는 아래와 같다. public static boolean isPrime(int num) { if(n..
-
[백준]9019: DSLR - JAVA문제풀이/백준 2021. 3. 7. 19:53
문제 www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 A를 B로 표현할 수 있는 최소한의 방법을 출력하는 것이므로 BFS를 사용하였다. 모든 경우에서 4가지 명령어를 실행하고 각각의 실행한 경우에서 또 명령어를 실행하도록 반복해 주었다. 이러다가 B가 되었을때 그때까지의 명령어를 반환하도록 하였다. 현재까지 사용된 명령어를 저장하기 위해서 Node 클래스를 사용해 주었다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..
-
[백준]13023: ABCDE - JAVA문제풀이/백준 2021. 3. 4. 14:19
[백준]13023: ABCDE www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 모든 경우를 탐색하는 DFS탐색 문제로, A -> B -> C -> D -> E인 관계가 있다면 1을 출력, 아니면 0을 출력하는 문제이다. 위와 같은 연결 관계가 있다면 DFS탐색 깊이가 4가 되는 것을 이용하여 문제를 풀었다. 반복문을 사용하여 시작 순서를 돌아가면서 DFS탐색을 하였고, 탐색 깊이가 4가 되는 순간 1을 출력하고 프로그램을 종료했다. 1이 출력되면 그 이후에는 더 이상 탐색하지 않아도 되기 때문이다. 모든 DFS탐색 동안 1이 출력이 되지 않는다면 위와 같은 ..
-
[백준 ]5014: 스타트링크 - JAVA문제풀이/백준 2021. 3. 3. 15:08
문제 www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 S -> G로 가는 최단 경로를 찾는 문제이므로 BFS를 사용하여 풀었다. 이미 방문한 층을 다시 방문하면 최단 경로가 아니기 때문에 visited를 사용하여 다시 방문하는 일이 없도록 하였다. 또한 노드 class를 만들어 현재 층의 위치와 현재까지 몇번의 버튼을 눌렀는지 기억하도록 하였다. 이 문제에서 주의할 점이 있는데 예제 입력 1번을 잘 이해했다면 넘어가도 된다. 예를 들어, 예제 1번에서 1 -> 10..
-
[백준]1504: 특정한 최단 경로 - JAVA문제풀이/백준 2021. 3. 2. 17:39
[백준]1504: 특정한 최단 경로 www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 1에서 시작해서 V1과 V2를 포함하여 N까지 가는 최단 경로 값을 찾는 문제이다. 간단하게 생각하면된다. 다음과 같은 두 경로를 구한 후 둘 중에 더 작은 경로를 출력하면 된다. 최단거리(1 ~ V1) + 최단거리(V1 ~ V2) + 최단거리(V2 ~ N) 최단거리(1 ~ V2) + 최단거리(V2 ~ V1) + 최단거리(V1..
-
[백준]2589: 보물섬 - JAVA문제풀이/백준 2021. 3. 2. 15:34
[백준]2589: 보물섬 www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 풀이 최단거리 중에서의 최대값을 구하는 문제였다. BFS로 각 정점에서의 최단 거리를 구해주고 그 최단 거리 들 중의 최대값을 계산해 주었다. BFS에서 현재 위치와 현재 위치 까지의 거리를 저장해줄 Node class를 만들어서 저장해 주었다. 그리고 이중 for문으로 모든 노드를 확인하면서 '육지'인 경우에만 BFS탐색을 하도록 하였다. 코드 1 2 3 4 5 6 7 8 9 10 11 ..
-
[백준]1647: 도시 분할 계획 - JAVA문제풀이/백준 2021. 3. 1. 18:34
[백준]1647: 도시 분할 계획 www.acmicpc.net/problem/16471647번: 도시 분할 계획첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집www.acmicpc.net풀이집이 모두 연결되어 있는 상태에서 연결된 집을 두개의 마을로 나누는 문제이다. MST알고리즘을 사용하여 풀면 된다.MST알고리즘은 최소 간선을 선택해서 모든 노드를 연결한 경로를 찾는 알고리즘이다. 이 문제의 어려웠던 점은 하나로 연결된 집을 간선의 비용을 최소로 갖는 두 개의 마을로 나누는 부분이다. 처음에는 어떻게 해야 하나 감이 안잡혔지만..
-
[백준]2580: 스도쿠 - JAVA문제풀이/백준 2021. 3. 1. 14:59
[백준]2580: 스도쿠 www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 백트레킹 문제이다. ArrayList를 사용해 0이 입력된 좌표의 위치를 저장하고, list에 담긴 좌표를 하나씩 꺼내 해당 위치에 들어갈 수 있는 숫자를 찾아주었다. 없으면 다음 좌표를 탐색하도록 구현했다. list의 저장된 좌표를 모두 탐색하였다면 더 이상 탐색하지 않아도 되므로 출력을 해주고 아예 프로그램을 종료해 버린다. 여기서 종료해 주지 않고 return을 해주면 틀렸다..