[비선형자료구조] 트라이
트라이(Trie)
문자열을 저장하고 빠르게 탐색하기 윈한 트리 형태의 자료구조
- 정렬된 트리 구조
- 문자열 저장을 위한 메모리가 필요하나 탐색이 빠름 – 길이가 N인 문자열 탐색의 시간 복잡도: O(N)
문자열 구성
탐욕 알고리즘은 빠르지만 최적의 답을 보장하지 않는다.
- 탐욕적 선택 특성(Greedy Choice Property) – 앞의 선택이 이후의 선택에 영향을 주지 않음
- 최적 부분 구조(Optimal substructure) – 문제에 대한 최적의 답이 부분문제에 대해서도 역시 최적의 답
예제 - 활동 시간 선택
N개의 활동과 각 활동의 시작/종료 시간이 주어졌을 때
한 사람이 최대한 많이 할 수 있는 활동의 수 구하기
| Activity | A | B | C | D | E | Activity | C | A | B | D | E | Activity | C | B | E | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 시작 | 1 | 4 | 2 | 4 | 6 | ➤ | 시작 | 2 | 1 | 4 | 4 | 6 | ➤ | 시작 | 2 | 4 | 6 |
| 종료 | 5 | 5 | 3 | 7 | 10 | 종료 | 3 | 5 | 5 | 7 | 10 | 종료 | 3 | 5 | 10 |
구현 코드
관련 문제
문제1. 백준[2839] 설탕 배달
작성 코드
문제2. 백준[1931] 회의실 배정
작성 코드
