세상의 모든 Software 지식을 정리

한국 블로그 정리 잘 된글: http://hochulshin.com/data-structure-b-tree/ 외국: http://www.geeksforgeeks.org/b-tree-set-1-introduction-2/

private static boolean isPaline[][]; private static int []dp; public static void main(String[] args) { // TODO Auto-generated method stub try(BufferedReader reader=new BufferedReader(new InputStreamReader(System.in))){ char[] words=reader.readLine().toCharArray(); isPaline=new boolean[2501][2501]; dp=new int[2501]; Arrays.fill(dp,-1); int len=words.length; for(int i=0;i<len;i++){ isPaline[i][i]=true; for(int j=0;j<i;j++){ if(words[i]==words[j])isPaline[i][j]=isPaline[i-1][j+1]; if(i-j==1){ isPaline[i][j]|=words[i]==words[i-1]; } } } System.out.println(solve(len-1)); }catch(IOException e){ e.printStackTrace(); } } private static int solve(int pos){ if(pos<0) return 0; int r=dp[pos]; if(r!=-1)return r; r=Integer.MAX_VALUE; for(int i=pos;i>=0;i--){ if(isPaline[pos][i]){ r=Math.min(r,1+solve(i-1)); } } return r; }

*그리디 알고리즘 성립조건 예를들어, 여러개의 동전의 금액이 주어질 때, 다음 동전이 항상 이전 동전의 배수로 이루어질 때 Greedy알고리즘이 성립한다. 증명방법) https://www.acmicpc.net/problem/1931 이 문제에서 그리디 알고리즘에 의해 발생하는 답과 똑같은 답이 존재하는데 이를 최적해라고 한다. 이를 증명할 수 있는 방법은 그리디알고리즘으로 이루어진 답의 일부분을 최적해 답의 일부분으로 바꾸는 것이다. 그 이유는 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다. 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다. 다음 문제를 보자.  서로 다른 수 n개 a1, a2, a3, ..., an가 주어졌다. 이 중 k개(물론 k는 n보다 작거나 같은 수이다)의 숫자를 뽑아 이들의 합을 가장 크게 만들어주려면 어떻게 해야할까? 답은 간단하다. 바로 '가장 큰 숫자 k개를 뽑는 것'이다. 즉, '숫자를 뽑는 선택'을 내리는 매 순간마다 남아있는 숫자 중 '가장 큰' 숫자를 뽑는 것, 이것이 바로 Greedy Algorithm의 한 예라고 볼 수 있겠다.  그러면 Greedy Algorithm으로 얻은 답은 항상 옳을까? 이는 증명해 보아야 할 문제이다. 어떤 문제를 풀던   간에   Greedy Algorithm으로 접근하여 답을 얻었다면 이 답이 옳은지를   증명 하여야한다.   위의 문제 역시 자명해 보이지만, 엄밀하게는 증명이 필요하며 증명은 다음과 같다. 증명 ​  Greedy Algorithm으로 얻은 k개의 숫자의 집합을 G={g_1, g_2, ...

보통  인접행렬 :O(V^2)         연결리스트: O(E)을 사용하는데, 이 두개가 무의미해지는 상황이 있다. 이럴 경우는 간선을 저장하는 간선리스트를 만든다. E[0]= 1 2 E[1]= 1 5 ...... E[15]=0 4 이때 간선 0번째의 의미는 정점 1과 2를 연결하는 간선이라는 의미다 그러므로 int E[][]=new int[간선의 갯수][2]가 된다. 이를 시작정점이 몇개인지에 해당하는 배열에 저장하면 for(in i=0;i<M;i++){   cnt[E[i][0]]+=1; } 즉 cnt[1]이 2라면 1에서 시작하는 간선의 갯수가 2개라는 의미이다. 이를 누적하면 for(int i=1;i<=N;i++){   cnt[i]=cnt[i-1]+cnt[i]; } 여기서 알 수 있는 것은  i번쨰 정점과 연결된 간선은 cnt[i-1]부터 cnt[i]-1까지이다. 왜냐면 누적값이므로.. 즉 3번정점과 연결된 간선은 cnt[2]~cnt[3]-1     4번정점과 연결된 간선은 cnt[3]~cnt[4]-1

만약 Node라는 클래스를 만들고 이를 PriorityQueue에 보관할 때, 크기를 비교하기 위해서는 Comparable를 구현해야 한다. 이때,  크기 비교는 compareTo를 오버라이딩 해야한다. 예) PriorityQueue<Node> pq=new PriorityQueue<Node>(); //우선순위 큐에 중복되는 number가 있는지 확인 Node temp=new Node(10); if(pq.contains(temp))//-------------------------------->equals메소드에 의해 중복이 있으면 true를 반환한다. Class Node{   int count;   int number;   public Node(long number){ this.number=number; this.count=0; } @Override public int compareTo(C o) { long otherNumber=o.number; int otherCount=o.count; // TODO Auto-generated method stub if(this.count>otherCount){ return -1; } else if(this.count==otherCount){ if(this.number<otherNumber) return -1; else return 1; } else   return 1; } }

Stable Sort란 배열안의 숫자를 정렬시키는데, 이때 만약 같은 숫자가 존재할 경우, 먼저 들어온 숫자를 나중에 온 숫자보다 앞에 오게 정렬시키는 것이다. 시간복잡도가 O(nlogn)인 경우는 병합정렬(mergeSort)가 해당되고 O(n^2)인 경우는 버블소트(BubbleSort)가 해당된다.

