HwangHub

문제 링크 해석 공유기를 설치하는 거리를 x라고 할 때, x를 이분 탐색으로 구하여 답을 도출할 수 있다. 답을 가정할 때, 특정 구간에서는 해당 답이 거짓이고, 특정 구간에서는 해당 답이 참일 수 있는 경우에는 이분탐색을 통한 답 도출을 하는 "parametric search"를 활용할 수 있다. 이 문제는 공유기 설치를 어느 거리로 해야 최대 거리로 설치할 수 있는지 묻는 문제로, parametric search 문제 중 대표 유형인 "칸막이 설치" 유형이라고 할 수 있다. 로직 기본적으로 이분탐색을 통해 찾는 값이 "가장 가까운 라우터끼리의 거리"이다. 라우터 좌표를 배열에 저장하고 정렬한다. 배열을 순회하면서 누적 거리를 재고, 이분탐색을 통해 설정한 '기준 거리'를 넘어갈 때 routerCnt를..

문제 링크 해석 이 문제는 조합과 그래프 탐색을 조합하여 푸는게 일반적인 방식이다. 하지만 유니온파인드로 풀어보라고 제안을 받아서 이를 이용하여 "부분집합 + 유니온파인드"로 풀었다. 정점의 개수가 N, 간선의 개수가 E라고 할 때, 유니온파인드 시간복잡도가 O(E * log N)이고, 부분집합의 시간복잡도가 선택하냐 마냐이므로 O(2^N)이다. 따라서 내가 구성한 로직은 O(2^N * E) 인데, 10! 이 약 4백만이고, N이 10까지이므로 1초 내로 구성할 수 있을 것으로 판단했다. 풀이 코드가 길고 지저분해서, 만약 코드를 보고자 하는 분은 흐름을 먼저 체크해주시길 바란다. /* * 1. 부분집합을 구한다. * * 2. 구해진 부분집합을 기준으로 선거구로 가능한지 체크한다. * -> adj 리스트..

문제 문제 링크 해석 이 문제는 대표적인 분할정복 문제다. 분할정복은 재귀를 이용하여 큰 문제를 작은 문제로 나눠서 해결하는 알고리즘이라고 한다. 이번에 학습하면서 연습문제 삼아 풀어봤다. 이것과 더불어 Z라는 문제도 유명하다. 나는 누적합을 같이 적용하여 풀었고, 기준에 미치지 못하면 재귀를 타고 들어가서 처리할 수 있도록 분할정복 로직을 구성하였다. 코드 public class BOJ_1992_쿼드트리 { /* * 실행시간 : 264 ms * * 메모리 : 17020 KB * */ static int[][] ps; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new In..

문제 문제 링크 해석 그리디는 "언제나 최선"인 경우라는 기준이 존재하여, 그 기준을 바탕으로 차례대로 선택하는 것이 가능할 때, 정렬이나 특정 연산을 통해 전체 연산을 최적화하는 알고리즘이다. 이 문제는 그리디 알고리즘 개념학습 마지막 문제이며, 이를 해결하기 위해서는 직관적으로 알 수 있듯 "가장 앞의 숫자가 큰 숫자를 먼저 고른다." 가 첫 번째 기준이 되어야 한다. 그리고 두 번째 조건이 중요한데, "가장 앞자리의 숫자가 동일할 경우, 두 세 번째 숫자도 체크해야 한다."는 게 고려되어야 한다. 즉, 결국 모든 숫자를 체크해야만 할 것 같은 느낌이 든다. 하지만 이를 잘 생각해보면, 일단 앞 자리 기준으로 큰 숫자를 먼저 앞으로 배치하되, 만약 앞자리가 같다면 직접 붙여봐서 더 큰 경우가 될 때의..

