PS/Algorithms (22) 썸네일형 리스트형 [Java] TreeSet 유용한 기능 https://coding-factory.tistory.com/555 [Java] 자바 TreeSet 사용법 & 예제 총정리 TreeSet이란? JDK 1.2부터 제공되고 있는 TreeSet은 HashSet과 마찬가지로 Set 인터페이스를 구현한 클래스로써 객체를 중복해서 저장할 수 없고 저장 순서가 유지되지 않는다는 Set의 성질을 그대로 가 coding-factory.tistory.com 제 6회 천하제일 코딩대회에서 다음의 조건에 맞는 자료구조를 사용해야했다. 1. 크기에 따라 정렬되어야함 2. 특정 수에 위, 아래로 가까운 수가 무엇인지 찾아야함 3. 자유롭게 add 가능해야함 원래 2번은 이분탐색을 하던가 할텐데 1, 3을 만족하려면 들어올 때마다 정렬해줘야 하고 그러면 LinkedList나 P.. [Java] HashMap vs TreeMap https://soft.plusblog.co.kr/70 Java Map - HashMap, TreeMap, LinkedHashMap 비교, 차이점 데이터를 모아서 관리할 수 있는 클래스를 컬렉션이라고 한다. 컬렉션은 그 타입에 따라 내부에 데이터를 저장하는 구조와 처리하는 방법이 다르다. 내부에서 처리하는 방법에 따라 데이터의 soft.plusblog.co.kr 알고리즘은 아닌데... 기억해둘 겸 적어둔다 예전에는 TreeMap이 HashMap보다 빠르겠거니 싶어서 트리만 주구장창 써왔는데 탐색이 해시는 O(1)이라는 걸 얼마 전에 알았다... 해시 원리를 모른 채 지낸 것이 문제였다. TreeMap은 RBT여서 보통 lg n이다 그래도 트리를 쓰면 인자들을 정렬된 상태로 보존할 수 있으니 쓰기 나름인듯.. [Java] Pollard-Rho Algorithm https://aruz.tistory.com/entry/factorization-3 소인수 분해 알고리즘 #3 폴라드 로 알고리즘 정수의 소인수분해는 다양한 정수론 문제에서 활용될 수 있습니다. 이 글의 시리즈에서 소인수분해 알고리즘 몇 가지를 소개합니다. Pollard`s rho algorithm 폴라드 로(Pollard`s rho) 알고리즘은 John Polla aruz.tistory.com 이 블로그에서 정말 큰 도움을 받았다. 그런데 solve의 반복문에서 큰 차이가 있는데, 반복 횟수가 1000을 넘어갈 경우 x, y, c의 값을 랜덤하게 변경하도록 수정했다. 왜인지는 도저히 모르겠는데 같은 n의 입력에 대해서도 x, y, c에 따라 결과가 달라지는 모습이 보인다 (특정 값들에서 무한루프가 되는.. [Java] Euclidean-Algorithm https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 ko.wikipedia.org 위키피디아 움짤만 봐도 바로 이해가능 import java.util.*; import java.io.*; public class euclidean { static FastScanner fs = new FastScanner(); static Prin.. [Java] Millar-Rabin primality test https://casterian.net/algo/miller-rabin.html The Casterian Home casterian.net 평범한 소수 판별은 n^(1/2)인 반면 n^(1/4)까지 줄일 수 있다. import java.util.*; import java.io.*; public class millar_rabin { static FastScanner fs = new FastScanner(); static PrintWriter pw = new PrintWriter(System.out); static int[] primes = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 27}; public static void main(String[] args) { int t .. [Java] LCA (Lowest Common Ancestor) https://pangtrue.tistory.com/262 [백준 11438 : JAVA] LCA 2 / 최소 공통 조상 문제 풀이 LCA(Lowest Common Acestor_최소 공통 조상) 알고리즘을 사용하는 기본 유형의 문제다. 해당 문제에서 주의깊게 봐둬야할 건 각 노드의 2^i 번 째 조상노드를 테이블에 저장하기 위해 DP를 사용 pangtrue.tistory.com 0. 깊이 초기화 dfs를 통해 parent[a][0] 을 각자 초기화 (부모노드의 번호) 1. parent 배열 초기화 - parent[a][b] : a번 노드에서 2^b 만큼 위의 노드 번호 2. 2^i 씩 위로 올리는 테크닉 - 1) 비교할 두 노드 중 더 깊은 노드를 위로 올려 높이를 맞춤 - 2) 2^i 씩 위로 올릴 .. [Java] Index Tree / Segment Tree Lazy Propagation https://www.acmicpc.net/blog/view/26 세그먼트 트리 나중에 업데이트 해야지! 글이 업데이트 되었습니다. https://book.acmicpc.net/ds/segment-tree-lazy-propagation 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제가 있습니다. 10999번 문제: 구간 합 구하기 2 구간 l, r (l www.acmicpc.net https://steady-coding.tistory.com/129 [BOJ] 백준 6549번 : 히스토그램에서 가장 큰 직사각형 (JAVA) 문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그.. [Java] Segment Tree https://www.acmicpc.net/blog/view/9 세그먼트 트리 (Segment Tree) 글이 업데이트 되었습니다. https://book.acmicpc.net/ds/segment-tree 문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + .. www.acmicpc.net https://steady-coding.tistory.com/126 [BOJ] 백준 2357번 : 최솟값과 최댓값 (JAVA) 문제 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와.. 이전 1 2 3 다음
