두찡의 일상

아래 블로그를 보고 이해한 내용을 정리합니다. blog.naver.com/kks227/221028710658 접미사 배열(Suffix Array) (수정: 2018-03-03) 시험기간 버프를 맞아서 돌아왔습니다.영영 포스팅할 수 없을 줄 알았던 SA도, 시험기간 앞에선 무력화되... blog.naver.com // [출처] 접미사 배열(Suffix Array) (수정: 2018-03-03)|작성자 라이 #include #include #include using namespace std; const int MAX = 1

기본 풀이가 deque 인 것 같은데 priority queue 두개로 푼게 기-묘 해서 올려봅니다 1. i 로 순회를 한다고 할 때 0 N >> L; priority_queue pq; priority_queue reserved; for ( int i = 0; i > arr[i]; pq.push( -arr[i] ); if ( pq.size() > L ) { reserved.push( -arr[i - L] ); } while ( !reserved.empty() ) { if ( pq.top() == reserved.top() ) { pq.pop(); reserved.pop(); } else { break; } } cout

백준 문제를 go 언어로 풀었는데, 시간초과가 나서 찾아봤다 // 기존코드 for r := 1; r

백준 문제를 풀면서 알게된 Trie 자료구조에 대한 정리 많은 문자열중에서 같은 문자열을 찾을 때 최대길이가 m이라면 n번 시행할때 O(mn)으로 찾을 수 있고, 트라이를 만들 때도 O(mn)으로 만들 수 있게 한다. #include #include #include #include using namespace std; struct Trie { char c; bool end; Trie* next[10]; Trie() { end = false; memset(next, 0, sizeof(next)); } ~Trie() { for (int i = 0; i < 10; i++) { if (next[i]) delete next[i]; } } void insert(string s) { if (s.size() == 0)..

외판원 길찾기 문제에서 비트마스크 개념이 나오는데 그 개념을 몰라서 차라리 비트마스크를 공부해보자 싶었다. 왜 길을 찾는데 비트마스크란 개념을 쓰냐면, 어떤 곳에 방문했는지 탐색할때마다 배열을 만드는건 비효율적이니까 int값만 넘기는데 자릿수마다 어떤 마을에 방문했는지 쓸 수 있는것 이다. (1번째 bit가 1이라면 1번 마을을 방문) 대신 넘기는 자료형의 자릿수보다 크게는 안된다. (32bit int 에서는 32까지 표현 가능) - n번째 비트를 1로 만들기 arr |= (1