SK_MOUSE 개발일기

2467 용액 #소스코드 : 모든용액에 대하여 한가지를 잡고, 나머지 한 용액은 이분탐색으로 찾음. 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)); int n = Integer.parseInt(br.readLine()); int[] lq = new int[n]; StringTokenizer st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { l..

투포인터 https://www.youtube.com/watch?v=rI8NRQsAS_s 투포인터,구간합 알고리즘 강의 나동빈 처음에는 투포인터 문제인지 모르고 풀었다. 그 풀이는 아래와 같다. 풀이 한 코드가 너무 아까워서 남겨둔 것이니, 투포인터 풀이를 보려면 더 아래로 내려가서 확인하면 된다. import java.util.*; import java.io.*; public class Main { static int n; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // StringTokenizer st = n..

dfs 방식으로 접근하면 풀리는 문제이다. 적록색약인 사람일때의 탐색용 배열은 R과 G를 한쪽으로 통일 시켜서 배열을 저장해서 dfs해주면 된다.(replaceAll 사용) import java.io.*; import java.util.*; public class Main { static int N; static char[][] org, rg; static boolean[][] visited; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(b..

BFS 아니고, 다익스트라 알고리즘 문제이다. 두 알고리즘 용도가 헷갈렸는데, 아래 정리해보았다. BFS탐색: 시작점으로부터 어떤 정점까지 너비우선적으로 탐색한다. 최단경로를 구할 때 사용할 수도 있다. 다익스트라: 시작점으로부터 나머지 모든 정점까지의 최단경로를 구할 때 사용 다익스트라 위 문제에서는 아래 코드가 키 포인트다. static final int INF = 1000000000; static List[] list = new ArrayList[1001];//리스트 배열 static int[] dist = new int[1001]; private static void dijkstra(int start) { Queue pq = new PriorityQueue((a, b) -> a.dist - b.d..

플로이드 워셜 문제로 풀어야 시간초과가 나지 않는 문제이다. 단뱡향 노드로 모든 길에 대한 값이 들어가있는 문제에서 사용! 시행착오 1. BFS로 각각의 케이스에 대해서 따로 최단거리를 구하려했다 => 파티장의 크기 N(5 ≤ N ≤ 500) , 파티장의 번호, C(1 ≤ C ≤ 1,000,000,000) 이므로 BruteForce(N * N = 2500)로 한번에 모든 거리를 구해놓아야 한다는 것을 깨달았다. 2. 완전탐색(Brute-Force)으로 모든것을 탐색할때 BFS방식으로 탐색했다. => 이미 진행한 길에 대해서 추가적인 낭비 노드가 발생한다. 따라서 플로이드 워셜로 순차적으로 업데이트 해나가는 삼중for문 방식이 더 효율적인 것을 알 수 있었다. import java.io.*; import ..

주의할점 1. 학번은 Integer형이 아닌 String으로 받아야한다. (예를들어 012345678이라는 학번은 Integer형으로 받을시 1234578로 데이터의 변형이 발생한다.) 2. (수강가능인원) > (대기목록의길이) 인 경우를 생각해아한다. ((IndexOutOfBounds) 발생 가능성) 처음 작성한 코드. HashMap을 통해서 중복제거와 동시에 우선순위를 뜻하는 key를 넣어준다.(순서 역할) ArrayList에 위 key를 이용한 Student 객체를 넣어주고 정렬한다. ArrayList에서 필요한 객체를 순서대로 반환한다. import java.io.*; import java.util.*; public class Main { static int k, l; static HashMap ..

처음에는 하나씩 증가하면서 수를 순서대로 잘라서 넣어주는 방식으로 진행했다. 하지만, 그런식으로 진행하게되면 최대값이 몇인지 몰랐고, 효율성 측면에서 순열이 더 좋다고 하여 방식을 바꾸었다. 각각의 경우에 대하여 일의자리 수에 따른 경우의 수를 구한다 일의자리수 각각에 대하여 아래와 같은 방식으로 미리 계산한다. 0: 0 1: 1, 10 2 : 2, 20, 21, 210 3 : 3, 30, 31, 32, 310, 320, 321 ... 참고로 가장 큰 숫자는 9876543210 이다. 즉, 열자리 숫자이며 이 경우 2^10 -1 = 1024-1 = 1023개이다. list.size()를 출력해보면 위 결과를 얻을수 있었다. 1023개를 꼭 알아야할 필요는 없다. import java.io.*; impor..

https://www.acmicpc.net/problem/16401 이분탐색 문제였다. 처음에는 Priority Queue로 각각의 경우를 나눠주는 방식으로 접근했지만, 아래 예시와 같은 경우를 따지려니 실패하였다. ex) 3명의 조카에게 1개의 과자 3cm인 경우=> 3등분 해야함. 따라서 위 방식은 잘못되었음을 깨닫고 이분탐색 방식으로 진행해야했다. import java.io.*; import java.util.*; public class Main { static int[] arr; static int m, n,result; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(..

import java.io.*; import java.util.*; public class Main { static int[] memo, arr; static int n; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine()); StringTokenizer st = new StringTokenizer(br.readLine()); arr = new int[n]; memo = new int[n]; for (int i = 0; i < arr.length; i++) ..

누적해서 합을 구한 값을 배열에 넣고 각 시행마다의 덧셈을 최소화 시키는 방식을 선택했다. 위 방식대로 하면 효율성이 좋은 코드가 나올 수 있다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N, M; static int[][] grid; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)..