블로그 이미지
이태원에서 사는 다섯식구의 무직 가장. 흰둥에미

카테고리

분류 전체보기 (184)
Itaewon (2)
ryu's?? (1)
20121210이전 (20)
20130827이전 (147)
soo'study (13)
Total34,674
Today8
Yesterday13

'이진 트리'에 해당되는 글 2건

  1. 2013.01.31 검색 알고리즘 (1)
  2. 2013.01.24 2. 실외 지형( 4. Quad tree )

검색이란

 - 특정한 구조로 되어 있는 자료의 집합에서 주어진 키에 해당하는 자료를 찾아내는 것.


검색의 종류

 - 선형 검색 : 처음부터 차례대로 검색하며, 자료가 정렬되지 않아도 가능

                   속도가 가장 느리지만 알고리즘 작성이 쉬움.

   제어 검색 : 자료가 정렬되어 있음을 전제로 하며, 피보나치 검색(피보나치 수열을 이용), 보간 검색, 이진 검색

   블록 검색 : 인덱스를 이용해서 검색하며 자료가 어느 정도 정렬되어 있음.

   이진 트리 검색 : 가변 크기 검색, 삽입, 삭제, 수정이 쉬움.

   해싱 검색 : 해싱 함수를 이용한 검색으로 직접 파일을 구성.


검색 알고리즘이란

 - 자료를 찾는 것만이 아닌, 자료가 추가되고, 삭제될 때 이 자료들이 특정한 구조(효율적인 검색을 위한)를 유지되게 하는 것도 포함.

   자료를 다루는 동작 - 초기화, 검색, 삽입, 삭제 등.

   예 : 선형 검색 - 일반적인 배열을 사용하여 자료를 조직화

         이진 검색 - 정렬된 배열을 사용하고, 동적인 자료에 유용, 트리 구조로 자료를 조직화.


선형 검색

 - 자료의 처음부터 하나씩 검색하는 방법으로, 프로그래밍이 간단하고, 쉽기에 작은 양의 데이터에 대해 빈번히 사용됨.


피보나치 검색

 - 피보나치 수열에 따라 비교후의 결과에 다음 비교 대상을 선정하여 검색하는 방식.

   장.단점

   - 덧셈과 뺌셈으로 다음 검색할 위치를 정함(이진 검색은 검색위치 산출 시 나눗셈으로 연산)

     이진 검색보다 평균 비교 횟수가 적음.

     부가적인 overhead때문에 이진 검색보다 대체로 비효율적임.


보간 검색

- 우선 리스트는 정렬되어 있음.

  검색하는 자료가 있음직한 위치를 비교대상으로 선정하고 검색.


이진 검색

 - 이미 정렬된 배열에 대해 매우 빠르고 간단한 알고리즘.

   검색은 간단하지만, 자료를 삽입, 삭제시 정렬된 구조를 유지해줘야하는 번거로움이 있음.


이진 트리 검색

 - 이진 트리를 이용하여 검색하는 방법

   이진 트리가 균형 잡힌 경우 시간 복잡도는 logN(이진 검색과 같음)

   이진 검색은 삽입, 삭제시 원소들을 밀고, 당기는 번거로움이 있지만, 이진 트리는 포인터 조작으로 원하는 구조를 유지할수 있음

   단, 특정 노드N의 왼쪽 자식은 N보다 키값이 작고, 오른쪽 자식은 N보다 커야함(검색을 위한 구조화)

   예 ) 제로섬 게임의 유리한 수를 얻기 위해, 각 수들에 대해 트리를 구성하고, 효율적인 수를 검색함.


신고

'20130827이전 > 알고리즘' 카테고리의 다른 글

병렬 알고리즘  (0) 2013.01.31
암호 알고리즘  (1) 2013.01.31
압축 알고리즘  (0) 2013.01.31
수치 해석 알고리즘  (1) 2013.01.31
검색 알고리즘  (1) 2013.01.31
정렬 알고리즘  (0) 2013.01.31
Posted by 흰둥에미

트리의 종류

- 이진트리

  - 하나의 공간을 반으로 나누고, 나눠진 공간의 한쪽을 선택하여 다시 반으로 나눔

    나누는 기준은 생성된 공간의 polygon

    실내 지형(던전) 같은 종류의 지형 관리 및 충돌 처리(각 node에서의 Object가 속한 부분을 검사하는 방법)에서 많이 쓰임.

- 쿼드트리

  - 2차원의 공간에서 두 축으로 네 개의 공간으로 나눔.

    카메라의 frustum외에 위치한 오브젝트를 컬링.

- 옥트리

  - 하나의 공간(박스라고 가정)을 세 축으로 분할하고 분할된 점은 박스의 중심.

    새로운 공간(박스)을 다시 재귀 호출로 분할하여, 사용자가 원하는 만큼 또는 화면에 있는 Object를 모두 공간 분할할때까지 반복.

    3D공간에 Object가 있을 경우, frustum에 속해 있는 공간의 Object만 처리해주는 컬링에 사용


  - LOD와 컬링 시에 지형 데이터, 실시간 연산일 경우 계산이 효율적이게 됨.


이러한 트리 구조로 지형을 관리함은 혼자서는 큰 의미가 없으나, LOD나 Culling과 같이 사용되면, 정리된 자료구조에 의해,

빠른 search가 가능하기 때문에 최적화에 적합.


신고
Posted by 흰둥에미

최근에 달린 댓글

최근에 받은 트랙백

글 보관함