공부중의 블로그

{bat,tab,cat} 이 있으면 bat tab 이 palindrome이므로 존재한다.중복도 존재가능하다 우선 두개를 고르는 경우의 수가 N^2 개 이므로, palindrome인지 검사하는 비용 K를 고려하면 O(N^2K) 알고리즘이다. 그런데 성질을 조금 더 관찰해 보면 우선 두개를 합쳐서 palindrome이 되려면 1앞 == 2뒤 또는 1뒤 == 2앞이어야 한다. 그래야 합치니까.. aaaz aaab aaac aaad aaae 이 경우에 결국 모든 조합을 다 테스트해 보니 최악의 경우는 같다 답 : 트라이 프리프로세싱을 할 수 있다..!! of 8 votes1) Add the first word to the trie ( A B) 2) Take the second word (D E E D B A) ..

패턴은 1 ... N 의 값의 조합 배열으로 주어진다.배열은 서로 다른 N개의 값이다.패턴대로 배열을 정렬해 보자. O(N^2), O(1) 은 partition 해가면서 각 K번째 원소를 찾으면 가능하다. 근데 O(NlogN) O(1) 알고리즘이 있대.. 조합 배열을 정렬한 후에 패턴 배열에 원하는 값을 입히고 패턴 배열을 출력한다.. 추가 공간은 안 쓰는 듯? 더 좋은 O(N) O(1) 알고리즘이 있대.. public static int[] sort2(int[] Xs, int[] As) { for (int i = 0; i

행렬에는 1 ~ N^2 의 서로 다른 숫자로 구성되어 있다.. ex)1 5 92 3 84 6 7 >> ans : 6 7 8 9 풀이 : 각 점에 대해 연속된 숫자가 주위에 있는지 확인한다. 재귀적으로 따라간다. 길이가 최대보다 길면 기록한다.크게 재귀가 많이 일어나지는 않을 것으로 보이고 풀고 나면 DP 캐핑이 될 것 같기는 하다. 참신한 최선 풀이vector(N^2,false) 에다가 i이 i-1 과 붙어있는가? 의 값을 찾아서 채운다.최종적으로 이 불리안 어레이의 true가 가장 긴 부분이 정답이다. https://www.careercup.com/question?id=5147801809846272

본인이 테일 노드이거나, 테일 노드를 가리키거나, 테일 노드로 이어지는 노드를 가리키면 good 노드이다.모든 노드가 good이 되기 위한 최소 포인터 변경 횟수는? 아무래도 union_set 문제인 것 같다. 구체적인 구현으로는,본인의 종결점을 찾는다. 그것이 tail이 아니면 그것을 테일로 가리킨다.모든 노드에 대해 수행한다. 물론 visited를 써 가면서 수행하자. 그렇게 하면 O(N) 수행시간을 얻는다..!! DFS >> 횟수가 곧 최소 횟수이다!! vector visited; for(int i = 0 ; i < graph.size() ; i++){if(visited[i]!=false){// not containing node 1, need to move pointerif(!goDFS) coun..

비방향 그래프에서는 최대 V-1 개의 엣지가 가능하다. spanning tree이다. 그 이상 연결하면 반드시 사이클이 생긴다.방향 그래프에서는 Topological sort를 고려한다고 생각해 보면 맨 앞에서는 V-1개 , V-2 ... 1 의 총합은 V(V-1)/2 개이다.

각 점에서의 최대 트래픽을 구해보자. ex) 1 2 54 3 의 경우 1 142 133 124 115 4가 나와야 한다. 모든 점에서 nearby 점의 값들 중 최대값을 고려하는 듯 한데 이걸 preprocessing으로 풀어서 O(N) 을 만든 것으로 보인다. 그냥 나이브하게 구하면 O(N^2) 알골이 된다. // preprocess your input graph to the following structure // node -> hash set of neighbors // hash set to enable amortized O(1) deletions vector topology(n); vector metadata(n); // contains the population count vector curre..

min heap와 max heap을 유지해 가며 서로의 균형을 유지하면 top() 의 값들이 median이다. 계속적으로 들어오기 때문에 힙이 유리하지, 단 한번 찾는거면 partitioning 이 O(N) 으로 가장 빠르다.이 알고리즘은 O(NligK) 이다.

탐험가가 북서남동(반시계방향으로) 주어진 배열의 길이만큼씩 계속 움직인다. 전부 움직이는 동안 한번이라도 본인의 경로를 밟는 경로가 있을까? ex ) 2 1 1 2 >> cross(1)1 2 3 4 >> not cross(0) 이건 빼박 성질탐구 문제네..뭐 나이브하게는 경로를 기록해 두면서 밟는지 체크할 수 있겠지만, 메모리 사용이 과다하고 정답 요구사항은 싱글 패스, O(1) 메모리이므로 결국 성질탐구 뿐 대충 두가지 방법이 있는데, 안으로 줄어드는 경우와 밖으로 확산하는 경우가 있다. 두 경우에 대해 계속적으로 성립하는지 확인해 나가야 한다. // There are only two patterns when cross can happen, // one involves four moves another..

ex ) [2,1,4,5,1,4,2,2,4,1] >> ans : 5 소팅을 해서 찾는다 : O(NlogN), O(1)해싱을 해서 찾는다 : O(N) O(N)XOR을 해서 찾는다(?) 비트 문제 비트의 갯수를 세서 확인한다 : O(N), O(1) 그러나 external 메모리를 사용한다..비트의 갯수 중에서 3의 배수가 아닌 것들을 다 더하면 그게 답이다. 아 이거 맞네.. 근데 그 대신에 전부 센 후에 확인하지 말고 그때그때 3의 배수인지 확인하고 결과값에 더해주면메모리 사용 안해도 된다..!! int findtheone(vector & data){int m = 1;int ret = 0;for(int i = 0 ; i < 32 ; i++){long count = 0;for(int j = 0 ; j < d..

제곧내 해시 테이블에 "반복되지 않은" 원소들을 넣는다. 즉, 처음 만난 원소면 넣고, 리스트에 append하고 그 포인터를 맵에 저장한다.만약 반복되면 그 리스트 포인터를 지우고 포인터를 널로 만든다. 이미 널이면 이미 두번 이상 나왔다는 거니까 무시한다. string findfirstuniqueURL(vector & data){// make buffer elementslist tmp;unordered_map buffer;// go through datafor(int i = 0 ; i second!=NULL){tmp.erase(it->second);it->sec..