알고리즘/백준
-
[백준]1012. 유기농 배추 (java, python)알고리즘/백준 2021. 4. 19. 14:24
링크 유기농 배추 문제 분석 컴포넌트의 개수를 구하는 문제입니다 bfs 또는 dfs를 돌며 모든 1을 탐색합니다 탐색 알고리즘을 실행한 횟수가 답이 됩니다 코드 JAVA import java.util.*; public class Q1012 { static int N, M, K; static boolean[][] map; static int[] dy = {-1, 0, 1, 0}, dx = {0, 1, 0, -1}; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int tc = sc.nextInt(); while(tc-- > 0) { M = sc.nextInt(); N = sc.nextInt(); K = sc.nex..
-
[백준]1011. Fly me to the Alpha Centauri (java, python)알고리즘/백준 2021. 4. 19. 14:24
링크 Fly me to the Alpha Centauri 문제 분석 풀이 1(java) 문제의 핵심은 거리 값이 좌우 대칭이 된다는 것입니다 처음과 끝은 1이 되어야하므로 1 1 2 2 3 3 4 4 ... 이렇게 더해나가다가 전체 거리를 초과한다면 최소 작동 횟수를 얻을 수 있습니다 풀이 2(python) 규칙 하나를 깨닫는다면 짧은 코드로 풀 수 있습니다 2^2 = 1 + 2 + 1 3^2 = 1 + 2 + 3 + 2 + 1 4^2 = 1 + 2 + 3 + 4 + 3 + 2 + 1 코드 JAVA import java.util.Scanner; public class Q1011 { public static void main(String[] args) { Scanner sc = new Scanner(Sys..
-
[백준]1010. 다리 놓기 (java, python)알고리즘/백준 2021. 4. 19. 14:23
링크 다리 놓기 문제 분석 중복되지 않게 M개에서 N개를 선택해야 함 -> 조합!! m C n 위 공식을 사용할 수도 있지만 DP를 이용해서 해결해보았습니다 nCr = n-1Cr-1 + n-1Cr python3.8이상이라면 math.comb 메서드를 이용할 수 있습니다 코드 JAVA import java.util.Arrays; import java.util.Scanner; public class Q1010 { static int n, m; static int[][] cache; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int tc = sc.nextInt(); for(int t = 1; t
-
[백준]1008. A / B (java, python)알고리즘/백준 2021. 4. 19. 14:22
링크 A / B 문제 분석 두 수 를 입력받고 몫을 출력합니다 java 풀이일 경우 타입을 신경써서 해결합니다 코드 JAVA import java.util.Scanner; public class Q1008 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); double ret = sc.nextDouble() / sc.nextDouble(); System.out.printf("%.12f", ret); } } PYTHON a, b = map(int, input().split()) print(a / b)
-
[백준]1005. ACM Craft (java, python)알고리즘/백준 2021. 4. 19. 14:21
링크 ACM Craft 문제 분석 풀이 1(java) bfs의 시작점이 될 루트 노드들을 찾아서 큐에 넣습니다 BFS를 진행하며 노드들을 방문하며 가장 오래 걸린 시간을 저장합니다 풀이 2(python) 풀이 1과는 반대로 목표 지점에서 시작합니다 간선 연결을 반대로 연결해줍니다 DP(cur) = MAX(DP(prev)) + time[cur] DP를 이용하여 해결합니다 코드 JAVA import java.io.*; import java.util.*; public class Q1005 { static int stoi(String s) { return Integer.parseInt(s); }; static int N, K, ret, e; static int[] time, visit; static ArrayL..
-
[백준]1003. 피보나치 함수 (java, python)알고리즘/백준 2021. 4. 19. 14:20
링크 피보나치 함수 문제 분석 기본적인 다이나믹 프로그래밍 문제입니다 f(N) = f(N - 1) + f(N - 2) 를 구현합니다 N이 1일 때, 2일 때를 기저 조건으로 설정합니다 파이썬 코드는 타뷸레이션, 슬라이딩 윈도우로 해결했습니다 이 전 두 개의 값만 알면 되기 때문에, a와 b만 유지하며 해결합니다 코드 JAVA import java.util.Scanner; public class Q1003 { static int[] cache; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int tc = sc.nextInt(); cache = new int[42]; cache[0] = 0; cache[1] = 1..
-
[백준]1002. 터렛 (java)알고리즘/백준 2021. 4. 19. 14:19
📄 링크 터렛 💡 문제 분석 원의 반지름에 따라 거리 계산을 합니다 ⌨️ 코드 JAVA import java.util.Scanner; public class Q1002 { static class P { int x, y, r; public P(int x,int y, int r) { this.x = x; this.y = y; this.r = r; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int tc = sc.nextInt(); for(int t = 1; t d){ System.out.println(0); } else { System.out.println(2); } } } } public static do..