두찡의 일상

백준 문제를 풀면서 알게된 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)..

서버 공부를 하면서 클래스에 boost::noncopyable 을 상속받은 이유가 궁금해서 찾아보고 정리하게 되었습니다. https://stackoverflow.com/questions/3518853/what-are-use-cases-for-boosternoncopyable https://www.boost.org/doc/libs/1_44_0/libs/utility/utility.htm#Class_noncopyable Boost 공식 문서에서 나온 설명은 Some objects, particularly those which hold complex resources like files or network connections, have no sensible copy semantics. Sometimes th..

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

일상 개발 등등 포스팅!!