세상의 모든 Software 지식을 정리

Largest Sum of Averages 동적 계획법으로 첫번째 인덱스는,  i 번째 부터 시작하는 수 두번 째 인덱스는, K 번 그룹을 지칭 즉, d[i][k]는 K번째 그룹일 때, i번째 부터 시작하는 수. d[i][k] = max(d[i][k], search(i, k-1) + curr/ (n-i)); --> n-i는 끝에서 부터 i 번째 까지 --> curr 은 i번째 부터 n번째 까지의 합(그때가 K번째 그룹)

with Binary Search Tree, To require O(1) average Time(amortized analysis) and O(h) space. O(h) 공간을 만족하기 위해서, 루트 노드의 왼쪽값만 저장한다. 그 후 next()값을 호출시, 방금 출력된 값보다 큰 root.right를 삽입하여 O(h) 공간을 만족시킨다. Stack<TreeNode> treeList; public BinarySearchIterable(TreeNode root) {     while(root != null) {         treeList.push(root);         root = root.left;     }   }  public boolean hasNext() {       if(treeList.isEmpty())           return false;     return true;   }  public int next() {       if(hasNext()) {           TreeNode n = treeList.pop();           int value = n.value;           treeList.push(n.right);       }   }

B-Tree는 self-balancing 탐색 트리로. 거의 모든 데이터가 메모리상에 존재한다고 보면된다. 그러나 데이터량이 커지면 이 모든 것을 메인 메모리에 보관할 수 없다. 만약 key의 숫자가 커질 수록, 데이터들은 디스크에서 정보를 가져올 수 밖에 없다. 디스크 액세스 타임의 비용은 메인메모리 액세스 타임보다 훨씬 비용이 크다. B-Tree의 핵심은 디스크 액세스타임을 감소 시키는 것이 목적이다. B-Tree의 높이 h는 디스크 접근의 횟수와 비례한다 즉, 이것에 따라 성능이 결정된다. B-Tree의 PseudoCode는 다음과 같다. 1. B트리의 검색 (B-Tree-Search) 2. 빈 트리 생성 (B-Tree-Create) 3. B트리에 삽입 (B-Tree-Insert) 4. B트리 분할 (B-Tree-Split) 1. B트리의 검색 (B-Tree-Search) B-Tree-Search (x, k)  // x is node, k is value what we find. i = 1 while i<= x.n && k > x.key(i)  i= i + 1 if i <= x.n && k == x.key(i)  return (x, i) // x is node , i is index number else if x. leaf  return nil else DISK-READ(x)  return B-Tree-Search(x, k) 2. 빈 트리 생성 (B-Tree-Create) B-Tree-Create (T) x = new Node() x.leaf = true x.n = 0 (X노드에 있는 값의 갯수 0) Disk-Write(x) T.Root = x 3. B트리에 삽입 (B-Tree-Insert) O(h)번의 디스크 접근과 , O(tlogN)의 CPU시...

public int [ ] mergeArrays ( int [ ] myArray , int [ ] alicesArray ) { // 조건 myArray 와 alicesArray둘다 각각 이미 정렬되어 있어야한다. // set up our mergedArray int [ ] mergedArray = new int [ myArray . length + alicesArray . length ] ; int currentIndexAlices = 0 ; int currentIndexMine = 0 ; int currentIndexMerged = 0 ; while ( currentIndexMerged < mergedArray . length ) { boolean isMyArrayExhausted = currentIndexMine >= myArray . length ; boolean isAlicesArrayExhausted = currentIndexAlices >= alicesArray . length ; // case: next comes from my array // my array must not be exhausted, and EITHER: // 1) alice's array IS exhausted, or // 2) the current element in my array is less // than the current element in alice's array if ( ! isMyArrayExhausted && ( isAlicesArrayExhausted || ( myArray [ currentIndexMine ] < alic...

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 값만 남는다.

첫번째, 재귀를 이용한 방법 (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); } }

