본문 바로가기

Programming Problems/Preprocessing

(3)
증가하는 세개의 인덱스를 O(N)에 찾기 아예 랜덤하게 하나씩 뽑는것도 재밌을 듯. 그리고 나오는게 현재 인덱스들과 어떻게 구성되는지 비교하고 맞출 수 있으면 리턴.아니면 앞에서부터 순회해야겠지.현재 처음이야. 다음게 더 작아. 그럼 그걸 처음으로 잡아. 다음게 더 커. 그러면 그게 다음꺼야. 그리고 작은게 나오면 .. 이런식으로는 서로 떨어진 경우를 찾을 수 없다.자명한 해는 소팅하는 방법.. O(NlogN)랜덤하게 하나를 뽑는다. 5 9 이렇게 두개 뽑았는데 중간의 더 작은값이면 버리고.. 아 근데 이것도 결국에는 그걸 못찾고 지나치겠다.해싱이 답인거같다 O(N) 뽑으려면해싱해가면서 수를 기록한다.아니면 프리프로세싱..!!어 프리프로세싱 되겠다.오른쪽에 자신보다 큰게 있는가?왼쪽에 자신보다 작은게 있는가? == 왼쪽의 max가 자신보다 큰가..
행렬에서 가장 큰 십자가 모양 찾기 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
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 votes1) Add the first word to the trie ( A B)2) Take the second word (D E E D B A) and re..