혼종 꼬지마루

TRIE란 TREE를 응용한 문자열 알고리즘이다. Wiki에서는 hash map을 대신할 수 있다고 되어 있는데 실제로 그렇다. 단순하게 이진트리가 아니라, 문자열을 순차적으로 순회하며 tree를 구성해주게 되는데, trie를 사용하는 장점 중 하나는 저장과 동시에 정렬이 된다는 점이다. 삼성전자 상시 역량테스트를 준비하면서 hash를 공부하는 사람들이 많은데, 사실 데이터양이 많아질수록 직접 구현한 hash일수록 index충돌이 많이 일어나서 생각보다 AutoK를 하는 경우가 생길것이다. 물론 hash에 충돌이 안나게하는 여러가지 기법이 있지만.... key값이 그리 길지 않다면 trie를 hash처럼 사용하는 것을 선호하는 편이다. 위의 그림(Wiki 참조)과 같이 문자를 하나의 key값으로 삼으며 ..

Heap이란 입력으로 들어온 데이터를 2진 트리의 형태로 나타내어 순서대로 정렬? 해주는 것이라고 생각하면 쉬울 것이다. 자식 노드에 있는 값은 항상 부모노드의 값보다 작아야(혹은 정렬기준에 따라 커야) 함으로 입력과 동시에 정렬이 된다. Heap을 사용하는 가장 대표적으로 사용하는 우선순위 queue, heap sort가 있다. 그 중에서도 heap sort를 구현해 보았으며, 정렬 기준을 함수로 선언하여 던져주는, 즉, algorithm 헤더에 있는 sort와 최대한 비슷하게 구현해보았다. 정의된 시간 복잡도는 heap sort는 O(nlogn)이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464..

삼성전자 수시 역량테스트 B형을 준비하기 위해서 필요한 reference code를 직접 구현하면서 정리를 해보는 중 어짜피 queue나 stack은 딱히 구현할 연습은 없어보임....원래 stl을 안썻으니.... 하지만 map이나 sort는 해본적이 없고, 우선순위 queue같은 것도 미리 구현을 해보면 좋을 것 같다는 생각이 들었다. 그 중에 이 글은 map을 대체로 사용할 수 있는 hash를 구현해 보았다. 여기서 가장 중요하게 기억해야 할 것은 5381이라는 골든 넘버! hash를 구현하다 보면 다른 key값이지만, 이미 할당된 index를 참조하는 경우가 있다. 이런 index 충돌이 일어나게 되는 것이 최소화시키는 것이 5381이라고 한다. 자세한 것은 아래의 코드를 보면서 참조하면 될 것 같..