BOJ
-
[백준]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..
-
[백준]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..
-
[백준]17289. 오큰수 - Java알고리즘/백준 2021. 2. 19. 01:17
📄 링크 boj 17298. 오큰수 💡 문제 분석 N * N으로 모든 경우를 비교하면 시간 초과가 납니다 O(N) 방법 순서대로 스택에 숫자를 넣을 때, 스택에 숫자가 들어있다면 현재 넣을 숫자와 비교해 봅니다 만약 현재 넣을 숫자가 더 크다면, 스택에 있는 숫자들의 오큰수는 현재 넣을 숫자가 됩니다 마지막 숫자까지 스택에 넣었다면 모든 오큰수를 구한 것이 됩니다. ⌨️ 코드 public class _17298_오큰수 { static class Pair { int idx, n; Pair(int idx, int n) { this.idx = idx; this.n = n; } } public static void main(String[] args) throws IOException { BufferedReade..
-
[백준]16639. 괄호 추가하기 3알고리즘/백준 2021. 1. 10. 23:58
[백준]16639. 괄호 추가하기 3 📄 링크 괄호 추가하기 3 💡 문제 분석 수식을 입력받고 여기에 괄호를 임의로 추가하여 최대값을 구하는 문제입니다 이 문제의 핵심은 괄호를 마음대로 넣을 수 있기 때문에 연산자의 우선순위는 아무런 의미가 없다는 것입니다. 그렇기 때문에 괄호를 넣을 수 있는 모든 방법으로 완전 탐색을 진행하고 캐시에 저장해서 해결하였습니다 하지만 이 문제에서 *연산을 할 때 음수 * 음수를 했을 때 가장 큰 수가 나올 수 있기 때문에 가장 작은 값들도 계속 저장을 하고 있어야합니다. Calc(max, max) Calc(max, min) Calc(min, max) Calc(min, min) 4가지 계산을 모두 해서 가장 큰 수는 max 캐시에, 가장 작은 수는 min 캐시에 저장합니다 ..