문제 링크 해석 이 문제는 그리디를 연습하기 위한 문제로, 그리디 로직을 구성하는 기준에 따라 그리디를 적용할 수 있고 없고가 존재함을 이해할 수 있었다. 회의실을 최대한 많이 잡아야 하는 문제인데, 고려해야 하는 요소가 두 가지이다. 회의 시간이 짧은 것으로 최대한 골라야 많은 회의를 잡을 수 있으며, 겹치지 않도록 시작 시간과 끝 시간을 검사해야 한다. 이 두 가지를 동시에 고려하면서 그리디하게 풀어내기 위해서는 회의가 끝나는 시간을 기준으로 오름차순 정렬을 해야 한다. 이 지점만 캐치할 수 있으면 로직은 어렵지 않다. 코드 public class Main { public static void main(String[] args) throws IOException { BufferedReader br =..

문제 링크 해석 어제 백준을 풀면서 플로이드워셜을 학습하고, 잊지 않기 위해 개념 문제를 하나 더 풀었다. 여기서는 플로이드워셜 로직을 활용하여 "직 간접적으로 각 정점끼리 연결되어 있는지 여부"를 검사하는 로직을 구성하게끔 유도한다. 단순한 문제였으므로 코드로 대신한다. 코드 package 알고리즘연습.codetree.그래프.플로이드워셜; import java.io.*; import java.util.StringTokenizer; public class CodeTree_행렬로주어진간선 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(..

문제 백준 17182. 우주탐사선 해석 "중복으로 노드를 방문 가능하다"는 점에서 최소신장트리를 구하는 알고리즘보단 플로이드워셜을 사용하는 게 적절하겠단 판단을 했다. 그렇게 각 노드 간 weight 계산을 마치고 나서는, N이 10까지이므로 완전탐색을 이용하여 최소 비용 합을 계산하면 되겠다고 판단했다. 결론 : 플로이드워셜 + 순열(next permutation)을 이용하여 완탐을 돌아서 최소 비용을 계산했다. -- 더 배우고자 다른 이의 코드를 보고 뜯어봤는데, 다른 이는 DFS를 이용하여 최소 비용 합을 계산하였다. 눈에 띄는 차이는 플로이드 워셜을 사용할 때 방문 노드를 체크하지 않았던 점이다. 나의 경우에는 플로이드 워셜을 하면서 각 노드 간 weight를 계산할 때 애초에 다른 노드를 방문하..

문제 링크 해석 숫자 리스트 중 매번 가장 최소의 숫자 두 개를 골라서 합치는 비용을 더해주면 되는 문제이다. ArrayList를 이용해서 매번 정렬을 수행하며 숫자를 관리해도 되지만, 이 문제에 한해서는 힙을 사용하는 게 더 효율적이라 봐서 PriorityQueue를 적용해 풀었다. 코드 public class Main { /* * 수행시간 : 678 ms * * 메모리 : 27 MB * * 시간복잡도 : O(N * logN) * */ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw..

문제 문제 링크 해석 이 문제는 fractional knapsack 유형을 학습하기 위한 연습문제여서 로직 구성을 고민하진 않았다. 딱 한 가지 레슨런이 있다면, 단위 가치 순으로 정렬을 하기 위해 나는 최초 로직에서 트리맵을 사용하려고 했다. 를 트리맵에 넣어서 정렬을 내가 별도로 처리하지 않고 자료구조로 퉁치려고 했는데, key는 중복을 허용하지 않는단 사실을 뒤늦게 알고 아차 했었다... 실전에서는 이런 사소한 디버깅을 하기 어려울 거고, 시간도 부족하니 그냥 정렬 하기 귀찮다고 트리 구조를 이용하는 로직 구성은 하지 않기로 결심했다...(나름의 레슨런) 만약 자료구조를 이용해서 정렬 로직을 대신하고 싶다면 웬만해선 데이터 그룹을 클래스로 묶어서 우선순위큐를 활용하는 게 이롭다. 단, 주의할 점은,..

문제 문제 링크 해석 최대최소값과 같은 최적화를 요구하는 게 아니라 그냥 단순한 계산값을 요하는 문제라서, 입력이 주어질 때 규칙에 맞게 배치해주면 된다. 점수계산은 모두 자리에 앉은 이후에 해야 정확하므로 나중에 다시 N^2만큼 순회해야 한다. 말 그대로 주어진 조건을 코드로 구현할 수 있는지 묻는 문제로 보였다. N도 20까지라서 편하게 구현하면 되는 걸로 봤다. 한 가지 고민을 잠깐 했던 게 있는데, 3번째 조건의 경우 뭔가 정렬을 해야 할 것처럼 겁을 주는(?) 느낌이 들었는데, 애초에 로직이 행렬 순으로 순회하면서 입력을 하므로 별도로 정렬할 필요는 없는 것으로 판단할 수 있었다. 코드 package 알고리즘연습.boj; import java.io.*; import java.util.ArrayL..