Game Tech Blog

Binary Search Tree? 레드 블랙 트리를 배우기 전 알아야할 자료구조. 이진 검색 트리는 저장과 검색에 평균 O$LogN$ , 최악 O$N$ 의 비교적 불완전한 구조를 가진다. 이 불 완전성을 해결하기 위해 고안된 것이 균형잡힌 이진트리 이다. 균형잡힌 이진트리로 대표적인 것은 레드 블랙 트리, AVL 트리이다. 여기서는 레드 블랙 트리를 다룬다. 이 Tree 에서 중위 순회$왼쪽자식 -> 부모 -> 오른쪽자식$를 할 때, 다음과 같은 Key를 얻는다. 결과 : 20 -> 30 -> 40 -> 50 -> 60 -> 80 이를 다시 트리에 넣게 되면, 다음과 같은 최악의 구조가 나온다. 이 Depth 를 Balance 있게 잡아줄 트리라고 생각하면 된다. Red Black Tree ? 기본은 ..

Hasing ? - 임의의 길이의 값을 해시함수를 사용하여 고정된 크기의 값으로 변환하는 작업 Hash Table ? - 해시 함수를 사용하여 변환 값을 Index 로 삼아 Key, Value를 저장하는 자료구조 - 기본연산으로는 탐색, 삽입, 삭제 등이 존재 - 저장된 데이터를 찾을 때, hash_function을 한번만 수행하면 array내 저장된 Index위치를 찾아낼 수 있어서 탐색이 O$1$ 이다. - 순차 검색에 비해 비교도 안될정도로 빠르다. 해쉬 함수의 알고리즘 - Division Method $나눗셈 법$ 입력 값을 테이블의 크기로 나누고 그 나머지를 테이블의 인덱스로 이용하는 알고리즘 // 인덱스 $해시 값$ = 입력 값 % 테이블의 크기 - Digit Folding $자릿수 접기$ 숫..

Dictionary ? - Dictionary 란 Key, Value 로 나누어진 값으로 이루어져 있다. Python 에서 사용된다고 한다. - Vector, List , Array 에서는 숫자 인덱스로 Value 를 참조했으나, Dictionary 에서는 문자로 값을 참조할 수 있다고 한다. Dictionary Vs Map - 공통 1. Key , Value 를 가지고 있으며, Key로 찾아서 Value를 참조하는 자료구조 2. 중복 Key 값이 존재할 때 값을 넣지 않는다. $중복 Key 불허함, Key의 Unique한 성질을 보장해야함$ - 차이 - Map 1. Key값을 기준으로 요소들이 추가,삽입,삭제될 때, 재정렬을 수행한다. 2. 내부가 트리로 구성된다 $레드 블랙 트리로 구성$ 3. 트리로..