본문 바로가기 메뉴 바로가기

Minusi

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

Minusi

검색하기 폼
  • Minusi Library (52)
    • 개발 (40)
      • C++ (5)
      • C# (1)
      • Unreal Engine 4 (8)
      • Algorithm (4)
      • Data Structure (2)
      • DirectX (3)
      • Miscellaneous (13)
      • WinAPI (0)
      • Pattern (0)
      • TroubleShooting (4)
    • 이론 (6)
      • Computer (3)
      • Math (3)
      • OOP (0)
    • 기타 (4)
      • 레퍼런스 (4)
      • 비공개 (0)
    • 아카이브 (0)
      • 컴퓨터 (0)
  • 방명록

개발/Data Structure (2)

카테고리

  • Minusi Library (52)
    • 개발 (40)
      • C++ (5)
      • C# (1)
      • Unreal Engine 4 (8)
      • Algorithm (4)
      • Data Structure (2)
      • DirectX (3)
      • Miscellaneous (13)
      • WinAPI (0)
      • Pattern (0)
      • TroubleShooting (4)
    • 이론 (6)
      • Computer (3)
      • Math (3)
      • OOP (0)
    • 기타 (4)
      • 레퍼런스 (4)
      • 비공개 (0)
    • 아카이브 (0)
      • 컴퓨터 (0)
이전 1 다음
세그먼트 트리(Segment Tree, Index Tree)

앞서서 펜윅 트리에 대해서 소개한 적이 있습니다[링크]. 위 링크에서 세그먼트 트리와의 비교점 역시 쓰여있으므로, 차이점을 알고 싶으신 분들은 위 링크를 방문해 주시면 되겠습니다. 따라서 이 포스팅에서는 순수하게 세그먼트 트리에 대해서 설명하도록 하겠습니다. 세그먼트 트리 역시 부분합을 빠르게 찾을 수 있는 자료구조입니다. 위키피디아에서는 다음과 같이 정의하고 있습니다 : 통계 트리(statistic tree)라도고 하는 세그먼트 트리(Segment tree) 는 세그먼트나 간격에 대한 정보를 저장하는 트리 자료구조입니다. 주어진 지점에서 포함된 세그먼트들을 쿼리할 수 있습니다. 이론적으로 정적 구조체이며, 이 말은 한번 만들어지면 수정될 수 없음을 의미합니다. 유사한 데이터 구조로 간격 트리(inter..

개발/Data Structure 2020. 4. 25. 12:53
펜윅 트리(Fenwick Tree, Binary Indexed Tree)

펜윅 트리는 효과적으로 요소를 업데이트하고 수 배열의 구간합을 계산할 수 있는 자료구조입니다. 위키피디아에서는 다음과 같이 정의하고 있습니다 : 펜윅 트리 또는 바이너리 인덱스드 트리 는 효과적으로 요소를 업데이트하고 수 배열의 구간합을 계산할 수 있는 자료구조입니다. 1989년 Boris Ryabko에 의해 처음 제안되었으며 1992년 추가로 수정되었습니다. 펜윅 트리는 Peter Fenwick에서 이름이 유래하였습니다. 일반 배열과 비교했을 때 구간 합에 대해 배열은 선형 시간이 필요하며, 이는 배열 요소를 업데이트하는 데에도 똑같이 적용됩니다. 펜윅 트리는 두 가지 작업 모두에 대해 O(log n) 시간에 수행할 수 있습니다. 이러한 자료구조 필요한 이유는 다음 상황들에 대해 효율적으로 처리할 수 ..

개발/Data Structure 2019. 11. 5. 01:58
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
  • Jejuorange
TAG
  • 퍼포스 스트림
  • 행렬
  • C# 익명함수
  • C++ Compile error
  • Perforce Streams
  • c++ 핫 리로드
  • 구간합
  • C7568
  • Perforce Stream
  • game hot reload
  • P4 Stream
  • GoogleTest
  • Auto
  • DXGI
  • MSVC C1083
  • delaying 2 processes from spawning due to memory pressure
  • Unreal Engine 5
  • Visual Studio C1083
  • C++
  • 알고리즘
  • P4 Streams
  • C# 람다식
  • 퍼포스 개요
  • visual studio hot reload
  • UE4
  • C# lambda expression
  • 언리얼 엔진
  • 언리얼 엔진 5
  • visual studio 핫 리로드
  • c++ hot reload
more
«   2025/06   »
일 월 화 수 목 금 토
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30
글 보관함

Blog is powered by Tistory / Designed by Tistory

티스토리툴바