09.04 - TIL

오늘의 코드카타

스타 수열

• 빈도 수 정렬, 부분 수열
• LV3 - 31% (복습 필요)
  -> 문제 풀이

오늘의 공부

학습한 강의

• 챕터 10
  • 10-4 : Property Replication
• 10번 과제
  • 모듈과 플러그인 제작

정리 노트

• 언리얼 모듈 & 플러그인 만들기

오늘의 CS

std::map에 대하여

• 개념
  • key-value 쌍을 저장하는 STL 컨테이너
• 특징
  • 키는 중복 불가능, 내부적으로 정렬된 상태로 유지
  • 탐색, 삽입, 삭제 모두 O(logN)의 시간복잡도
• 내부 구현
  • Red-Black Tree 자료구조를 통해서 구현이 되어있음
    

Red-Black Tree

• 특징
  • 균형 이진 탐색 트리(BST)의 일종
  • 탐색, 삽입, 삭제 연산에서 항상 O(logN)을 보장
  • 트리 높이가 최대 2*log(n)
  • AVL 보다 느슨하게 균형을 유지하는 트리
  • AVL 보다 탐색은 조금 더 느릴 수 있으나, 삽입, 삭제 시 회전이 적어 효율적
• 규칙
  1. 각 노드는 빨강 또는 검정이다.
  2. 루트 노드는 항상 검정이다.
  3. 모든 리프는 검정이다.
  4. 빨강 노드의 자식은 모두 검정이다. (빨강은 연속될 수 없음)
  5. 루프에서 리프까지의 모든 경로에 있는 검정 노드의 개수는 동일하다. (Black-height)
     -> 따라서 트리 높이는 최대 2*log(n) 이내로 유지됨
• 삽입 과정
  1. 일반 BST 규칙대로 삽입
  2. 새 노드는 빨강으로 삽입
  3. 규칙 위반이 생기면 -> 회전 + 색상 변경으로 수정
• 삭제 과정
  1. 일반 BST 규칙대로 삽입
  2. 삭제한 노드가 Black이면 Black-height 불균형 발생
  3. 형제 노드 색상과 조카 색상을 확인 -> 회전 + 색상 변경으로 균형 복구

AVL (Adelson-Velsky and Landis Tree)

• 특징
  • 최초의 균형 이진 탐색 트리
  • 각 노드는 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이(균형 인수) = -1, 0, 1을 만족
  • 트리 높이가 log(n)으로 거의 완벽하게 균형을 이룸
• Red black tree와 비교
  • 엄격하게 균형을 잡아서 높이를 최소화함
  • 탐색 성능은 높이가 더 낮기 때문에 더 빠름
  • 삽입/삭제 성능은 회전이 많기 때문에 비용이 큼
  • 탐색에서 우수한 성능을 보이기 때문에 데이터베이스 인덱스, 검색 엔진에서 사용

std::unordered_map에 대하여

• 개념
  • key-value 쌍을 저장하는 STL 컨테이너
• 특징
  • 내부적으로 해시 테이블 기반
  • 원소들이 정렬되지 않음
  • 탐색, 삽입, 삭제 평균 O(1)의 시간복잡도
• 내부 동작
  • 내부적으로 버킷(bucket) 배열을 가지고 있음
  • 키에 대해 해시 함수를 적용 -> 특정 버킷으로 매핑
  • 같은 버킷에 여러 원소가 들어가면 -> 체이닝(연결 리스트/벡터) 방식으로 관리
    -> 충돌이 발생하면 같은 버킷에 여러 개가 들어가므로, 탐색 시 O(k) 시간이 걸림
    

언리얼의 TMap

• 개념
  • 언리얼 엔진에서 제공하는 해시 기반 컨테이너
• 내부 동작
  • 내부적으로는 Hash Table + Chaining(연결 리스트 or 버킷 관리)
  • std::unordered_map과 유사
• 특징
  • Key는 정렬되지 않음
  • 탐색, 삽입, 삭제 : 평균 O(1), 최악의 경우 O(n)
  • 메모리 구조 : 해시 버킷 배열 + 요소 배열