Donghae Blog

Donghae Blog

  • Category (122)
    • Computer Science (28)
      • Computational thinking (7)
      • Algorithem (10)
      • Data structure (6)
      • Operating system (5)
    • Programming (25)
      • C (20)
      • Python (3)
      • SQL (2)
    • Data Engineering (4)
      • Linux (1)
      • Docker (1)
      • Apache Airflow (3)
      • Apache Spark (5)
      • BigQuery (5)
      • Datahub (1)
    • Problem Solving (26)
      • Baekjoon Online Judge (13)
      • Programmers (10)
      • CodeUp (2)
    • Conference (2)
    • Code States AI (4)
    • LIKELION 9th (12)
    • Writing (5)
  • 홈
  • 태그
  • 방명록
  • 글쓰기
RSS 피드
로그인
로그아웃 글쓰기 관리

Donghae Blog

컨텐츠 검색

태그

bigquery 코딩테스트 멋쟁이사자처럼 c언어 장고 백준 스택 프로그래머스 Django 배열 자료구조 네이버 cs50 문자열 알고리즘 부스트코스 글또 포인터 파이썬 시간복잡도

최근글

댓글

공지사항

아카이브

트라이(1)

  • 자료 구조 | 트라이

    학습 목표 트라이의 원리와 구조를 설명할 수 있다. 트라이 트라이(trie)는 기본적으로 트리 형태의 자료 구조다. 트라이는 각 노드가 배열로 이루어져 있다는게 특징이다. 예시를 보자. 영어 알파벳으로 이루어진 문자열 값을 저장한다고 생각해보자. 노드는 a부터 z까지의 값을 가지는 배열이 될 것이다. 배열의 각 요소, 즉 알파벳은 다음 층의 노드(a-z배열)를 가리킨다. 트라이의 시간 복잡도 앞선 예시와 같은 트라이에서 값을 검색하는데 걸리는 시간은 문자열의 길이에 의해 정해진다. 일반적인 영어 이름의 길이를 n이라고 했을 때, 검색 시간은 O(n)이지만, 대부분의 이름은 그리 크지 않은 상수이기 때문에 O(1)이나 마찬가지다. 생각해보기 트라이가 해시 테이블에 비해 가지는 장점과 단점은 무엇일까. 트라..

    2021.03.01
이전
1
다음
티스토리
© 2018 TISTORY. All rights reserved.

티스토리툴바