[자료구조] 트라이 트라이는 기본적으로 문자열의 구성 character를 노드로 만든 만든 트리입니다. 전처리 과정이 매우 헤비한 대신, 탐색이 매우 빠릅니다. 문자열에서 이어지는 문자의 시퀀스에 따라 새로운 노드를 만들어 다음 문자를 넣어주고 또 그 노드에 다음 철자의 노드를 만들어 주는 식으로 진행합니다. 이렇게 해주면 접두사가 겹치는 문자열들에 대해 빠른 탐색이 가능하겠죠? 포인트는 문자열 끝의 구분인데, 노드에서 bool이나 다른 여러 장치를 이용해서 현재 노드가 어떤 문자열의 끝 문자임을 알리는 기능을 만들어야합니다. 이를 통해 어떤 문자열이 실제로 존재하는지 파악 할 수 있습니다. 트라이는 정말 정말 빠른 시간 내에 탐색을 진행 할 수 있습니다. 실제로 거의 탐색을 안 하는거나 마찬가지입니다...
[백준 130505] 두 수 XOR [백준 130505] 두 수 XOR 두 수 XOR은 최대 1,000,000,000의 숫자들 10만개가 주어지고 그 중 XOR이 가장 큰 두 쌍의 XOR연산값을 2초 안에 구하는 문제이다. 당연히 수가 10만개가 되기 때문에 직접 XOR 연산을 해준다면 (10만^2/1억) 초 정도의 시간이 소요되기 때문에 시간초과가 된다. 해당 연산에 트라이를 적용하면 더 빠른 연산이 가능해진다. 기본적으로 이진수 연산을 위해 모든 수를 이진수 문자열로 만들어 준 후, 그 수들로 트라이를 만들어 준다. 이후 모든 수들로 한번 더 탐색을 진행해준다. 이진수 XOR연산은 두 수가 같으면 0, 다르면 1을 결과로 갖는다. 넣어줬던 수들을 또 트라이에서 탐색하되, 지금 탐색중인 문자 (0 or..
Markdown 문법 본 글도 markdown으로 쓰여 있습니다 블로그에서는 많이 깨집니다. https://github.com/binary-ho/TIL-public/blob/main/Markdown/README.md 를 이용해주세요! [추천 익스텐션] Markdown all in one을 통해 미리 랜더링된 결과를 볼 수 있고(ctrl + shift + v), 일반 문서 편집기와 같은 명령어들을 이용할 수 있습니다. ex) ctrl + B로 bold체 변경 (2.8.2.6) Markdown Preview Enhance를 추가로 설치하면, Markdown all in one를 통해 만든 미리 보기의 배경을 하얀 색으로 바뀌 더 편하게 볼 수 있습니다. 1. Markdown 문법을 공부하는 이유 2. Mar..
1. About Map map은 제가 그리 자주 쓰는 자료구조는 아니지만, IT기업 코딩테스트 대비 과정에서 생각보다 Set과 Map의 이용이 잦았고, 정리가 필요함을 느껴 이렇게 정리하게 되었습니다. (굳이 굳이 굳이 직접 해시 함수를 만들어서 테이블을 이용하곤 했습니다.) map은 자료를 유일한 key와 하나의 value 쌍으로 저장하는 자료구조입니다. 정확히는 각 노드가 key, value 쌍으로 이루어진 'Tree'구조를 띄고 있습니다. key와 value의 타입은 서로 다를 수 있으며, 일반 map은 key 값을 오름차순 정렬하여 저장합니다. 이는 간단한 테스트를 통해 확인 할 수 있습니다. 위와 같이 내부적으로 key를 정렬하는 것을 확인할 수 있습니다. 그래서 수행 속도가 중요시 되는 테스트..
