09.08 - TIL

오늘의 코드카타

등산코스 정하기

• 여러 출발점에서 시작해서 여러 도착점으로 도착하는 다익스트라 응용
• LV3 - 30% (복습 필요)
  -> 문제 풀이
  
  

오늘의 공부

팀 프로젝트 개발 현황

AI 설계

• 기본 원칙
  • AI는 서버에서 구동
  • Behavior Tree를 통해 행동 로직 구현
  • AIController는 서버에서만 관리
• 행동 로직 : Enum::ActionState를 통해 관리
  1. Idle -> 랜덤 이동
  2. 일정 주기로 액션을 실행 : 모이 쪼기, 알 낳기
  3. 공격 받을 시에 역으로 캐릭터에게 스턴 발생
• GAS 적용
  1. 액션 관리 (Ability)
     • 모이 쪼기
     • 알 낳기
  2. 상태/스탯 관리 (AttributeSet)
     • 체력, 이동속도, 시야 범위 관리
  3. 이펙트 관리 (GameplayEffect)
     • 맞으면 플레이어에게 스턴 및 알 게이지 감소

정리 노트

• 언리얼의 세이브 시스템
  
  

오늘의 CS

std::unordered_map에 대하여

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

해시 충돌 해결법

1. Seperate Chaining (체이닝)

• 충돌이 발생하면 버킷에 연결 리스트(or 동적 배열)로 저장
• 탐색 시 해당 버킷을 순회하면서 키를 찾음
• C++ std::unordered_map의 대부분은 이 방식을 사용

2. Open Addressing (개방 주소법)

• 충돌이 발생하면, 테이블 내에서 빈 공간을 찾아 다른 위치에 저장
• 대표 기법들
  • Linear Probing (선형 탐사)
    • 충돌 발생 시 순서대로 빈 슬롯을 찾음
    • 단순하고 캐시 친화적이지만, 클러스터링 문제 발생
  • Quadratic Probing (이차 탐사)
    • 충돌 발생 시 h(k)+1^2, h(k)+2^2, h(k)+3^2... 방식으로 탐색
    • 클러스터링 문제를 완화할 수 있음
    • 단, 해시 테이블 크기를 소수 또는 2의 제곱으로 잘 설정해야 함
  • Double Hashing (이중 해싱)
    • 충돌 발생 시 두번째 해시 함수를 사용
    • 탐색 경로가 다양해져서 클러스터링 문제가 완화됨

3. Cuckoo Hashing (뻐꾸기 해싱)

• 각 키를 둘 이상의 해시 함수 위치 중 하나에 저장
• 충돌 발생 시 기존 키를 쫓아내고 다른 해시 함수 위치로 이동
• 탐색은 2개의 위치만 확인하면 되기 때문에 O(1)
• 삽입 시 쫓아내는 과정이 반복되다 무한 루프 발생 가능 -> 해시 테이블 재구성이 필요
  
  

클러스터링 문제

• 데이터가 한쪽에 몰리는 현상
  • 선형 조사 방식에서 특히 두드러짐
    • 예를 들어, 해시 충돌이 일어나면 한 칸씩 옆으로 이동하며 저장
    • 계속 같은 구간에 데이터가 몰려 클러스터 생성
    • 이 구간이 길어질 수록 새로운 원소가 삽입될 때 더 멀리 가야 하고, 탐색 성능도 떨어짐
• Robin Hood Hashing
  • 개방 주소법에서 클러스터링을 완화하는 기법
  • 삽입 시 충돌이 발생하면 탐사 거리가 더 긴 원소가 슬롯을 차지하도록 교환
  • 특정 원소가 매우 먼 거리에 저장되는 불균형을 막고, 탐색 시 평균 성능을 더 안정화함
  • 최악의 경우를 줄여주고, 평균 탐색 시간을 개선