HwangHub

기본적으로 두 좌표 사이의 거리의 제곱을 구하는 문제이므로 피타고라스 정리를 이용할거기 때문에 맨해튼 거리를 활용하고자 했다. 1차 시도 : 실패 실수했던 점은, 맨해튼 거리로 구하는 과정에서 답을 도출하기 전에 좌표간의 x거리와 y거리가 둘다 더 작은 경우에만 더 짧은 거리가 나올 거라고 가정한 것이다. 이제와서 생각하면 당연하게도, x거리가 기존에 구해둔 비교 대상의 거리보다 길어도 y거리가 현저히 짧으면 두 점 사이의 거리는 더 작아질 수 있다. 이를 간과하고 로직을 설계했었다. 2차 시도 : 성공 package 코드트리.완전탐색.물체탐색; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRead..

입력 조건이 아래와 같으므로 완전탐색을 하기에 충분하였다. 1 ≤ N,H ≤ 100 1 ≤ T ≤ min(N,10) 0 ≤ 밭의 높이 ≤ 200 풀이 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.NoSuchElementException; import java.util.StringTokenizer; public class Main { private static int[] arr; private static int[] ans; public static void main(String[] args) throws ..

풀이 package 코드트리.시뮬레이션.배열기록; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; import java.util.stream.IntStream; public class 만나는순간 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); St..

문제 두 사각형의 좌표가 주어질 때, 두 사각형이 겹치는 부분을 제외한 첫 번째 사각형의 영역을 덮는 사각형의 최소 넓이를 구하여라. 해석 단순한 완탐 느낌으로 접근해서, 2차원 배열에 사각형을 그리고, 첫 번째 사각형의 남는 영역을 찾아서 그 영역의 긴 변의 곱을 출력하면 되겠다 생각했다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.NoSuchElementException; import java.util.StringTokenizer; public class Main { public static void ma..

보호되어 있는 글입니다.

1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이 문제는 시간제한을 봤을 때, O(N^2)으로는 풀 수 없다. 즉, 일반적으로 우리가 떠올릴 수 있는 이중 반복문을 이용할 수 없다는 의미이다. 이렇게 시간복잡도를 고려할 때, 일반적으로 좋은 성능을 보여주는 것이 이진 탐색이다. public class B1920 { static int n, m; static int[] arr; static int[] ans; public static void main(Strin..

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 최단 기간의 경로를 구하고 있으므로 BFS가 적절한 선택일 것이다. public class B2178 { static int[] dx = {0, 1, 0, -1}; static int[] dy = {1, 0, -1, 0}; static boolean [][] visited; static int[][] arr; static int n, m; public static void main(String[] args) throws IOException { BufferedReader br = new Buf..

원래는 파이썬으로 알고리즘을 공부해왔지만, 자바로 언어를 바꿔야 할 것 같아서 풀었던 문제를 언어를 바꿔 다시 풀어보았습니다. 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net public class B11724 { static boolean visited[]; static ArrayList[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new..

11921번: 0.1 첫째 줄에 수의 개수 N = 5,000,000 이 주어진다. 둘째 줄부터 N개의 줄에는 자연수가 한 줄에 하나씩 주어진다. 입력으로 주어지는 자연수는 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 만점을 받을 수 없다고 한다. (정말 아주 간혹 자바로 풀 수 없는 문제가 있는 거라고 한다.)

1446번: 지름길 문제 해석 위 문제는 DP로 푸는 게 더 일반적인 것으로 보이는데, 다익스트라를 학습하는 단계라서 다익스트라로 풀어 보았다. 지름길 루트는 그래프에 정의해두면 될 것 같고, 모든 거리는 distance 리스트에 저장하면 될 것이다. 또한, 걸어가는 경우를 고려해야 하는데, 해당 케이스 또한 +1을 이용하여 그래프에서 뽑는 것 처럼 적용하면 된다. 풀이 코드 import heapq import sys # 입력 받기 n, d = map(int, input().split()) graph = [[] for _ in range(d+1)] INF = int(1e9) distance = [INF] * (d+1) # 간선 정보 입력 받기 for _ in range(n): start, end, cos..