세상의 모든 Software 지식을 정리

자바에서는 Card c=new Card(); System.out.println(c)와 System.out.println(c.toString())과 같다. 그 이유는 PrintStreamClass에는 print메소드가 있다. public void print(Object obj){    write(String.valueOf(obj)); } public static String valueOf(Object ob){      return (obj==null)?:"null":obj.toString(); }

*링크드 리스트의 탐색시간은 O(N)이 걸린다. 그래서 자료의 탐색에는 별로 좋지 않다. 그러나 이를 응용한 Skip List를 사용하면 O(logN)에 구현이 가능하다. 이 원리는 다음과 같다. 스킵 리스트 SKIP LIST 스킵 리스트 이해하기 스킵 리스트는 정렬된 상태를 유지하면서 데이터를 삽입, 삭제하고 탐색할 수 있는 데이터 구조체(data structure)이다. 여기 설명은  윌리엄 퓨(William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Tress)  의 논문(1990년 발표)에 근거해 설명한다.   살바토르도 이 논문을 바탕으로 Sorted Set에 사용되는 스킵 리스트를 구현했다. 스킵 리스트는 링크드 리스트의 단점을 개선하는 데서 시작한다.   여기서 설명하는 링크드 리스트는 정렬된 상태를 유지하는 리스트이다.   이런 링크드 리스트에서 n 번째 node를 찾으려면 n 번 비교를 해야 한다. 아래 그림에서 보는 것처럼 값이 '80' 인 노드를 찾으려면 비교를 9번 해야 한다.   최악의 경우 모든 노드를 비교해야 한다.   그림 1-a   정렬된 링크드 리스트 레벨을 갖는 스킵 리스트 탐색 시간을 단축하기 위해서는 비교 횟수를 줄여야 한다.   여기서 아이디어를 낸 것이 노드에 포인터를 두 개를 갖게 해서 두 번째 포인터는 하나 건너뛰어서 다음 노드를 가리키도록 한다.   그림 1-b   레벨 2 스킵 리스트 위 그림에서 보는 것처럼 홀수 번째 노드는 포인터 하나만 갖고, 짝수 번째 노드는 포인터를 두 개 갖은 것이다.   이렇게 구현하면 하나씩 건너 뛰어 비교할 수 있기 때문에 n 번째 노드를 찾는데 n/2 + 1 번 비교하면 된다.   비교 횟수를 반으로 줄이는 획기적인 아이디어이다.   값이 '80' 인 노드를 찾는데 비...

한국 블로그 정리 잘 된글: 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...

보통  인접행렬 :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; } }