programmer life guidance 101

www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 4750 1793 1208 37.785% 문제 생태학에서 나무의 분포도를 측정하는 것은 중요하다. 그러므로 당신은 미국 전역의 나무들이 주어졌을 때, 각 종이 전체에서 몇 %를 차지하는지 구하는 프로그램을 만들어야 한다. 입력 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 3..

> 트라이(Trie) 여튼 또 문자열인데, 이번엔 매칭 문제가 아니라 여러 문자열을 저장하는 자료구조를 소개해드릴 겁니다. 바로 트라이(Trie)인데, 트리와 굉장히 스펠링이 비슷하면서 트리와도 유사합니다. 아니, 아예 트리의 한 종류라고 해도 될 겁니다. 래딕스 트리(radix tree)나 접두사 트리(prefix tree)라고도 합니다. 예를 들어 {"he", "she", "her", "him", "show"}라는 문자열 집합이 있다면, 그들을 담고 있는 트라이는 그림과 같습니다. 빨간색 겹선 노드가 여기서 끝나는 문자열이 있다는 뜻으로, output이 있다고 하거나 final state, accepting node라고도 하는 등... 그런 의미가 있습니다. 왜 트라이의 별칭 중 접두사 트리라는 것이..

> 트라이(Trie) 문자열에서의 검색을 빠르게 해주는 자료구조 래딕스 트리(radix tree) 나 접두사 트리(prefix tree)라고도 한다. 우리는 정수형 자료형에 대해서 이진검색트리를 이용하면 O(logN)의 시간만에 원하는 데이터를 검색할 수 있다. 하지만 문자열에서 이진검색트리를 사용한다면 문자열의 최대길이가 M이라면 O(MlogN)의 시간 복잡도를 가지게 될 것이다. 우리는 문자열 검색을 개선하기 위해 트라이를 이용하여 O(M)의 시간만에 원하는 문자열을 검색할 수 있다. 트라이라는 명칭은 Retrieval에서 유래한다. 트라이가 retrieve(탐색)하는데 유용한 걸 생각하면 납득ㅇ ㅣ디ㅗㄴ다. 자 그러면 트라이는 어떻게 문자열의 검색을 O(M)만에 처리할까? 아래 그림은 문자열 집합 ..