'Programming Problems/Preprocessing'에 해당되는 글 3건

Programming Problems/Preprocessing

증가하는 세개의 인덱스를 O(N)에 찾기

아예 랜덤하게 하나씩 뽑는것도 재밌을 듯. 그리고 나오는게 현재 인덱스들과 어떻게 구성되는지 비교하고 맞출 수 있으면 리턴.

아니면 앞에서부터 순회해야겠지.


현재 처음이야. 다음게 더 작아. 그럼 그걸 처음으로 잡아. 다음게 더 커. 그러면 그게 다음꺼야. 그리고 작은게 나오면 .. 이런식으로는 서로 떨어진 경우를 찾을 수 없다.


자명한 해는 소팅하는 방법.. O(NlogN)


랜덤하게 하나를 뽑는다. 

5 9 이렇게 두개 뽑았는데 중간의 더 작은값이면 버리고.. 아 근데 이것도 결국에는 그걸 못찾고 지나치겠다.


해싱이 답인거같다 O(N) 뽑으려면

해싱해가면서 수를 기록한다.

아니면 프리프로세싱..!!


어 프리프로세싱 되겠다.

오른쪽에 자신보다 큰게 있는가?

왼쪽에 자신보다 작은게 있는가?

 == 왼쪽의 max가 자신보다 큰가?

 == 오른쪽의 min이 자신보다 작은가?

3 2 5 4 1

x x o o x

o o o o x


oo인 점이 있으니 true. 아마 두번째 프로세싱 만들면서 바로 발견가능할듯 .. !!!


아 근데 이렇게도 생각가능한데. 저런게 단 한개도 없다는 뜻은, 무조건 단조감소한다는 뜻이잖아.

..!! 띠용 !!


아 근데 "인덱스"를 찾아야 해서, 결국에는 위 방법이 될듯. 안된다는거는 확인해도 되면 그 점을 찾기는 쉽지 않아서 .. !!


vector<int> findthree(vector<int> & data){

// error cases

if(data.size()<3) return vector<int>();

// make preprocess array

vector<int> maxbuffer(data.size(),-1);

int max = data[0];

for(int i = 1; i < data.size() ; i++){

if(max<data[i]) max = data[i];

maxbuffer[i] = max;

}

// go through to track min and return

int min = data[data.size()-1];

for(int i = data.size()-2; i>= 0 ; i--){

if(min>data[i]) min = data[i];

// check if terminates

if(maxbuffer[i]<data[i]&&data[i]<min){

vector<int> ret = {maxbuffer[i], data[i], min};

return ret;

}

}

// not exist

return vector<int> ();

}


time complexity : O(N)

space complexity : O(N)


--



Programming Problems/Preprocessing

행렬에서 가장 큰 십자가 모양 찾기 Q

0과 1로 구성된 N*N 행렬이 있다.


여기에서 가장 큰 십자가 모양을 찾아보자.


   1

   1

  111

   1

   1


(대칭적이고 너비가 1인 십자가)


풀이 :


preprocessing을 하면 빠르다.

각 점에 대해 동서남북으로 이어진 길이를 가진 행렬 4개를 만든다.

만드는 방법은, 현위치가 0이면 전부 0

현위치가 1이면 동서남북의 인접한 값 + 1

각 점은 한번씩만 채워질꺼라 O(N^2)


그리고 그 값을 기반으로 한 점에서의 가장 큰 십자가는 4개의 값 중에서의 4*(최솟값-1) 이다.


https://www.careercup.com/question?id=5678853664014336

Programming Problems/Preprocessing

list of words 가 주어졌을 때, 두 단어를 조합해서 palindrome 만들기 Q

{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 votes

1) Add the first word to the trie ( A B)
2) Take the second word (D E E D B A) and reverse it (A B D E E D) 
3) See how many letters in the reversed word you can match in the trie (the first 2) 
4) Take the rest of the string (D E E D) see if it is a palindrome if it is you are done return true 
5) add the second word to the trie (D E E D B A)
6) go back to step 2 with the next word 
7) when out of words return false

그리고 반대의 경우 성립하지 않을 수도 있으므로 



1
of 1 vote

@DRADM, this will not work if first word to be inserted in trie is DEEDBA. And second word comes as AB so if you reverse it (BA) and try to compare in trie. You will end up returning false. 

In this scenario, apart from reversing word (BA) and checking trie, we have to take original word (AB) and try to match with the reverse of words which are inserted in tried (DEEDBA) so that will match here.

But it will be expensive to lookup word(AB) in reverse side in trie (DEEDBA).

So to simplify, we need to maintain two tries, when we insert DEEDBA in one trie, we will add ABDEED in second trie. And then for second word first we try to lookup reverse (BA) in first trie and original (AB) in second trie

Here it will be there in second trie and we can apply rest of the logic

뒤집은 트리도 보관한다!!


그니깐 두 트리에서 최대한 따라간 후에 남는 부분(어느 쪽이든) 을 테스트 해 본다.


시간복잡도가 O(NK) 라는데 그 이유는 더 생각해봐야 할듯..