<교차와 거리, 면적> *직선과 직선의 교차 x좌표에 대해 푼 뒤 방정식에 대입해 y좌표를 구하는 코드를 작성하거나 하면 수평선이나 수직선 같은 예외에 제대로 대응 할 수 없습니다. 직선의 교차를 작성할 수 있는 간단한 방법은 직선을 한 점과 방향벡터, 즉 a+p*b형태로 표현하는 것입니다. a+p*b와 c+q*d의 교점을 구하기 위해서는 a+p*b=c+q*d방정식을 풀면 된다. ax+p*bx=cx+q*dx ay+p*by=cy+q*dy 연립방정식을 p에 대해 정리하면 p=(c-a)Xd/bXd 이 p를 a+p*b에 대입해 원하는 점을 구할 수 있다. *선분과 선분의 교차 이 경우는 한 직선위에 두 선분의 판단에 유의해야 한다. 한 직선위에 두 선분이 있을 때, 이 선분들의 관계는 넷 중 하나이다. 1. 두 선분이 서로 겹치지 않음 2. 두 선분이 한 점에서 닿음 3. 두 선분이 서로 겹쳐짐 4. 한 선분이 다른 선분 안에 포함됨 lineIntersection()함수는 네 경우 모두 거짓을 반환하는데 (a)외의 경우에는 두 선분이 교차한다고 말할 수 있습니다. 문제의 특성상 이런 경우가 없다면 모르지만, 이 외의 겨우 이들을 꼭 고려해야한다. *선분과 선분의교차: 교차점이 필요 없을 때 교차점을 구할 필요 없을 때 두 선분의 교차 여부를 확인하기만 할 거라면 보다 단순한 방법을 사용할 수 있다. 바로 ccw()를 사용하는 것이다. 교차하는 두 선분 ab와 cd가 있다. a입장에서 ㅂ면 c와 d중 한쪽은 b를 기준으로 시계방향에, 다른한쪽은 시계반대 방향에 있다. 반대로 c입장에서보면 a와 b중 한쪽은 d의 시계방향에, 다른한쪽은 시계 반대방향에 있어야 합니다. 이 두 조건과 선분의 교차 여부는 동치임을 알 수 있다. 결국 ccw(a,b,c)와 ccw(a,b,d)중 하나는 양수, 하나는 음수가 되어야 하므로 이들의 곱은 항상 음수여야한다. 두 선분이 한 직선...

//atan2함수 참고: http://warmz.tistory.com/entry/CC-atan2double-y-double-x-함수 //acos(0.0)은 파이/2를 의미한다. 왜냐하면 코사인함수가 0을 만나는 x축좌표가 파이/2인 지점이다. const double PI=2.0*acos(0.0); --> 외적의 주된 사용처는 두 벡터의 방향성을 판단하는 것입니다. 두 벡터 a,b의 외적 axb가 양수라면 b가 a로부터 반시계방향으로 180도 이내에 있음을 알 수 있고, 음수라면 시계방향으로 180도 이내에 있음을 알 수 있습니다. -->ccw를 이용하면 좌표만으로 대답하기 힘든 여러 질문들에 쉽게 대답 할 수 있습니다. 세 점 a,b,c를 가리키는 세 벡터 a,b,c가 있다고 하자. 이떄, a,b,c를 순서대로 잇는 두 선분은 b에서 왼쪽으로 꺽을까요, 오른쪽으로 꺽을까요? 좌표들만으로는 계산하기 힘들지만 ccw(a,b,c)를 이용하면 쉽게 알 수 있다. 이 값이 양수라면 c가 b의 반시계 방향에 있는 것이니 좌회전이고, 아니면 우회전이나 직진이다. 물론 ccw()함수는 벡터의 극 각도를 계싼하는 polar()로 작성할수 있지만 외적을 사용하는 것이 훨씬 속도가 빠르고 수치적으로 안정적이다.

