HwangHub

🤔 Intuition아이디어를 떠올리기 어려워 결국 다른 이의 풀이를 참고했다. 요지는, 전체 부분수열을 부분집합 알고리즘으로 탐색하게 되면 (2 ^ 40) 정도라서 시간을 초과하지만, 이를 절반씩 쪼개서 부분집합을 구하면 (2 * 2 ^ 20) 이라서 시간이 터지지 않는다. 따라서 이를 절반으로 쪼개어 부분수열의 합을 구한 뒤, 한쪽 절반의 부분수열의 합을 기준으로 다른 반쪽의 부분수열의 합과 더한 값이 S가 될 때의 개수를 세주면 된다.🔎 Algorithm & Complexity * @algorithm backtracking (powerset)* @time O(2^N/2) : 976 ms* @memory O(N) : 96908 KB 👨🏻‍💻 Logic오른쪽 반 쪽의 부분수열의 합을 먼저 구..

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 🤔 Intuition 처음에는 DP라고 생각했다. 근데 아니였다. DP가 성립하려면 2가지 조건을 성립해야 한다. 부분 반복 문제 (Overlapping subproblem) : 어떤 문제가 부분 문제로 쪼개질 수 있는지 최적 부분 구조 (optimal substructure) : 부분 문제에서 구한 최적의 답이, 원래 문제의 최적의 답과 동일한지 이 문제를 통해 위 조건을 검토해보자면, 부분 반복은 된다. 왼쪽으로 한칸, 오..

🤔 Intuition 시뮬레이션 문제인 것은 확실하나, 탐색을 어떻게 할지 고민하였다. 우선되는 먹이의 조건이 (1) 거리가 가까울 것 (2) row가 작을 것 (3) column이 작을 것 이었으므로 델타탐색을 "상 좌 우 하" 로 하면서 가장 먼저 나오는 먹이를 낼름 먹어버리면 될 것으로 봤다. 하지만 위는 틀렸다. 위의 경우에는 항상 거리값이 가장 가까운 먹이를 찾을 수 있지만, 바로 만난 먹이가 가장 위에 있고, 가장 왼쪽에 있다는 것을 보장할 수 없다. 아래 예시를 보면 이해가 가능하다. private static int[] dy = {-1, 0, 0, 1}; private static int[] dx = {0, -1, 1, 0}; . . 1 . . . 2 x 3 . 4 x C x 6 . 5 x..

문제 링크 해석 공유기를 설치하는 거리를 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..

지난 실력진단 문제에서 구성되는 마을의 최대 크기라던지, 마을의 개수를 어떻게 구할 수 있을지 쉽게 떠오르지 않았어서 해당 부분을 연습하기 위해 이 문제를 다시 풀어봤다. 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 접근 이 문제는 단순 반복문을 통해서는 나의 한계로 로직이 떠오르지도 않거니와, 있더라도 분명히 매우 복잡할 것이므로 패스하였다. 그 외에 순열, 조합과 같은 경우의 수를 탐색하는 경우도 아니고, 최대최소를 얻는 그리디한 바이브의 문제도 아니였다. 탐색 알고리즘 중에 이웃한 항과의 관계를 통해 답을 도출해 내는 그래프 알고리즘이 이 문..