본문 바로가기

자료구조

 (34)
[ 자료구조 ] 탐색 - 04 - 1 . 레드 블랙 트리 <회전 , 삽입> [ 레드 블랙 트리 ] [ 레드 블랙 트리 ] 이진 탐색 트리는 균형있게 자라지 못하는 경우가 대부분이다 . 이런 성장은 검색 효율을 심각하게 저하시킨다 . 레드 블랙 트리는 이를 해결하기 위한 이진 탐색 트리이다 . 해당 트리를 이해하는데 해당 사이트가 많은 도움이 되었다 . 참고하면서 공부하면 좋을것이다 . 레드 블랙 트리 시물레이터 이진 탐색 트리와 다른 점은 노드를 빨강 , 혹은 검정으로 표시한다는 점이다 . 이를 구현한 구조체는 다음과 같다 . typedef struct tagRBTNode { struct tagRBTNode* Parent; struct tagRBTNode* Left; struct tagRBTNode* Right; enum { Red , Black } Color; ElementT..
[ 자료구조 ] 탐색 - 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..
[ 자료구조 ] 정렬 - 05 . qsort [ qsort 함수 ] [ 퀵 정렬 ] c언어의 표준 라이브러리에 (stdlib.h) 퀵 정렬 알고리즘이 구현된 함수가 제공된다 . qsort()함수는 다음과 같은 원형을 가지고 있다 . void qsort( void*base,//데이터 집합 배열의 주소 size_t num,//데이터 요소의 개수 size_t width,//한 데이터 요소의 크기 int (_cdecl*compare)(const void*,const void*)//비교 함수에 대한 포인터 }; 첫번째 매개변수 base는 데이터 집합 배열의 주소를 가리키는 포인터이다 . 두번째 매개변수 num은 데이터 집합 요소의 개수 (집합의 크기)이다. 세번째 매개변수 width는 데이터 요소 하나의 크기(바이트 단위)이다. 비교 수행한 결과를 반환하는..
[ 자료구조 ] 정렬 - 04 . 퀵 정렬 [퀵 정렬] [ 퀵 정렬 ] 퀵 정렬은 분할 정복 ( Divide and Conquer)에 기반한 알고리즘이다 . 퀵 정렬은 다음과 같은 과정의 분할정복으로 정렬을 수행한다 . 데이터 집합 내에서 임의의 기준 요소를 선택하고 , 기준 요소보다 작은 요소들은 순서에 관계없이 무조건 기준 요소 왼편에 , 큰 값은 오른편에 위치한다 . 기준 요소 왼편 / 오른편으로 나뉜 데이터 집합 내에서 다시 1의 과정을 반복한다 . 더이상 데이터 집합을 나눌 수 없을때까지 반복하면 정렬된 데이터 집합을 얻게 된다 . [ 기준 요소의 선택 ] 퀵 정렬이 더 빠른 성능을 갖게 하는 개선사항 중 하나는 데이터 집합 내에서 좋은 기준요소를 선택하는 것이다 . 무작위로 기준 요소를 선택하는 것은 최소 / 최대 값이 선택되는 확률을..
[ 자료구조 ] 정렬 - 03 . 삽입 정렬 [삽입 정렬] [ 삽입 정렬이란 ] 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아 이를 적당한 곳에 삽입하여 정렬해 나가는 알고리즘 . [ 정렬과정 ] 오름차순 정렬임을 가정했을때 삽입 정렬은 다음의 순서로 이루어 진다 . 데이터 집합에서 정렬 대상이 되는 요소를 선택한다 . 정렬 대상은 왼쪽 부터 선택, 범위는 2개에서 시작하여 알고리즘 반복 횟수가 늘어날때마다 1개씩 커진다 . ( 정렬 대상의 최대 범위는 데이터 집합의 크기 -1 ) 정렬 대상 가장 오른쪽의 값이 가장 큰 값을 가지고 있는지 확인한다 . 아니라면 해당 요소를 뽑아 적절한 위치 (가장 왼쪽을 기준으로 했을때 더 작은 요소가 없는 위치)를 찾는다 . 정렬 대상 내에서 삽입할 값보다 큰 값을 갖는 모든 요소를 한자리씩 오른쪽으로 이동..
[ 자료구조 ] 정렬 - 02 . 버블 정렬 [ 버블 정렬 ] [ 버블 정렬 ] 알고리즘이 데이터를 정렬하는 과정이 물 속 깊은 곳에서 일어난 거품이 수면을 향해 올라오는 모습과 같아 붙여진 이름이다 . 버블 정렬은 데이터 집합을 순회하면서 집합내의 이웃 요소들끼리의 교환을 통해 정렬을 수행한다 . [ 버블 정렬의 과정 ] 교환전 요소 둘 사이를 비교, 이웃끼리 올바른 위치에 있는지 확인한다 . (오름차순이라면 왼쪽은 오른쪽 보다 작다) 올바르지 않다면 두 요소의 위치를 바꾸어 준다 . 첫번째 , 두번째 요소간의 비교가 끝났다면 두번째 , 세번째 요소간의 비교를 수행한다 . 해당 과정의 반복으로 마지막 요소는 올바른 위치에 있게 된다 . 마지막 요소를 제외한 나머지 집합에서 다시 버블 정렬을 수행한다 . 위 과정의 반복으로 정렬이 완료된다 . [ ..

티스토리툴바