알고리즘 공부
-
[JAVA] 백준 21610 마법사 상어와 비바라기알고리즘 공부/문제 풀이 2021. 10. 26. 20:19
https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static class Pos{ int row, col; public Pos(int r, int c){ row = r; col = c; } } public static void main(String[] args) throws Exception { BufferedReader b..
-
[JAVA] 백준 1766 문제집알고리즘 공부/문제 풀이 2021. 10. 23. 16:02
https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 후기 - 처음에 dfs로 풀이하려 했더니 해결 전략에 있는 반례가 존재했다 - 그림을 그려보니 진입 차수가 0인 노드들에 대해 우선순위로 뽑으며 순서를 정하면 되겠다 싶어서 정석 위상 정렬 풀이로 바꿨다 import java.util.*; import java.io.*; public class Main { public static void main(String[..
-
[JAVA] 백준 13334 철로알고리즘 공부/문제 풀이 2021. 10. 22. 14:04
https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 이런 문제는 항상 오름차순 정렬을 하고 봐야하는 것 같다. 정렬한 후에 주어진 선분을 정보의 왼쪽이나 오른쪽 끝 값에 대보며 개수를 구하고, 반대쪽에서 정답 만족하는지 체크 이 문제 같은 경우는 오른쪽에 선분을 맞춰 이동시키며 왼쪽에서 정답 만족하지 않는 출근길들 빼내기 아래 블로그가 굉장히 설명이 잘 되어있다. https://chanhuiseo..
-
[JAVA] 백준 17136 색종이 붙이기알고리즘 공부/문제 풀이 2021. 10. 18. 23:17
https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 풀이 후기 - 큰 종이를 먼저 붙이는 것은 그리디한 접근 방식이라고 할 수 있다. 하지만 언제나 큰 종이를 붙이는 건 예외가 존재하기 때문에 모든 경우를 탐색해야 한다. - N-Queen문제가 생각났는데 가능하면 진행하고 불가능하면 다음 방법을 모색한다 => 백트래킹 - 처음에는 색종이를 붙이고 땔 때 과정을 복잡하게 생각했는데, 그냥 방문 표시 했다가 진행 후 다시 백 할때 방문 표시를..
-
[JAVA] 백준 17140 이차원 배열과 연산알고리즘 공부/문제 풀이 2021. 10. 16. 14:08
https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net import java.util.*; public class Main { public static class Node implements Comparable{ int val; int cnt; public Node(int v, int c){ val = v; cnt = c; } public int compareTo(Node o){ if(cnt==o.cnt) return val-o.val; ..
-
[JAVA] 백준 16438 원숭이 스포츠알고리즘 공부/문제 풀이 2021. 10. 14. 22:32
https://www.acmicpc.net/problem/16438 16438번: 원숭이 스포츠 승민이는 동물원의 원숭이들을 관리하는 사육사입니다. 이 동물원에는 N마리의 원숭이들이 있고 원숭이들에게 1번부터 N번까지 번호를 붙였습니다. 7일간 동물원에서 원숭이들끼리 스포츠 경기 www.acmicpc.net import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); monkeys = new char[7][N]; StringBuilder sb = new StringBuilder(); for(int i=0;i
-
[JAVA] 백준 4095 최대 정사각형알고리즘 공부/문제 풀이 2021. 10. 8. 15:21
https://www.acmicpc.net/problem/4095 4095번: 최대 정사각형 입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N과 M이 주어진다. (1 ≤ N,M ≤ 1,000) 다음 N개의 줄에는 공백으로 구분된 M개의 수가 주어진다. 마지막 줄에는 0이 두 www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; St..
-
[JAVA] 백준 2638 치즈알고리즘 공부/문제 풀이 2021. 10. 7. 22:05
https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new S..