</note>

간만에 문제풀이를 위해 들어갔는데.. 바보가 된 느낌이다 전에는 이렇게 안풀었겠지만 오랜만에 c++을 만지면서 STL사용이 너무 어색해져서 답을 알면서 구현을 못하는 말도 안되는 상황까지 온듯하다... 반성하자.. 너무나도 간단한 주제,, 두 string 리스트를 비교해서 중복되지 않는 하나의 string을 뽑아내는 문제였다. 처음에 생각났던 풀이는 HashMap이라는 주제에 맞춰서 Map을 구성해서 비교한 풀이였고 나중에 생각났던 풀이는 좀더 짧고 간단한 풀이였는데 뒤에있는풀이가 좀더 재밌는 풀이인것 같다. 우선 HashMap이라는 주제에 고정시킨 풀이부터 설명해보자면 1. 입력된 string값들을 hashing해서 hashValue, string을 한쌍으로 해서 Map에 집어넣는것을 두 string ..

Fenwik Tree(Binary Index Tree)는 구간합을 구할때 많이 사용되는 자료구조이다. 처음 배울 때 분명히 이해 했는데 매번 다시 볼때마다 새로워서 계속 코드를 보면서 공부해야할것 같다. Fenwik Tree를 구현하려면 어떤 수 N을 이진수로 만들었을 때 마지막 1의 위치를 구할 수 있어야 한다 L[i]배열의 값을 직접적으로 사용하지는 않지만 Fenwik Tree를 이해하기 위해서는 이해하고 있어야 할 듯 하다. 따라서 L[i]값을 수식으로 구하면 (i & -i)가 된다. (L[i] = (i & - i)) 그리고 배열 A[1] ~ A[N]에 N개의 수가 들어있다고 할 때 Tree[i]에는 A[i - L[i + 1]] ~ A[i]까지의 합이 저장되게 하면 된다. Fenwik Tree를 U..

STL을 배제하고 문제를 풀어보면서 가장 힘들었던게 vector를 못쓴다는 점이었다. 그래서 이번기회에 vector를 구현해봤다. 평소에 안쓰던 문법을 많이 사용해본것같다. - 2021.04.03 수정 (카라츠바 알고리즘 구현을 위해 생성자 추가) #include #include template class _vector{ private: T* _elements; int _size, _cap; void init(int cap) { _size = 0; _cap = cap; _elements = (T*) malloc(sizeof(T) * _cap); } public: _vector(){ init(32); } _vector(int cap, int init_value) { init(cap); for (int i ..