본문 바로가기

전체 글

 (195)
[ 자료구조 ] 탐색 - 04 - 3 . 레드 블랙 트리 <구현> [RBT.h] #ifndef RBT #define RBT #include #include typedef int ElementType; enum NodeColor { Red, Black }; typedef struct tagRBTNode { //부모 struct tagRBTNode* Parent; //왼쪽 자식 struct tagRBTNode* Left; //오른쪽 자식 struct tagRBTNode* Right; //색 NodeColor Color; //데이터 ElementType Data; }RBTNode; //트리의 삭제 void RBT_DestroyTree(RBTNode* Tree); //노드의 생성 RBTNode* RBT_CreateNode(ElementType NewData); //노드의 소멸..
[ 자료구조 ] 탐색 - 04 - 2 . 레드 블랙 트리 <삭제> [레드 블랙 트리의 노드 삭제] [삭제] 레드블랙트리의 삭제연산은 기본적으로 이진 탐색 트리의 삭제연산과 같다 . 다만 , 삭제후 레드 블랙 트리의 무너진 규칙을 수습하는 과정이 더해질 뿐이다 . [ 무너진 규칙의 복구 ] 무너진 규칙의 복구를 위해 레드 블랙 트리의 규칙을 다시 떠올리자면 모든 노드는 검정색 아니면 빨간색이다 . 루트 노드는 검은색이다 . 잎 노드는 검은색이다 . 빨간 노드의 자식들은 모두 검은색이다 . 하지만 검은 노드의 자식이 빨간색일 필요는 없다 . 루트 노드부터 모든 잎 노드 사이에 있는 검은색 노드의 수는 모두 동일하다 . 노드를 하나 삭제했을때 다음의 경우로 나뉜다 . 01 . 삭제한 노드가 빨간색일때 =>아무것도 처리할 필요가 없다 . 위의 규칙에 위반사항이 없다 02 . ..
[ 자료구조 ] 탐색 - 04 - 1 . 레드 블랙 트리 <회전 , 삽입> [ 레드 블랙 트리 ] [ 레드 블랙 트리 ] 이진 탐색 트리는 균형있게 자라지 못하는 경우가 대부분이다 . 이런 성장은 검색 효율을 심각하게 저하시킨다 . 레드 블랙 트리는 이를 해결하기 위한 이진 탐색 트리이다 . 해당 트리를 이해하는데 해당 사이트가 많은 도움이 되었다 . 참고하면서 공부하면 좋을것이다 . 레드 블랙 트리 시물레이터 이진 탐색 트리와 다른 점은 노드를 빨강 , 혹은 검정으로 표시한다는 점이다 . 이를 구현한 구조체는 다음과 같다 . typedef struct tagRBTNode { struct tagRBTNode* Parent; struct tagRBTNode* Left; struct tagRBTNode* Right; enum { Red , Black } Color; ElementT..
[ 시네머신 ] 02 . 가상 카메라 [ 가상 카메라 ] [ 정의 ] 단일 Unity카메라 사용 가상 카메라는 Unity카메라를 이동 및 회전하고 해당 설정을 제어한다 . (카메라의 애니메이터) Unity 카메라의 제어권을 가상 카메라로 이전시 해당 설정들을 Unity카메라에 적용한다 . 가상카메라는 다음의 작업을 수행한다 . 씬에 Unity 카메라를 배치합니다. Unity 카메라가 무언가를 향하게 합니다. Unity 카메라에 절차적 노이즈를 추가합니다. 노이즈는 핸드헬드 효과 또는 차량 흔들림과 같은 것을 시뮬레이션합니다. [ Status ] 가상 카메라는 다음중 하나의 상태를 가지고 있다 . Live : 시네머신 브레인이 있는 Unity Camera를 능동적으로 제어한다 . 시네머신 브레인이 원래 가상카메라에서 다음 가상카메라로 Blen..
[ 자료구조 ] 탐색 - 03 . 이진 탐색 트리 [ 이진 탐색 트리 ] [ 이진 탐색 트리 ] 이진 탐색 트리 ( Binary Search Tree)는 이진 탐색을 위한 트리이자 , 탐색을 위한 이진트리이다 . 즉 , 이진 탐색 트리는 이진탐색을 위한 이진트리이다 . [필요 이유] 이진 탐색은 데이터 집합이 배열인 경우에만 사용이 가능하기 때문이다 . 이진 탐색에는 다음이 조건이 필요하다 데이터 집합의 처음과 끝을 알아야 한다 . 순식간에 데이터 집합의 중앙 요소를 계산 할 수 있어야 한다 . 계산된 중앙요소에 즉시 접근이 가능해야 한다 . ex) 링크드 리스트는 다음의 작업들이 불가하다 . 헤드와 테일 사이 중앙 요소를 알 수 없기 때문이다 . =>따라서 , 이진탐색은 사전에 정의된 크기의 데이터 집합에 대해서만 사용이 가능하고 , 동적으로 크기가 ..
[ 자료구조 ] 탐색 - 02 . 이진탐색 [이진 탐색] [이진 탐색] 이진 탐색은 정렬된 데이터 집합에서 사용할 수 있는 '고속'탐색 알고리즘이다 . 이진 탐색이라는 이름은 알고리즘의 핵심이 탐색범위를 1/2 씩 줄여나가는 방식에 있기 때문에 붙여졌다 . [과정] 데이터 집합의 중앙에 있는 요소를 고른다 . 중앙요소의 값과 찾고자 하는 목표값을 비교한다 목표값과 중앙요소의 값을 비교해 목표값이 중앙요소가 작다면 왼편,크다면 오른편에 대한 이진검색을 수행한다 찾고자 하는 값을 찾을때까지 위의 과정을 반복한다 . [성능] 이진 탐색은 참색을 시도할때마다 탐색의 범위가 1/2씩 줄어들어 결국은 1이 된다 . 1의 경우 (마지막 데이터 범위)를 식으로 나타내자면 1 = n * (1/2)x제곱이며 이를 단순화 한다면 x = log2n으로 나타낼수 있다 ..
[ 자료구조 ] 탐색 - 01 . 순차탐색 [순차 탐색] [순차 탐색] 순차 탐색은 데이터 집합의 처음부터 끝까지 차례대로 모든 요소를 비교해서 데이터를 찾는 탐색 알고리즘이다 . 한쪽 방향으로만 탐색을 수행한다고 해서 선형탐색이라 불리기도 한다 . 효율적인 방법은 아니지만 , 정렬되어 있지 않은 데이터 집합 사이에서 원하는 데이터를 찾을 수 있는 유일한 방법이며, 구현이 간단해서 극적으로 높은 성능이 필요 없거나 데이터 집합의 크기가 작은 곳에서 사용된다 . [예시] 링크드 리스트를 위한 순차 탐색 구현의 예이다. Node* SLL_SequentialSearch(Node* Head , int Target ) { Node* Current = Head; Node* Match = NULL; while(Current !=NULL) { if(Curren..
[C#]sealed 한정자 [sealed] [sealed] 가상 / 추상 인터페이스 등의 카워드로 클래스 구조를 잡다 보면 너무 복잡해질 수 있다 . 이를 위한 한정자가 Sealed이다 . 상속이 여러번 일어나며 계층이 깊어지게 되면 나중에 코드 구현하는 사람입장에서는 어디까지 재정의를 해야 하는지 알기가 쉽지 않고 불필요한 기능 역시 구현 할 수 있으므로 구조를 잡는 입장에서 확실하게 sealed를 사용하는 습관을 가지면 좋을 것 같다 클래스 / 속성 / 메서드에 사용이 가능하다 클래스 class A {} sealed class B : A {} sealed class C : B {}//재정의가 불가하다 메서드 class X { protected virtual void F() { Console.WriteLine("X.F"); } ..

티스토리툴바