* 길이가 n인(n<=4000)인 문자열은 최대 (n+1)*n/2개의 부분 문자열을 가질 수 있다. 하지만 이들이 모두 다른 것은 아니다. 예를들어, "banana"는 "ana"를 두번 "n"을 두 번포함한다. 문자열이 주어질 때 이들의 서로 다른 부분 문자열의 수를 세는 문제를 풀어보자. 가장 간단한 방법은 각 부분 문자열을 직접 만들어보면서 이들을 집합 자료 구조 안에 넣는것이다. O(n^2)개의 부분 문자열이 있고, 이들을 set<>자료구조에 넣으려면 각 문자열마다 O(lgn)번의 비교를 해야 한다. 각 문자열을 비교하는 데 O(n)의 시간이 걸리므로 전체 시간 복잡도는 O(n^3lgn)이 된다. 해시를 이용해서 필요한 비교횟수를 O(1)로 줄이면 시간복잡도를 O(n^3)으로 줄일수도 있지만 부족하다. 접미사 배열로 이 문제를 풀 수 있다. 우선 주어진 문자열의 접미사배열을 생성한다. 이때 S의 모든 부분 문자열들은 이 접미사들의 접두사로 표현 할 수 있다. 이 의미는 만약 "banana"의 접미사 배열 중 a와 ana가 있다고 하면 ana는 접미사이며 이때 3개의 접두사가 존재한다. ana의 접두사로 a, an, ana를 만들 수 있다. 하지만 a하나로 부분 문자열을 만들 수 있으므로 ana와 a는 a라는 부분문자열이 중복된다 그러므로 이것을 뺴는 것이다. 길이 m인접미사에는 m개의 접두사가 있을 테니, 부분문자열이 중복이 없다면 각 접미사의 길이를 모두 더해서 부분 문자열의 수를 얻을 수 있다.

길이가 n(n<=40000)인 문자열을 끝과 끝이 연결된 원형으로 써보자. 이 문자열은 항상 시계방향으로 읽는데, 시작위치가 어디인지는 정해져 있지 않으므로 n가지 방법으로 읽을 수 있습니다. 이 중 사전순으로 가장 앞에오는 문자열은 무엇일까요? 이 문제를 푸는 가장 단연한 방법은 n개의 후보를 하나하나 만들어보고 이들 중 가장 사전순으로 앞에 오는 것을 찾는 것이다. 그러면 n-1번의 비교를 하게 되는데, 각 비교에는 O(n)의 시간이 걸리기 때문에 전체시간복잡도는 O(n^2)이 된다. 접미사배열을 통해 이 문제를 풀 수 있다. 문자열 S를 두 번 반복한 2S를 만드는것이다. 따라서 2S의 접미사 배열을 우선만든뒤, 길이가 n이상인 접미사중 가장 앞에 오는 것을 찾아내면 되는 것이다. 그러면 접미사배열을 만드는 시간인 O(nlg^2n)시간에 답을 계산 할 수 있다.

이 알고리즘은 O(n)시간안에 동작한다. 이것은 n개의 정수를 비교 정렬하는 것보다 빠르다. 이 알고리즘은 접미사들의 목록을 여러 번 정렬하는데, 매번 그 기준을 바꿉니다. 처음에는 접미사의 첫 한 글자만을 기준으로 정렬하고, 다음에는 접미사의 첫 두글자만을 기준으로 정렬하고, 그 다음에는 첫 네글자를 기준으로 정렬합니다. 이렇게 lgn번의 정렬을 하고 나면 우리가 원하는 접미사 배열을 얻게 되지요. 이렇게 정렬을 여러 번 하는데도 더 빠르게 동작하는 이유는 이전 정렬에서 얻은 정보를 이용해 두 문자열의 대소 비교를 O(1)할 수 있기 때문입니다. 첫 글자를 기준으로 접미사들을 정렬한 결과를 가지고 있다고 합시다. 각 접미사들을 첫 글자가 같은 것들끼리 그룹으로 묶고, 각 그룹마다 0부터 시작하는 번호를 매깁니다. "mississipi"의 접미사를 정렬해 나가는 과정. -->group[i]=S[i....]가 속한 그룹의 번호

