본문 바로가기

(탈퇴) Reuent's Post/Algorithms

Algorithm #2. Search algorithm. - 2.5 Red-Black Tree (2). Red-Black Tree 두 번째 포스트입니다. 이번엔 Red-Black Tree 의 회전에 대해서 알아볼까요. 앞서 Red-Black Tree 의 유지조건에 대해 언급드렸을 겁니다. Introduction to Algorithms 의 Red-Black Tree 절에 따르면 다음과 같은 정의가 성립해야 하죠. 1. Every node is either red or black. 모든 node 는 적색 혹은 흑색이다. 2. The root is black. root 는 흑색이다. 3. Every leaf is black. 모든 leaf 는 흑색이다. 4. If a node is red, then both its children are black. 만약 한 node 가 적색이라면, 이 node 의 두 자식은.. 더보기
Algorithm #2. Search algorithm. - 2.5 Red-Black Tree (1). 이번에 소개할 Red-Black Tree 는 Binary search tree 의 일종입니다. 이전에 구현했던 Binary Search Tree 는 다음과 같은 node 구조체를 선언했었죠. typedef struct node{ char dat; struct node *lLink; struct node *rLink; } bTree_node; node 의 값을 저장할 변수와, 좌/우측 link node 의 값을 포함하는 구조체입니다. 하지만, Red-Black Tree 는 여기에서 '색깔' 을 저장할 추가 변수의 선언이 필요합니다. 다시말하면, 각 node 는 'Red' 혹은 'Black' 의 색깔을 갖는다는 것이죠. 그럼 이쯤에서 Red-Black Tree 의 필요성을 설명드려야 할 듯 합니다. 예전 포.. 더보기
Algorithm #2. Search algorithm. - 2.4 Binary Tree Search (2). #include #include #include /*Binary search tree 구현에 사용할 NODE 구조체. */ typedef struct node{ char dat; struct node *lLink; struct node *rLink; } bTree_node; /* Binary search tree의 구성을 위한 함수의 prototype. */ void bTreeInsert(char data, bTree_node **root); /* Tree 구성에 필요한 함수의 prototype. */ bTree_node *TreeConstruct(void); /* Binary tree searching 에 필요한 함수의 prototype. */ int bTreeSearch(char key, bTree_.. 더보기
Algorithm #2. Search algorithm. - 2.4 Binary Tree Search (1). 테슬라 군이 트리 자료구조에 대한 일반적인 설명을 해 주었군요. -_-a - Dlbo 군이 그렇게나 강조하는 테슬라 군과의 자료구조 포스팅 첫번째 연동입니다. - 트리 구조에 대한 일반론은 테슬라군이 이미 설명을 해 놓았으니 생략하겠습니다. Binary Tree 는 트리 자료구조 중에서도 각 부모 노드가 자식 노드를 2개씩 가지는 자료구조를 말합니다. Binary Tree Search 기법은 일반적으로 Binary Tree 의 일반적 특징을 따릅니다만,여기에 한 가지 조건이 더 붙죠. 그것은 각 노드에 저장되는 레코드의 값 순서가 ' Left < Root < Right ' 여야 한다는 것입니다. 일반적으로 Binary Tree Search 는 동적인 자료집합에 대해서 가장 효율적입니다. 값을 그냥 넣기만.. 더보기
Algorithm #2. Search algorithm. - 2.3 Binary Search. 이번 주제는 Binary Search. 즉, 이분 검색입니다. 왜 'Binary' 라는 표현이 나왔는지 궁금하실텐데요, 이는 검색 방식 때문입니다. 앞서 작성한 'Quick Sort' 알고리즘에서 'Divide and Conquer' 와 'Three of median' 기법을 설명 드렸을겁니다. Binary Search 알고리즘은 이 기법들을 동시에 사용합니다. 단, 전제 조건은 '이미 정렬된 레코드' 에서 사용해야 한다는 전제조건이 붙죠. 그럼 알고리즘 소개를 해 볼까요. 1. 이 레코드의 중앙값을 찾는다. - 이미 정렬된 레코드라 가정한다. - 2. . 만약 찾을 key 값이 이미 찾아놓은 레코드의 중앙값과 같다면 Find it. 3. 먄약 찾지 못했다면 3 - 1. key 값보다 중앙값이 작은 경우.. 더보기
Algorithm #2. Search algorithm. - 2.2 Sequential Search. 쫌 많이 늦었군요... 죄송합니다 -_-a; H 대학교 친구한테 C 언어 알려주느라 어제 늦게 들어왔습니다. 매번 공지도 없이 늦네요 orz. 여튼.. 각설하고. 이번 주제는 Sequential Search - 순차검색 - 입니다. 혹자는 Linear Search - 선형 검색 - 이라는 표현도 쓰기도 합니다. 이는 알고리즘의 특성때문에 나온 말이죠. - 사실 알고리즘이라 하기 좀 민망하긴 합니다. -_-;;;;; - Sequential Search 라는게 사실 별 것 아닙니다. 말 그대로 찾으려는 자료를 소스에서 처음부터 순차적으로 계속 검색해 나가는 거죠. 가령. S T U D Y I N G T H E L O G I C A L W O R L D 로 초기화되어 있는 기준 배열 input 에서 W 라는 .. 더보기
Algorithm #2. Search algorithm. - 2.1 검색 알고리즘의 종류. ( & Algorithm vs. Data Structure (??) ) 이제부터 포스팅해 나갈 주제는 Search algorithm 입니다. Sort algorithm과 마찬가지로 거의 모든 프로그램 - 사실상 전부 -_- 라고 해 두죠 - 에서 필수적인 알고리즘 중 하나입니다. Database 와의 연동이 없는 프로그램은 거의 없다고 해도 무방하기 때문이죠. 작게는 간단한 인원 관리 프로그램부터, 크게는 게임, OS, 그리고 서버에 이르기까지. 이런 거대한 자료 뭉치 - Database - 에서 원하는 자료를 찾아야 한다고 가정해 봅시다. 여러분들은 어떻게 하실 건가요? . . . 이런 물음에 대한 답은 이미 여러가지가 나와 있습니다. 정렬과 함께, 학계에서 가장 많이 연구되어 왔고 또한 필요성 역시 가장 높은 알고리즘 주제중 하나이기 때문이죠. - 그리고 아마 세계 어딘.. 더보기
Algorithm #1. Sort algorithm. - 1.6 Radix Sort algorithm. 이번엔 기수 정렬, Radix Sort 대해 알아보죠. Radix Sort 는 기본적으로 비트열을 정렬 대상으로 삼는 알고리즘입니다. 그래서 숫자 배열에 대해서는 매우 효율적인 알고리즘 중 하나입니다만, 문자 배열에 대해서는 탐색해야 할 비트열이 많아지므로 그다지 효율적인 선택이 아닙니다. 이 경우엔 다른 Sort 알고리즘을 선택하는걸 추천하죠. 우선 Radix Sort 는 두 가지로 나뉘어 집니다. 1. Radix Exchange Sort(기수 교환정렬) 2. Straight Radix Sort(직접 기수정렬) 흠... 그 중 Radix Exchange Sort 는 가장 직관적인 방법이라 할 수 있겠군요. 일상생활에서 우리가 가장 즐겨쓰는 방법입니다. 보통 인간은 10진법 체계를 사용합니다. 따라서, .. 더보기
Algorithm #1. Sort algorithm. - 1.5 Heap Sort algorithm. 이번 주제는 Heap Sort 알고리즘입니다. Heap Sort 를 알기 위해선 Heap 이란 자료구조에 대한 설명이 필요하겠군요. Heap 은 일반적으로 완전 이진트리(Complete Binary Tree) 로 추상화됩니다. - 포화 이진트리와 완전 이진트리의 차이점은 알고 계시리라 생각하겠습니다. - 우선 Max - heap 을 봅시다. 각 자식 노드와 부모 노드의 값을 비교할 때, 부모 노드의 값이 자식 노드들 보다 크게끔 완전 이진트리를 구현합니다. 그리고 재귀적으로 모든 서브 트리에 대해 위와 같은 정의를 적용해 주고, 그 이후 이 완전 이진트리를 level 별로 순회해 가면서 배열에 넣어주면 Max - heap 이 완성됩니다. - 즉, 각 서브 트리 별 루트 노드의 값이 서브 트리의 레코드 중.. 더보기
Algorithm #1. Sort algorithm. - 1.4 Quick Sort algorithm. 네. 저번주에 포스팅 하는 걸 잊었습니다. ... 그래서 이제부터 일주일 내내 하나씩 포스팅하기로 약속했습니다. - Matrix 때문에 지금 Dlbo 군에게 열심히 갈굼당하고 있습니다. -_- 이건 그것도 겸한거죠. - 큼... 각설하고. 이번 포스팅 주제는 Quick Sort 알고리즘입니다. 정렬 알고리즘 중 가장 효율적이고 사용 빈도가 높은 알고리즘 중 하나입니다. - C 언어 라이브러리 함수로 qsort() 라는게 있습니다. Quick Sort 를 라이브러리화 해 놓은 거라 쉽게 사용이 가능합니다. 이것도 이유가 될 수 있겠죠. 비교 함수만 하나 더 만들어 주면 끝이거든요. - 흠... 일단 Quick Sort 를 소개하려면 'Divide and conquer' 라는 알고리즘 기법부터 설명해야 할까.. 더보기
Algorithm #1. Sort algorithm. - 1.3 Bubble Sort algorithm. 이번은 거품정렬 . Bubble Sort에 대해서 알아보죠. 간단히 말해, 이런 이름이 붙은 이유는 정렬과정의 모양 때문입니다. 한 레코드와 인접한 index들을 비교해 가장 큰 레코드 값이 한 칸 한 칸씩 옆으로 밀려나가는 모습이 마치 거품모양과 같다 하여 이런 이름이 붙었다. .... 고 합니다. -_-;;;;;;; - 전 그렇게 못 느끼겠습니다만. 제 상상력이 부족한 건가요????- last index 가 n 인 문자열 배열 a 가 있다고 가정합시다. 이 문자열을 Alphabet order 로 Bubble Sort 를 써서 정렬하고자 한다면. 레코드 값을 비교하기 위해 레코드 쌍을 마련한다. -> 이 경우, 인접한 요소끼리 레코드 쌍을 만든다. 한 레코드 쌍의 첫번째와 두번째 요소를 비교한다. ->.. 더보기
Algorithm #1. Sort algorithm. - 1.2 Insertion Sort algorithm. 흠. 두 번째 포스트군요 ㅇ_ㅇ. 이번 포스트는 앞서 언급했던 정렬 알고리즘들을 세분화하고 그 특징. 그리고 구현법에 대해 알아보죠. 우선, 가장 간단한 것부터 알아보도록 할까요. 우선 삽입 정렬(Insertion Sort)입니다. 삽입 정렬 알고리즘은 보통 카드 게임에서 카드를 정렬하는 것으로 비유하고 있습니다. 카드 몇 장을 이미 받았다고 가정하고, 카드 덱(Card deck) 에서 카드 한 장을 뽑아 손에 쥐어 봅시다. 그리고 나서 무늬에 관계없이 카드를 정렬하려 한다고 가정합시다. 여러분들은 어떻게 하시나요? 일반적으로, 이미 카드 몇 장을 받은 시점에서 카드를 정렬할 겁니다. 우선 처음 두 장을 비교하고, 값 순서대로 배열하겠죠. 그리고 나서 아마 '이미 정렬된' 두 장의 값 범위를 비교하고 나.. 더보기
Algorithm #1. Sort algorithm. - 1.1 정렬 알고리즘의 필요성, 그리고 알려진 알고리즘의 종류와 일반적 특성. 흠... 자료구조 포스팅을 먼저 한다는걸 잊고 알고리즘부터 준비했군요 -_-;;;; 정렬 알고리즘들의 포스팅이 끝난 다음엔 기초 자료구조부터 시작하죠. - ... 포스트 제목을 정말 거창하게 지어버렸네요 -_-;; - 여튼. 이번 포스팅 주제는, Sort algorithm. 즉 정렬 알고리즘입니다. 어떤 작업을 하든지 우린 '정렬작업' 이라는걸 해야하는 경우가 많습니다. 사실 우리 주위엔 정보를 정렬하는 것이 필수적인 분야들이 많습니다. 가장 대표적인 예를 들자면 고객 관리 프로그램이겠죠. 특히 중, 고등학생들의 정보를 관리하는 학생 정보 관리 시스템이라던가. 자. 물론 자료 입력시 정렬을 해서 넣는 경우도 있겠죠. 하지만 우리가 프로그래밍을 할 땐, 우리의 고객이나 서버 채점기는 '정렬을 하지 않고 자.. 더보기