<첫번째 방법> 소수 N=a*b 제일 작은 소수는 2이므로 b는 최대 N/2이다. 즉 , int i=2 부터 i<=N/2까지 탐색하면 된다. 하지만 시간 복잡도는 여전히 O(n)이다. <두번째 방법> 소수인 숫자 N= a*b일 때, 두 수중 하나는 a<=루트N 또는 b<=루트 N이다. 만약 두 수 모두 a>루트N and b>루트 N 이면 a*b는 N보다 커진다. a<=b라고 하면 예를들어, 루트 24=4.xxxxx 그러면 숫자 a는 2, 4, 6, 8, 12라 했을 때, 2,3,4 계산해보면된다. 즉,   for(int i=2;i*i<=N;i++){     if(N%i==0)         return false;  }  return true; 결국 시간복잡도는 O(루트N이다) <에라토스테네스의 체> N=100인 소수의 갯수를 찾는다 치면 2가 소수이므로 2의배수는 모두 지운다. 3이 소수이므로 3의배수를 지운다 5가 소수이므로 5의 배수를 지운다. ..... N는 10까지만 시행한다. *백준-골드바흐의 추측 문제에서 N의 범위가 1백만인데 그 소수를 저장하고 탐색하는 것이  소수를 true,false로 한 것보다 빠르다. 그 이유는 루트N까지가 리스트에 담겨잇으므로.

여러개의 숫자가 있다. 예를들어 3 8 2 8 2 3 1 즉, 1을 제외한 나머지 숫자들은 2번씩 중복된다. 이때 1의 값을 찾아라 풀) 해쉬맵 사용 그러나 복잡도가 O(n) , 그러나 O(1)으로 가능하다. XOR이용 XOR특성 1 7 9를 XOR하면 1 7 9의 성분이 남아있다 그러나 여기서 다시 7을 XOR하면 1 9만 남는다. 즉 이런식으로 0의 값을 다 하게 되면 마지막에 유니크 Integer 값만 남는다.

GCD(a,b)=GCD(a,a%b) 예를들어 24, 18이 존재할 때 GCD(24,16)=GCD(16,8)=GCD(8,0) 그럼으로 최대공약수는 8이다. int gcd(int a,int b){   if(b==0){     return a;  }   else{       gcd(b,a%b);   } }

첫번째, 재귀를 이용한 방법 (Directed Graph) http://www.geeksforgeeks.org/detect-cycle-in-a-graph/ (Undirected Graph) http://www.geeksforgeeks.org/detect-cycle-undirected-graph/ 두번째, Stack을 이용한 방법 --->방문한 점인데, 현재 Stack안에 그 노드가 있으면 Cycle이다. --->st.contains(k) void DFSUtil(boolean visited[], int i, Stack<Integer> st) { st.push(i); visited[i] = true; for (int k : adj[i]) { if (!visited[k]) DFSUtil(visited, k, st); else if (st.contains(k)) flag = 1; } if (flag != 1) st.pop(); } void DFS() { Stack<Integer> st = new Stack<Integer>(); boolean visited[] = new boolean[V]; for (int i = 0; i < V; i++) { if (!visited[i]) DFSUtil(visited, i, st); } }

*트리 정점: V개 간선: V-1개 그렇다면 위 두 조건을 만족하는 것은 트리다???NO O-O   O-O O 이 처럼 왼쪽 세개는 다 연결되어 사이클을 이루고 나머지 두개는 따로 인경우가 있을 수 있다. 결국 3가지조건을 만족해야 한다. 1. 정점이 V개 2. 간선 V-1개 3. 모두 연결되어 있다. <조상, 자손 개념> 자기자신도 조상,자손이 된다. 예를들어 5가 단말노드고 5->2->1(루트노드)일때, 5의 조상노드느 5,2,1 3개 모두 해당된다. <이진트리 종류> 1. 포화 이진트리(Full Binary Tree) 잎 노드를 제외한 모든 노드가 자식을 둘씩 가지고, 또한 모든 잎 노드들이 높이가 같다. 가장 안정적인 구조이다. 2. 완전 이진 트리(Complete Binary Tree) 잎 노드들이 왼쪽부터 차근차근 채워지는 것이 특징. 트리를 이용한 검색에서는 완전한 모습에 가까울 수록 높은 성능을 보인다. 그러니 데이터를 배치할 때는 최대한 완전이진트리에 가깝게 배치한다. 3. 높이 균형 트리(Height Balanced Tree) 루트노드를 기준으로 왼쪽 하위트리와 오른쪽 하위트리의 높이가 1이상 차이나지 않는 트리 4. 완전 높이 균형트리 왼쪽 하위트리의 높이와 오른쪽 하위 트리의 높이가 같은 것

*트리 정점: V개 간선: V-1개 그렇다면 위 두 조건을 만족하는 것은 트리다???NO O-O   O-O O 이 처럼 왼쪽 세개는 다 연결되어 사이클을 이루고 나머지 두개는 따로 인경우가 있을 수 있다. 결국 3가지조건을 만족해야 한다. 1. 정점이 V개 2. 간선 V-1개 3. 모두 연결되어 있다.

트리에서 정점 두개를 잡고 거리를 구한다. 그런데 이렇게 되면 O(n^2)이된다. 하지만 dfs 2번 돌려서 O(n)에 해결할 수 있다. 1. 아무 정점(루트)를 잡고 , 이 점에서 가장 거리가 먼 점 t를 잡는다. 2. t에서 가장 거리가 먼 점 u를 찾는다. 3. t~u가 트리의 지름. 끝 (증명):  https://www.quora.com/How-does-following-algorithm-for-finding-longest-path-in-tree-work 따라서 이러한 점 C는 존재하지 않는다. 문제:  https://www.acmicpc.net/problem/1167