개발하면서/Algorithm,DS,PS
-
[Algorithm] Heap sort개발하면서/Algorithm,DS,PS 2011. 2. 28. 21:32
Heap sort란 Heap 자료구조를 이용해서 sort하는 방법입니다. 우선 Heap에 대해 알아야겠죠? http://dol9.tistory.com/129 전에 포스팅한게 있네요 : ) root에는 max값 혹은, min값이 있습니다. 정렬이 안된 데이타를 heap 구조로 만들고, root의 값 하나꺼내고 heap구조 재정렬하고 root의 값 하나꺼내고 정렬하고, 이를 반복하면 정렬된 데이타가 생성됩니다. 단순한 방법이네요;;; 아래는 지금 두줄 설명한것을 코딩한것입니다. 생각한것을 막힘없이 구현할수 있도록 많이 짜보고 피드백 받고 수정하는 일련의 과정을 반복해야겠지요... // default max heap~!! int heap_sort(void *data, int max, int data_size,..
-
[Algorithm] Bubble sort, Insert sort, Select sort, Radix sort개발하면서/Algorithm,DS,PS 2011. 1. 5. 22:22
기존에 작성되어있는것을 지우고 다시 쓰려고 했지만, 내가 얼마나 초짜인지 각성하기위해 새롭게 포스팅을 합니다. 맨처음 작성한 소스 부끄러운 내소스 입니다. 기존에 DATA_TYPE을 한 이유가 대입과 swap때문에 했는데, 그럴필요없이, memxxx함수를 이용해 가능하다는것을 알고, (qsort에서 그렇게 하는것을 보고) 다시 짜보았습니다. 와.....너무좋다. 이렇게 간단한걸, 노가다로 짠 내자신이....흑흑 main.c #include "dol9_sort.h" int compare(const void *data1, const void *data2) { return *(char*)data1 - *(char*)data2; } int main(int argc, char *argv[]) { int input..
-
2-3-4 tree개발하면서/Algorithm,DS,PS 2010. 12. 26. 11:04
2-3-4 트리란 이진트리가 한쪽으로 쏠리는 경우가 발생할수있는데 이를 해결하기위해 고안한 자료구조이다. 2-3-4 트리의 특징으로는 이진트리의 경우 하나의 노드는 하나의 데이터와 두개의 자식노드를 가질수 있는데 반해 2-3-4 트리의 경우, 세개의 데이터와 네개의 자식노드를 가질수있다. 2-3-4 트리라는 명칭은 가질수 있는 자식노드의 수때문에 나온것같다. 그렇다면 왜 1개 자식노드를 가지는 노드는 없을까? 삽입, 삭제과정에서 발생하는 연산을 보면 이해가 된다. split할때 자식이 두개인 노드생성, merge할땐 부모노드가 가진 자식노드 갯수가 3이상이므로(두개 이상의 데이타를가짐) 1개 자식노드를 가지는 노드는 있을수가 없다. (아....정말 설득력 없네요....) 마지막으로 데이타를 추가할때 이진..
-
[Algorithm]Bubble sort, Insert sort, Select sort개발하면서/Algorithm,DS,PS 2010. 12. 24. 10:35
sort 세개를 한꺼번에 포스팅하는 이유는? 세개 sort에 대해서는 자료가 너무 많아서 굳이 설명 하지 않아도 될 것같아서 였습니다. 그럼 지금 왜 포스팅을 하냐? 위 세개 알고리즘에 대한 소스를 공유하고자 입니다. 더 나은 방법이나 잘못된 부분이 있으면 알려주세요. 지금 개념 파악후 혼자 낑낑대면서 하고있는데.....정말 제가 부족하다는걸 뼈저리게 느끼고 있습니다. int와 char을 지원하고 구조체 정렬까지 하려고 했는데 이 부분에 대해선 아직 머리가 안돌아가네요 허허허 dol9_sort.c, dol9_sort.h main.c 로 구성되어있습니다. 조금 수정한 내소스 dol9_sort.h #include "dol9_sort.h" int main(int argc, char *argv[]) { //in..
-
[Algorithm] Brute Force개발하면서/Algorithm,DS,PS 2010. 12. 3. 12:42
가장 간단한 알고리즘입니다. 만약 찾고자 하는 패턴은 ABTBA, 원본 텍스트는 AAABTABTBAB일 경우 아래 그림과 같이 비교를 합니다. 아래와 같은 방법으로 문자열을 찾습니다. 패턴첫글자와 원본을 비교하면서 일치가되는것을 찾습니다. 일치가 되었으면, 다음글자가 일치되는지 확인하고, 중간에 일치하지 않는다면 바로 다음칸으로 이동해서 다시 패턴 첫 글자부터 일치여부를 판단합니다. 구현이 간단하지만 비효율적인 문자열 검색 알고리즘 이네요. int main() { char str[12] = "AAABTABTBAB"; char pattern[5] = "ABTBA"; int i = 0; int j = 0; for (; i < 11; i++) { for (; j < 5; j++) { if (str[i+j] !..
-
[Algorithm] Binary Heap개발하면서/Algorithm,DS,PS 2010. 12. 2. 23:12
Heap 이란? complete binary tree이고, 부모 노드는 항상 자식 노드보다 크거나 같음을 만족하는 자료구조이다. 출처: http://code.cloudkaksha.org/binary-tree/types-binary-tree 위 사진은 binary tree의 3가지 타입을 보여준다. full binary tree는 잎 노드를 제외한 노드들의 자식 노드가 0개 혹은 2개인 트리를 말한다. complete binary tree는 마지막 level을 제외한 모든 level에 노드가 채워져 있고 마지막 level은 최소한 왼쪽으로 노드가 채워진 트리를 말한다. perfet binary tree는 잎노드를 제외한 모든 노드들의 자식 노드가 2개인 트리를 말한다. 노드의 개수는 2^n-1개 있다.(n..