우선 그 전 포스팅과 관련하여 이번 포스팅에서 알아야할 내용은 명령어의 오퍼랜드 필드에 메모리나 레지스터의 주소를 담는 경우가 많고, 그래서 오퍼랜드 필드를 주소 필드라고 부른다는 점을 알아야 한다. 그렇다면 왜 오퍼랜드 필드에 메모리나 레지스터의 주소를 담는 걸까? 그 이유는 명령어의 길이 때문이다. 즉, 오퍼랜드 필드 안에 메모리 주소가 담긴다면 표현할 수 있는 데이터의 크기가 하나의 메모리 주소에 저장할 수 있는 공간만큼 커지기 때문이다. 예를 들어, 만약에 한 주소에 16비트를 저장할 수 있는 메모리가 있다고 가정하면, 이 메모리 안에 데이터를 저장하고, 오퍼랜드 필드 안에 해당 메모리 주소를 명시한다면 표현할 수 있는 정보의 가짓수는 2^16개로 확 늘어날 것이다. 또한 오퍼랜드 필드에 메모리 ..
기계어와 어셈블리어를 이루는 하나하나는 명령어이다. 이번 포스팅과 다음 포스팅에서 이 하나의 명령어를 자세히 들여다보면서 연산 코드, 오퍼랜드, 주소 지정 방식이라는 개념에 대해서 정리해보려 한다. 명령어는 '무엇을 대상으로, 어떤 작동을 수행하라.'라는 구조로 되어있다. 즉, 연산 코드와 오퍼랜드로 구성되어 있는데, '명령어가 수행할 연산'을 연산 코드라고 하고, '연산에 사용할 데이터' 또는 '연산에 사용할 데이터가 저장된 위치'를 오퍼랜드라고 한다. 또한 연산 코드를 연산자라고 하기도 하고, 오퍼랜드를 피연산자라고 하기도 한다. 그럼 우선 오퍼랜드부터 자세히 알아보자. 오퍼랜드 오퍼랜드가 담기는 영역을 오퍼랜드 필드라고 한다. 그래서 오퍼랜드 필드에는 숫자와 문자 등을 나타내는 데이터 또는 메모리나..
이진 탐색 트리의 한 종류로 스스로 균형을 잡는 트리이다. 이때 balance factor를 통해 균형을 유지하는게 핵심이다. 그럼 balance factor에 대해서 조금 더 자세히 알아보자. 노드의 balance factor란 임의의 노드 x에 대해서 그 노드의 왼쪽 서브트리의 높이와 그 노드의 오른쪽 서브트리의 높이의 차이를 구했을때, 그 높이 차이를 그 노드의 balance factor라고 한다. 여기서 AVL 트리의 특징은 트리의 모든 노드들의 balance factor가 -1, 0 ,1 값을 가진다는 특징이 있다. 또한 AVL 트리는 트리에 삽입 혹은 삭제후에 balance factor가 -1, 0, 1이 아닌 노드가 생기면 균형을 맞추는 작업을 수행한다. 즉, AVL 트리에서 삽입/삭제를 위..
이번 장에서는 균형 이진 탐색 트리로 많이 사용되는 RB tree를 C언어로 구현해본다. 여기서 구현하는 ADT(Abstract Data Type)은 ordered set, multiset이다. 구현해야 하는 기능들은 CSLR 13장의 수도 코드를 구현하면 되는데, 구현해야 할 기능들은 다음과 같다. new_tree() : RB tree 구조체를 생성한다. 이때, 여러 개의 tree를 생성할 수 있어야하며, 각각 다른 내용들을 저장할 수 있어야한다. Tree를 생성할 때는 여러 개의 tree를 생성할 수 있어야하며, 각각 다른 내용들을 저장할 수 있어야 한다. 이를 tree 구조체의 동적 할당이라고 한다. 또한 RB tree의 leaf 노드는 nil 노드라는 것으로 표시해야 하는데, nil 노드는 일종의..
이진 탐색 트리란 정렬된 이진트리로써 다음과 같은 속성이 있다. 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가 있는 노드만 포함된다. 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가 있는 노드만 포함된다. 그리고 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리여야 한다. 또한 중복된 키를 허용하지 않는다. 이러한 이진 탐색 트리의 특성때문에 효율적인 검색이 가능하다. 검색 이진 탐색 트리에서 검색은 특정 요소의 위치를 찾는 것이다. 과정은 먼저 루트에서 시작하여, 검색 값을 루트와 비교하여 루트보다 작으면 왼쪽에 대해 재귀하고 크면 오른쪽으로 재귀한다. 일치하는 값을 찾을때까지 절차를 반복한다. 검색 값이 없으면 null을 반환한다. 이를 구현하면 다음과 같다. struct node* sear..
Red-Black Tree는 이진 탐색 트리의 한 종류로서, 스스로 균형을 잡는 트리를 의미한다. 즉, 이진 탐색 트리의 worst case의 단점을 개선하였으며, 모든 노드는 red 혹은 black이라는 특징을 가지고 있다. 또한 RB tree는 nil 노드라는 독특한 특징을 가지고있다. 이는 존재하지 않음을 의미하는 노드로, 자녀가 없을 때 자녀를 nil 노드로 표기한다. 그럼에도 불구하고 값이 있는 노드와 동등하게 취급을 해주기 때문에, RB tree에서 leaf 노드는 nil 노드인 것이다. RB Tree의 특성에는 다음과 같은 규칙이 있다. 모든 노드는 RED or BLACK이다. 루트 노드는 BLACK이다. 모든 NIL 노드는 BLACK이다. 노드가 RED이면, 그 노드의 자녀는 BLACK이다..
개요 효율적인 알고리즘의 설계와 분석을 위해서는 3가지 중요한 기법들을 익혀야 한다. 이 것들에는 크기 동적 프로그래밍, 그리디 알고리즘, 분할상환 분석이 있는데, 이 기법들은 좀 더 복잡하지만, 컴퓨터로 해결할 수 있는 많은 문제들을 효과적으로 공력할 수 있게 도와준다. 동적 프로그래밍은 일반적으로 최적해(optimal solution)에 도달하기 위해 일련의 선택이 이루어지는 최적화 문제에 적용된다. 그리고 각각의 선택을 하는 과정에서 종종 같은 형태의 부분 문제가 생긴다. 동적 프로그래밍은 어떤 부분 문제가 둘 이상의 부분적인 선택 집합에서 발생하는 경우에 효과적이다. 또한 이 기법의 중요한 특징은 부분 문제의 해가 다시 나타나는 경우를 대비해 그 해를 저장해두는 것이다. 그리디 알고리즘도 동적 프..
DP란 다이나믹 프로그래밍이란 복잡한 하나의 문제를 여러 하위 문제들로 나누고, 각각의 결과를 저장한 후에 해당 문제에 대한 중복 컴퓨팅을 제거하여 효율성을 제거하는 문제 해결 방법이다. 즉, 같은 input에 대한 반복되는 호출을 하는 솔루션을 만났을 때, 우리는 그것을 Dynamic Programming으로 최적화 시킬 수 있다. 그리고 DP를 구현하는 방법에는 2가지가 있는데, 하나는 Tabulation이고, 하나는 Memoization이다. Tabluation ( bottom up ) tabulation을 사전에서 찾아보면, 표, 목록 등의 결과를 확인할 수 있다. 이러한 tabulation 방식은 순서대로 차근차근 값을 구하고 구한 값을 토대로 다음 값을 빠르게 구해나가는 bottom up 형태..
Trie는 문자열을 저장하고, 효유적으로 탐색하기 위한 트리 형태의 자료구조이다. 여기서 trie라는 이름은 retrieval tree에서 나온 단어이다. 즉, Trie는 radix tree, prefix tree, retrieval tree라고도 한다. Trie의 핵심 개념은 우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조라는 것이다. 예를들어, Datastructure라는 단어를 검색하기 위해서 제일 먼저 D를 찾고, 그 다음에 a, t .. 순서로 찾는 이러한 개념을 적용한 것이 Trie이다. 그렇다면 트라이의 장점은 무엇일까? 트라이의 장점은 문자열 검색을 빠르게 한다는 것이다. 문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색하는 것보다 ..
Union-Find의 개념은 다음과 같다. A와 B가 친구 관계에 있고, 내가 A와 친구 관계이면 자동으로 나와 B는 친구 관계가 된다. 이 개념을 이용해서 내가 A라는 사람과 친구 관계를 맺었는데, 그럼 내가 F라는 사람과 친구 관계가 될 수 있을지는 어떻게 알 수 있을까? 답은 친구 관계를 그래프로 나타낸 후에 나를 시작으로 그래프 탐색(DFS, BFS)를 통해 목표 지점까지 도달할 수 있는지 확인하면 간단할 것이다. 하지만 친구 관계는 언제나 새롭게 생겨날 수 있다. 그럼 친구 관계가 새로 생겼다고 할 때, F와 친구 관계가 될 수 있는지 알기위해서 다시 그래프 탐색을 진행해야 한다. 따라서 이런 방식을 사용하기 때문에 사용하는 사용자의 수가 엄청 많다면 새로운 친구 관계가 생겨날 때마다 그래프 탐..
