알고리즘 (18) 썸네일형 리스트형 [Algorithm/Tree] Binary Tree (이진트리) Binary Tree / 이진 트리최대 차수가 2인 트리 구조증명정리 1 : N레벨에서의 최대 노드의 수직관적으로 노드의 레벨 N의 최대 노드의 갯수는 2N-1 이다. P(N) = 2N-1 이라고 했을 때P(1) = 21-1 = 20 = 1P(N) = 2N-1P(N+1) = 2N노드의 차수는 최대 2 이므로2*P(N) = 2*2N-1 = 2N = P(N+1) 이므로 깊이가 N일 때의 최대 노드 수는 2N-1 이다.정리 2 : 트리의 최대 노드의 수일단 결과적으로 계산해 본다면 N레벨의 트리의 최대 노드의 수는 2N-1이 된다. n = 1 : 2-1 = 1 n = 2 : 22-1 = 4-1 = 3 n = 3 : 24-1 = 8-1 = 7왜 이렇게 되는가? 먼저 위와 같은 결과의 수식을 귀납법으로 증명해보겠.. [Algorithm/Math] 비트 연산으로 log2 구하기 쉽게 구한다면 while(n>1) { n/=2; count++} 이런식으로 구할 수 있겠지만 곱하기(*) 나누기(/) 연산은 생각보다 엄청나게 느리다. 보통 더하기 연산의 수십배 이상 느린 곱하기, 나누기 연산이라고 했을 때.... 그래서 아래와 같이 바꿀 수 있는데 뭔가 좀더 줄이고 싶다면 logBitCount 만에 구할 수 있다. 탐색문제나 log2로 무엇인가 구해야하는 문제가 나왔다면 곤란하기 짝이 없는데 아래와 같은 코드로 생각보다 쉽게 구할 수 있다(물론 정수 값만 가능하다.) [Algorithm/boj] 애너그램 그룹 문제 링크 : https://www.acmicpc.net/problem/6566 정말 진짜 완전 귀찮은 문제... 위 문제를 푸는 방법은 몇가지 있는데 1. 단어별로 counting sort -> 결과값(int[])을 가지고 z부터 letter별로 sort 하면 된다, 끝부터하는 이유는 사전순을 위해 (26NlogN) 2. 단어별로 counting sort -> 결과값(string) 가지고 quick sort한데, 성능은 보장 못함 (N^2ogN) 3. 단어별로 counting sort -> 결과값(int[]) 알파벳 배열을 가지고 열심히! radix sort한다, D가 낮을 경우 굉장히 유리하나 성능(DN)은 보장 못한다 ㅎ. 일단 위 3가지 푸는 방법 중 3번으로 풀었는데, 출력형식에 유의하면 될 듯.. [Algorithm/boj] 애너그램 만들기 문제 링크 : https://www.acmicpc.net/problem/1919 간단히 말해서 여러가지 쌍의 단어들을 주어지는데 각 단어의 쌍의 애너그램 거리를 찾는 것 https://gist.github.com/jinseoung-lee/7bd8981f7ff9fa521b76f837cd4951eb [Algorithm/boj] 애너그램 거리(anagram distance) 문제링크 : https://www.acmicpc.net/problem/3778 전형적인 anagram 문제, 단어의 문자를 counting한 후, 단어의 차이를 Math.abs로 계속해서 더해주면 두 단어의 anagram distance를 쉽게 구할 수 있다. [BOJ/SegmentTree] 최소값 최대값 Segment Tree로 푸는 전형적인 문제 [Algorithm/Java] BufferedReader 템플릿 알고리즘 문제를 풀다보면 가끔식 이유를 알 수 없이 timeout나는 경우가 많은데 이 경우 C/C++과 JVM언어간의 퍼포먼스 차이라기보다는 input을 얼마나 빠르게 받을 수 있는가에 따른 차이일 경우가 크다. 그래서 아래와 같이 미리 템플릿을 만들어 놓고 쓰자해서 작성해본다. [Tree] 자바로 구현한 Fenwick Tree 설명 https://www.acmicpc.net/blog/view/21 이전 1 2 3 다음