지난 글에서는 이진 탐색트리의 개념과 Search, Add, Delete 의 구현에 대해 정리하였다. 이번 글에서는 BST의 핵심인 '탐색' 과 탐색 시간에 대해 좀 더 깊게 정리해보자. BST의 탐색 시간 모든 BST의 기능 중에서 제일 중요한 것은 BST 의 이름에도 들어있는 '탐색' 기능이다. 탐색 시간이 얼마나 걸리는지 ( 탐색을 위해 비교를 몇 번이나 하는지) 는 어떻게 측정할까? 답은 정확하게 BST 의 노드 중 찾으려는 노드의 depth + 1 (level + 1) 이다. 더보기 [트리에서 Depth, Height, Level ] Depth = 루트 노드의 depth를 0 으로 정의할 때, 자식 노드의 depth는 부모 노드의 depth + 1 이다. Level = Depth 와 같다. de..
이진 탐색 트리 (Binary Search Tree, BST) 는 노드가 정렬되어 있어 탐색을 수행할 수 있는 이진 트리를 말한다. 각 노드는 여러개의 필드로 이루어진 데이터를 가지고 있다고 가정한다. 데이터 중에서 탐색을 하기 위해 사용되는 데이터를 '키' 라고 한다. node v 의 키를 key(v) 라고 정의하면, BST 는 모든 노드 u 에 대해서 아래를 만족하는 이진트리이다. (1) 만약 v 가 u 의 왼쪽 서브트리에 있다면 key(v) key(u) 이다. 등호는 좌, 우 둘 중 하나 어디든 들어가도 되지만, 왼쪽에 들어간 것으로 생각하자. 이 정의를 통해 이진 탐색 트리는 매우 효율적으로 원하는 key 를 탐색할 수 있다. 이제 이렇게 생긴 BST가 있다고 가정해보자. 이 트리에서 3이라는 값..
지난 글에서는 트리와 이진트리, 그리고 이진 트리를 만들 수 있는 가짓수인 카탈란 수에 대해서 정리하였다. 이번 글에서는 이진 트리를 순회하는 3가지 방법을 정리해보고자 한다. 사람에 관점에서는 이진트리의 전체적인 모습이 보이기 때문에 특정 노드를 찾을 때 전체 이진트리에서 특정 노드를 바로 딱 보면 쉽게 알 수 있다. (글로벌 뷰) 하지만 컴퓨터 입장에서 이진트리를 탐색할 때는, 연결리스트 때와 비슷하게, 현재 자신이 보고 있는 노드 T와, 그 T의 ITEM(T), 왼쪽 노드 LEFT(T) , 오른쪽 노드 RIGHT(T) 만 본다. (로컬뷰) 이런 로컬 뷰가 재귀적으로 반복되기 때문에, 이진트리를 탐색할 때는 재귀를 이용하게 되는데, 이진 트리를 재귀적으로 탐색하는 방법에는 3가지가 있다. Preord..
지난 글에서는 메모리와 레지스터 사이 데이터를 주고받는 방법을 정리해보았다. 간단히 정리하면, ld [메모리주소], 레지스터 형태로 메모리에서 값을 불러온다. 메모리주소는 불러올 데이터 크기의 배수여야한다. 만약 ldd 로 8byte 를 불러온다면 레지스터는 짝수번째 레지스터여야한다. 메모리주소는 레지스터와 레지스터(상수) 합으로 표현되며, -레지스터만 없으면 된다. st 레지스터, [메모리주소] 형태로 레지스터 값을 메모리에 저장한다. 마찬가지로 메모리 주소는 저장할 데이터 크기의 배수여야 하고 만약 std 로 8byte 를 저장한다면 레지스터는 짝수번째 레지스터여야 한다. 메모리주소는 레지스터와 레지스터(상수) 합으로 표현되며, -레지스터만 없으면 된다. 이번 글에서는 메모리의 영역 중 static ..
지난 글에서는 연결리스트가 사용하는 메모리 공간을 어떻게 관리하는지 그 구현을 C언어로 직접 해보았다. 이번 글에서는 트리와 이진트리의 개념을 정리해보고자 한다. 트리 트리는 아래와 같이 정의된다. a tree is a finite set T of nodes such that 1) T has one special node called root 2) the remaining nodes are partitioned into m disjoint sets T1, T2, ... Tm, and each of these sets is turn to a tree. wee call them subtrees of T 트리는 '루트' 라고 불리는 특별한 하나의 노드를 가지고 있고, 나머지 노드들은 m 개의 서브트리를 이루는..
메모리 개요 메모리는 프로그램의 명령어와, 그 명령어가 사용할 데이터가 들어있는 공간이다. (폰 노이만 구조에서는 프로그램의 명령어도 데이터이다.) 저장 단위는 byte 단위이며, 레지스터와 달리 4byte로 고정되지 않고 1, 2, 4, 8 byte 등으로 유동적인 사이즈로 저장할 수 있다. 하지만 레지스터가 한번에 4byte 씩 파악하기 때문에, 명령어의 사이즈는 4byte 로 고정되어있다. 메모리 접근 메모리에 접근하여 데이터를 읽고 쓰는 명령어는 기본적으로 아래와 같은 형태를 띈다. Load, 메모리의 데이터를 불러와(loading) 레지스터에서 읽는 것 ld [메모리주소], 레지스터주소 메모리 -> 레지스터 순서로 읽으면 되니 이해가 간단하다. 메모리주소는 R + A 형태로 표현되고, [ ] 는..
이제 지금까지 배운 내용을 응용해보자 어떤 세 점이 주어질 때, 그 세 점을 삼각형으로 하는 평면을 결정할 수 있다. 임의 지점에서부터 주어진 방향으로 광선을 쏘았을 때, 그 광선이 삼각형에 맞았는지 어떻게 알 수 있을까? 이는 아래와 같은 방법으로 계산할 수 있다. 1. 평면식을 구한다. (세 점으로부터 둘레 벡터 구하고, 둘레벡터의 외적과 세 점중 하나로 평면식 결정) 2. 광선의 직선식을 구한다. 3. 광선의 직선식과 평면식의 교점을 구한다. 4. 교점이 삼각형 내부에 있는지 체크한다. (각 삼각형 선분마다, 그 선분을 포함하고 삼각형평면에 수직인 평면식을 짜고, 그 평면식 위의 임의 점 A 에서 평면식의 법선벡터를 내적했을 때 양수임이 모든 선분에서 확인되면 내부에 있다고 볼 수 있다.) 내적의 ..
지난 글에서는 연결리스트를 이용해 스택과 큐를 구현하였다. 이번 글에서는 연결리스트를 이용하는 과정에서 new(), free() 기능을 사용했는데, 이 기능을 직접 구현해본다. 사실 직접 구현이라고 해서 나도 처음엔 메모리를 직접 다루는 거창한 걸 기대했는데, 그런건 아니다. 그냥 배열을 이용해서 전체 memory pool 을 세팅해두고, 그 세팅된 pool 내 메모리를 주고 받고 하는 방식이다. 메모리 풀은 연결리스트 노드의 데이터 형태로 배열에 세팅해두고, 이를 스택처럼 활용하여 메모리를 주고 받는다. 메모리 풀은 이런 구조로 존재한다. 만약 new 함수로 메모리 공간을 요청하면 top이 가리키는 노드를 제공해준다. 제공을 마친 모습이다. 제공된 메모리는 연결리스트에서 자유롭게 Item 부분에도 값을..
지난 글에서는 분기 최적화에 대해 정리하였다. 분기 최적화를 하는 방법에는 from before, from after, annulled branch 3가지가 있었다. from before 은 분기 명령어 이전에 실행되는 명령어를 가져오는 것으로, 보통 mov 명령어를 이용한 레지스터 값 세팅을 가져올 수 있다. from after 은 분기 명령어 이후에 실행되는 명령어를 가져오는 것으로, 보통 분기 이후 실행되는 명령어 중, 분기 여부에 상관없이 반드시 실행되는 명령어를 당겨올 수 있었다. annulled branch 는 분기를 할 때는 delay slot 명령어를 실행하고, 분기를 하지 않을 때는 delay slot 명령어를 실행하지 않는 분기 명령어로서, 반드시 분기 후 첫 명령어를 delay slo..
지난 글에서는 직선과 점, 직선과 직선, 점과 평면 사이 최단 거리를 구하는 방법을 정리하였다. 직선과 점에서는 직선의 법선벡터를 방향벡터로 하고, 직선밖의 점을 지나는 새로운 직선식을 세운다음, 기존 직선과 교점을 구해 거리를 구하거나, 점의 위치를 원점으로 평행이동시키고, 이동된 직선의 방정식의 법선벡터를 정규화하여 최단 거리를 구할 수도 있었다. 직선과 직선의 경우, 두 직선의 외적을 이용해 한 직선을 지나는 평면식을 세우고, 그 평면식과 다른 직선 위 임의점 사이 최단 거리를 구하였다. 점과 평면사이 최단거리의 경우, 점의 위치를 원점으로 옮기고, 이동된 평면의 방정식의 법선벡터를 정규화하여 최단거리를 구하였다. 이번 글에서는 특정 평면으로 입사된 벡터의 반사벡터를 구하는 방법을 정리하고자 한다...
