자료구조 (2) 썸네일형 리스트형 [자료구조] - 트라이(Trie) 목차 1. 들어가며 2. 트라이(Trie)란 3. 예제 적용 들어가며 문자열 관련 문제에 단골로 등장하는 트라이(Trie)라는 자료구조에 대해 정리해보겠다. 트라이는 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조이다. 문자열이 여러개 주어지고 하나의 문자열이 다른 문자열에 속한다는 것을 확인하라거나, 여러개의 문자열을 사전에 저장한 후 검색같은 기능을 구현하라는 문제들이 모두 이 트라이 자료구조를 사용하는 문제라고 할 수 있다. 트라이(Trie)란? 더보기 트라이는 트리의 일종으로 문자열의 검색에 특화된 자료구조이다. 예를들어 'apple', 'apply', 'car'의 3개의 단어를 트라이에 저장한다고 가정해보자. 트라이는 root 노드아래에 단어들을 저장하는 방식이다. 'appl.. [자료구조] - 그래프(Graph) 경로탐색 알고리즘을 정리하기에 앞서 그래프 자료구조에 대해 정리해보려고 한다. 그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미하며, vertex는 정점, edge는 정점과 정점을 연결하는 간선이다. - 위키백과 네트워크상에서 연결된 호스트의 관계를 나타낸다거나 게임이나 메신저에서 유저간에 친구관계를 나타낼때 위와 같은 그림을 자주 볼 수 있을 것이다. 그래프는 이처럼 vertex(정점)간의 연결 관계를 나타내기에 적합한 자료구조이다. 그래프의 종류 위의 그림처럼 일반적인 그래프에서 매 간선마다 가중치를 다르게 설정하는 경우 '가중치 그래프(Weighted Graph)'라고 부른다. 지하철 노선도와 같이 매 역마다 거리가 다른 경우 가중치 그래프처럼 모든 역(vertex)과 역 사이의 거리.. 이전 1 다음
