본문 바로가기

TreeSet5

백준 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.
백준 2014 자바 - 소수의 곱 (BOJ 2014 JAVA) 문제 : boj2014 1. 문제 이해 문제를 다소 이해하기 힘들 수 있는데 문제를 이해하기 쉽게 써보면 다음과 같다. 예를들어 2,5,7이 입력으로 주어졌다면 이하의 수식으로 나온 결과 중 N번째로 작은 수를 구하면 되는 것이다. (단, i,j,k가 모두 0이면 안됨. 그리고 K(k와 다름. 문제에서 주어진 K) 가 늘어나면 물론 i,j,k 외에도 더 추가해주면 됨.) 2. 해결 로직 생각해보기 근데 i, j, k를 임의로 정해서 작은 수를 찾기에는 뭐부터 해야지 작은수부터 차례대로 나올지 알 수 없다. 또한 무한정 i, j, k를 늘려나가기엔 당연히 무리가 있다. 따라서 처음에 주어진 K개를 모두 넣어두고 작은 수부터 차례대로 K개의 소수를 곱해 넣고, 그 결과중에서도 다시 작은 수부터 차례대로 K개.. 2021. 12. 12.
백준 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.