티스토리
관련 서비스
  • Symbols스토리 홈바로가기바로가기
  • 브런치브런치스토리바로가기바로가기
  • 카카오스토리카카오스토리바로가기바로가기

흔들리며 피는 꽃
검색하기
블로그 홈

블로그 홈

흔들리며 피는 꽃

eun-jeong.tistory.com/m
신고

Front-end Developer @ NHN https://github.com/iamkkwak

구독자
6
방명록 방문하기
구독하기

주요 글 목록

  • [자료구조] 트라이 (Trie) C++ 구현 트라이 (Trie) 우리가 여러 개의 문자열을 가지고 있을 때, 어떤 문자열이 그 문자열 중 하나인지 알아내는 방법을 생각해보자. 단순하게 일일히 비교하는 방법이 있겠지만, 이러한 방법은 매우 비효율적이다. 최대 길이가 M인 문자열 N개의 집합에서 마찬가지로 최대 길이가 M인 문자열이 그 문자열의 집합에 포함되는지를 일일히 확인하면 최악의 경우 O(NM)의 비교 횟수가 필요하다. 이때, 문자열을 효율적으로 저장하고 탐색할 수 있는 자료구조가 트라이(Trie)다. Prefix tree, Digital search tree, Retrieval tree라고 부르기도 한다. 프레드킨이 Retrieval tree에서 "Trie"라는 이름을 붙였다. 트라이는 특정 문자열을 찾는 작업을 O(N)만에 해결할 수 있다... 공감수 2 댓글수 1 2020. 9. 18.
  • [자료구조] 세그먼트 트리 (Segment Tree) C++ 구현 Segment Tree 배열 A[1], ..., A[N]이 있을 때, 아래 문제를 생각해보자. [문제 1] 순서쌍 (i, j)에 대하여 A[i], ... ,A[j] 중 최솟값을 찾는 경우를 생각해보자. A[i]부터 A[j]까지 순회하면서 찾는 것이 가장 단순한 방법일 것이다. 이 경우 시간 복잡도는 O(N)이 된다. 그러나 이러한 연산이 Q개 주어지고 N과 Q의 범위가 1부터 10만이라면, 시간 복잡도가 O(NQ)이므로 오랜 시간이 걸릴 것이다. [문제 2] 구간 [l, r] (l ≤ r)이 주어진다. (1) A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력한 뒤, (2) i번째 수를 v로 바꾼다. 이 과정을 M번 반복한다. (1)번 과정은 O(N), (2)번 과정은 O(1).. 공감수 5 댓글수 2 2020. 8. 3.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.