이분탐색6 백준 18384 자바 - PRIM (BOJ 18384 JAVA) 문제 : boj18384 이 문제를 풀기 위해 코드적으로 알아야 하는 것은 다음의 두가지 이다. 1. 1000000보다 처음으로 큰 소수까지의 모든 소수 2. 특정 입력에 대해 빠르게 그보다 작지않은 소수를 구하기 '1'의 경우 에라토스테네스의 체로 구할 수 있다. 참고로 1000000보다 처음으로 큰 소수는 1000003이다. 이건 정확히 몰라도 된다. 대충 1000100 까지 구하면 된다. 참고로 n이하의 모든 소수를 알기위해 에라토스테네스의 체를 사용할 때는 sqrt(n) 까지만 확인하면 된다. 이것에 대한 설명 및 증명은 이 글('에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유')에 있다. '2'의 경우 이분탐색을 활용하면 된다. c++의 upper_bound에 해당하는걸 .. 2022. 3. 22. 백준 15352 자바 - 욱제와 그의 팬들 (BOJ 15352 JAVA) 문제 : boj15352 1. 우선 '행동 2'만 존재할 경우 어떻게 풀 수 있을지 확인해보자. 입력으로 주어진 N개의 A값들에 대해 좌우로 인접한 항목이 같은 팬클럽 번호라면 그룹을 지어보자. 이 때, union-find를 사용하고 부모가 되는 노드에 차수를 입력해둔다고 한다면 '행동 2'에 대해 O(1)로 부모의 차수를 출력하는 것 만으로 결과를 낼 수 있다. 예를들어 parents[a]에 대해 parents[a] >= 0일 경우 부모의 번호, parents[a] < 0일 경우 부모 중 하나이며, 그 부모에 그룹지어져 있는 노드의 개수라고 하면 예제 입력 1은 다음과 같이 나타낼 수 있다. union-find의 사용방법은 다양한 편이므로, 어쨌든 해당 그룹에 포함된 개수를 한방에 알 수만 있도록 짜면.. 2022. 2. 4. 백준 1450 자바 - 냅색문제 (BOJ 1450 JAVA) 문제 : boj1450 1. 문제 접근 딱히 냅색과 관련없어 보이는 문제이다. N이 작아 쉽게 풀 수 있을 줄 알았다. 근데 당연하게도 모든 경우를 보면 O(2^30) 이므로 통과할 수 없다. 그렇다고 냅색처럼 DP로 풀자니 1~10^9 까지 확인해야 할 것 같으니 역시 통과할 수 없다. bit DP쪽으로도 딱히 떠오르지 않았다. 그래서 이 문제에서 적용한 방식처럼 반반을 나눠서 생각해보기로 했다. 1.1 최대 30개의 데이터를 대충 반반으로 15개씩 나눈다(사실 한쪽을 25개, 한쪽을 5개로 해도 상관없다.). 이걸 A와 B라 하겠다. 1.2 A에 대해 나올 수 있는 모든 무게 합의 경우의 수 확인하고 어딘가에 저장한다. 이 경우 최대 15번에 대해 해당 수를 포함하거나 포함하지 않거나의 2가지 경우이.. 2022. 1. 22. 백준 9847 자바 - 4SUM (BOJ 9847 JAVA) 문제 : boj9847 1. Brute Force로 가능한가? 4개의 수의 합이 0이 되는 경우를 찾아야 한다. 제일 간단하게 생각해보면 모든 쌍을 보면 된다. 이 경우 O(500^4) 이므로 유효한 시간 내에 찾을 수 없다. 2. 문제를 단순화 해보자 그럼 우선 문제를 단순화해서 생각해보자. 세트가 2개만 존재한다고 생각해보자(각 세트에 들어간 수는 N개). 그럼 각 세트에서 하나씩 골라서 2개의 수의 합은 어떻게 찾을 수 있을까? 모든 경우를 보는 O(N^2)보다 더 빠른 방법이 있을까? 두 세트가 X와 Y라고 한다면, X의 수를 정렬한 후 Y의 모든 수를 순회하면서 X에 대해 이분탐색으로 합이 0이 되는 경우를 찾을 수 있을 것이다. 그럼 O(NlogN[정렬] + N[순회]*logN[이분탐색]) 정.. 2022. 1. 8. 백준 1365 자바 - 꼬인 전깃줄 (BOJ 1365 JAVA) 문제 : boj1365 이 단어를 제가 쓰게될줄은 몰랐는데.. 'Well-Known'한 문제이다. DP쪽엔 냅색류가 유명하듯, 이분탐색쪽도 뭔가 선 꼬인거에서 안꼬이게 최대치 이런 종류의 문제가 유명하다. 사실 이런 류의 문제를 접해보지 못했다면 아이디어를 떠올리기 힘들 수 있다. 아이디어는 어떨 때 꼬이는지를 확인해보면 된다. -> 간단히 순서대로 선을 이어줄 때, 직전에 들어왔던 입력값보다 작은 값이 입력되면 꼬이게 된다. 예를들어 아래와 같은 경우 좌측의 순서대로 우측에 매칭된 숫자는 1, 3, 4, 2가 된다. 이 때 꼬인 부분은 이전보다 작은 값이 들어온 [4, 2] 부분이 된다. 그럼여러 경우를 테스트 해보면, 위와 같이 서로 겹치지 않게(안꼬이게) 하려면 단순히 subsequence(1,3,.. 2021. 12. 1. 백준 15970 자바 - 화살표 그리기 (BOJ 15970 JAVA) 문제 : boj15970 제시된 x와 y를 색상을 기준으로 나눠서 생각해보자. 즉, 문제에서 제시된 예시는 다음과 같이 나눠서 볼 수 있다. 두 경우는 연관되는 경우가 없으므로 색상이 다르다면 따로 생각해도 상관없다. 이렇게 보면, 각 색상별로 각 지점에서 좌, 우로 가장 가까운 점을 선택하기만 하면 된다. 정렬을 한 후 이분탐색으로 쉽게 찾을 수 있다. 그럼 이럴 때 쓰기 딱 좋은 자료구조가 있는데 Binary Search Tree로 구현되어 있는 TreeSet이다. 일반적으로 set은 해당 값이 들어있는지 파악하는 용도로 많이 쓰지만(hashSet 처럼), TreeSet은 이분탐색트리로 구성되어 있고 알아서 정렬되어 들어가므로 ceilling과 floor도 쉽게 구할 수 있다. 즉, 그보다 높거나 낮.. 2021. 11. 30. 이전 1 다음
