초이로그

https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 게리맨더링1은 그래프 개념을 통해 쉽게 구현할 수 있었는데 2번은 배열 빡구현이라 인덱스 설정하면서 두통을 얻을 수 있었다! 다 풀고 난 뒤 보니까 규칙을 사용하신 분들도 있었는데 난 복잡할 수록 조건에 맞게 단위를 나눠서 푸는게 편해서 빡구현 했다^^. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. ▶︎ 범위에 해당하는 경우만 다음 단계를 진행한다. 다음 칸은 경계선이다. ▶︎ markFi..

이전의 숨바꼭질 시리즈와는 다르게 시간에 따라 동생의 위치가 바뀐다. == 이전에 방문했던 좌표를 재방문할 수 있다. (최소시간을 위해) == BFS로만 돌리면 메모리 초과를 맛볼 수 있다. 역시 골드1의 문제... 약간의 아이디어가 필요했다. 헤이 구글 1. 재방문의 경우, 최소 2초가 걸린다. 2. 수빈이가 각 좌표에 도달하는 최초 시간을 구한다. 즉, 각 좌표에 도달하는 최소 시간을 구한다면, 해당 좌표는 언제나 2n초 안에 돌아올 수 있다. 2n초 안에 재방문 가능하다는 것은, 최초 시간이 홀수라면 언제나 홀수 시간에, 최초 시간이 짝수라면 언제나 짝수 시간에 방문 가능하다는 것이다. 따라서 짝수로 최초 도달하는 시간, 홀수로 최초 도달하는 시간을 구분해야한다. int[][] vis = new i..

이정도 난이도의 구현문제가 그렇듯 "오? bfs/dfs 써서 구현만 딱하면 될거 같은데?" 하고 덤비면 점점 꼬이는 문제.. 7달전의 나처럼.. 게임이 진행되는 것과 같이 차근차근 케이스를 나누고 적절한 알고리즘을 대입하면 쉽게 해결할 수 있다. 1. 궁수를 배치한다. -> M개의 자리중 3개를 선택하는 문제이므로 재귀를 사용하여 조합을 구현 private static void combination(int cnt, int st) { if (cnt == 3) { // 궁수 3명 자리 고르기 완료! 조합 완성! } else { for (int i = st; i < M; i++) { archers[cnt] = i; combination(cnt + 1, i + 1); } } } 2. 완성된 조합에서, 몇명의 적..

최단 거리를 구해야하므로 BFS 문제이다. 처음에는 큐마다 방문 배열을 함께 넣어서 풀었었다. static class Point { int x; int y; boolean wall; int[][] vis; public Point(int x, int y, boolean wall, int[][] vis) { this.x = x; this.y = y; this.wall = wall; this.vis = vis; } } // ... private static int bfs() { // ... Queue queue = new LinkedList(); // ... } 하지만 N*M 최대가 1000 * 1000이다보니 배열을 계속 생성해서 메모리 초과가 난다. 그리고 처음에 메모리 초과가나는 이유가 궁금해서 찾다가 ..

코테때 못푼 PriorityQueue 문제때문에 분해서 우선순위큐 문제 조지는중이다.... 아으ㅠ오분만 더 있었다묜,,,,!! 자바의 PriorityQueue 자료구조에서 Comparator를 사용하여 새로운 정렬 기준을 정의하였다. ** Wrapper 클래스에서 새로운 정렬 기준 만드는 법(Comparator 사용) PriorityQueue pq = new PriorityQueue(new Comparator() { @Override public int compare(Integer o1, Integer o2) { if (Math.abs(o1) == Math.abs(o2)) return o1 - o2; return Math.abs(o1) - Math.abs(o2); } }); https://github.c..

"먼저 푸는 것이 좋은 문제면 반드시 먼저 푼다" 라는 말에서 나 위상정렬로 푸는거라고 광고하고 있다! 대신 3번에 가능한 쉬운 문제부터 풀어야한다는 조건이 추가되어있으므로 일반적으로 큐를 사용하는것과 달리 우선순위 큐를 사용하였다. 따로 객체를 생성하여 PriorityQueue에 저장해야하나 했으나 문제집 번호가 곧 쉬운 문제 순이므로 그냥 Integer를 사용하여 PriorityQueue를 생성하였다. 코테전에 그래프 문제 하나만 더 풀어볼껄,,, 아쉽따! https://github.com/SuyeonChoi/Algorithms/blob/master/BaekJoon/Java/%EA%B7%B8%EB%9E%98%ED%94%84/p1766.java SuyeonChoi/Algorithms Personal A..