*접미사 배열은 어떤 문자열 S의 모든 접미사를 사전순으로 정렬해 둔 것이다. 대개 접미사 배열은 각 접미사의 시작 위치를 담는 정수 배열로 구현된다. 예제) 접미사 배열을 이용한 검색 짚더미 H가 바늘 N을 포함한다면 항상 N은 H의 어떤 접미사의 접두사라는 점을 이용합니다. 예를들어, "alohomora"에서 "homo"를 찾는다고 합시다. "homo"는 S의 접미사인 "homora"의 접두사가 된다. 모든 부분 문자열에 대해 이 속성이 성립함을 쉽게 알 수 있다. 이 속성을 이용하면 H의 접미사 배열을 이진 탐색해서 각 문자열이 출현하는 위치를 찾을 수 있다. 접미사 배열의 길이는 항상 |H|이므로 이진탐색의 내부내는 O(lg|H|)번 수행된다. 각 문자열 비교에 O(|N|)시간이 걸리기 때문에 이 이진 탐색의 수행시간은 O(|N|lg|H|)이 된다. 물론 전처리 과정에서 짚더미의 접미사 배열을 생성해야 한다는 부담이 있지만, 같은 짚더미에서 여러 바늘을 찾아야 한다면 이 알고리즘은 아주유용하다. <접미사 배열 생성> sort의 시간복잡도는 O(nlogn)이다. 이거은 두 원소의 비교에 상수 시간이 걸릴 때 이야기이다. 두 문자열을 비교하는데는 최대 두 문자열의 길이에 비례하는 시간이 걸리므로, 한 번 비교에 O(n)시간이 걸린다고 할 수 있다. 전체 시간 복잡도는 O(n^2*log(n))이다. 이 시간 복잡도가 크다고 생각할 수 도 있지만,실제로는 모든 글자를 다 비교할 필요없이 첫 몇글자만 비교해도 어느 쪽이 큰지 판단 할 수 있는 경우가 많다.

*분리집합: 교집합을 갖지 않는 집합들 즉, 서로 공통된 원소를 갖지 않는 집합 **분리집합에는 교집합이 있을 수 없다. 오직 합집합(Union)만 있을 뿐이다. **분리집합의 표현** -->자식이 부모를 가르킴 루트노드는 집합 그 자체이고, 루트노드 자신을 포함한 트리내의 모든 노드들은 그 집합에 속한다. **집합의 구조체 typedef struct tagDisjointSet { struct tagDisjointSet* parent; void* data; }DisjointSet; 1) 합집합 void DS_Unionset(DisjointSet* Set1, DisjointSet* Set2) { Set2 = DS_FindSet(Set2); Set2->parent = Set1; } 2) 탐색 DisjointSet* DS_FindSet(DisjointSet* Set) { while (Set->parent != NULL) { Set = Set->parent; } return Set; }

https://algospot.com/judge/problem/read/PALINDROMIZE  int palindromize(const string& a, const string& b) { int n = a.size(); int m = b.size(); int begin = 0; int matched = 0; vector<int> pi = getPartialMatch(b); while (begin < n) { if (a[begin + matched] == b[matched]){ matched++; if (begin + matched == n) return matched; } else{ if (matched == 0) ++begin; else{ begin += matched- pi[matched - 1]; matched = pi[matched - 1]; } } } return 0; }

Manacher's algorithm은 문자열 내에서 팔린드롬(palindrome,회문)을 찾는것과 관련된 알고리즘이며, 시간 복잡도는  O ( n )  이다.( n 은 문자열의 길이) 이 알고리즘은 문자열  S 를 입력으로 받아 다음을 반환한다: 문자열  S 와 길이가 같은 정수 배열  A , 각  A 의 원소  A [ i ] 는  i 번째 문자열을 중심으로 하는 가장 긴 팔린드롬의 반지름의 길이.(즉,  S [ ( i − A [ i ] ) ⋯ ( i + A [ i ] ) ] 는 팔린드롬이며,  S [ ( i − A [ i ] − 1 ) ⋯ ( i + A [ i ] + 1 ) ] 은 팔린드롬이 아니다) 예를 들면, S='banana'라는 입력에 대해 A의 결과는: S [ i ] b a n a n a A [ i ] 0 0 1 2 1 0 알고리즘은 다음과 같다: i 는  0 부터  n − 1 ( n = | S | ) 까지 진행된다 j < i 인 모든  j 에 대해  R = max ( j + A [ j ] ) 이라하고, 또한 그러한  j 를  p 라 하자. 즉,  R = p + A [ p ] i ≤ R 인지 여부에 따라  A [ i ] 의  초기값 이 정해진다 i > R 이라면,  A [ i ] 의 초기값은  0 이다. i ≤ R 이라면,  i 는  p 를 중심으로 한 팔린드롬에 속한다는 이야기이다. 이때  p 를 중심으로  i 의 대칭점  i ′ 을 구한다. (즉,  i ′ = 2 ∗ p − i )  A [ i ] 의 초기값은  min ( R − i , A [ i ′ ] ) 으로 둔다. A [ i ] 의 초기값에서부터,  S [ i − A [ i ...