본문 바로가기

알고리즘/백준126

[Java] BOJ 11404번 플로이드 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 플로이드-워샬 알고리즘을 사용해서 해결했습니다. 자세한건 코드의 주석을 참고해주세요 코드 import java.io.InputStreamReader; import java.util.StringTokenizer; import java.io.BufferedReader; import java.io.IOException; public class Main { public static final int INF = 987654321; public static int n,.. 2021. 7. 24.
[Java] BOJ 1520번 내리막 길 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 Memoization을 적용한 DFS를 사용하여 해결했습니다. 주의할 점은 이미 방문한 지점을 파악해야 하는데 문제의 조건에 128MB라는 메모리 용량은 visited 배열을 만들면 메모리 부족이 발생할 수 있어서 대신 memo 배열을 -1로 초기화하여 -1보다 클 때, 즉 0 이상일 때 방문했음을 알게 하여 결과도 정확하게 나올 수 있게 하였습니다. 코드 import java.io.BufferedReader; import java.io.IOException; .. 2021. 7. 23.
[Java] BOJ 1717번 집합의 표현 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 풀이 분리 집합(Disjoint Set)을 사용하여 해결했습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static int n, m; public static int[] parent.. 2021. 7. 21.
[Java] BOJ 2580번 스도쿠 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 재귀함수를 사용하여 해결했습니다. 이때, 스도쿠가 성립하는 경우가 여러개이므로 맨 처음 완성된 스도쿠만 출력하고 바로 종료하게하였습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static int[][] board; p.. 2021. 7. 20.
[Java] BOJ 1987번 알파벳 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 DFS를 사용하여 해결했습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static int R, C, answer; public static boolean[] visited; public static char[].. 2021. 7. 19.
[Java] BOJ 9084번 동전 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 풀이 DP를 사용하여 해결했습니다. 문제에서 주어진 수는 너무 큰 관계로 3개의 동전 2원, 3원, 5원으로 10원을 만드는 경우를 구해보겠습니다. 1 2 3 4 5 6 7 8 9 10 2원 0 1 0 1 0 1 0 1 0 1 2원의 경우 위와 같은데 이때, 총경우의 수를 구해야 하므로 구한 결괏값을 그대로 유지하고 새로 갱신을 해나가야 합니다. 다음으로 3원의 경우를 보겠습니다. 예를 들어, 3원의 경우 앞서 2원으로 만들 수 있는 경우의 수들.. 2021. 7. 16.

티스토리툴바