개발하면서/Algorithm,DS,PS
-
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..
-
[Algorithm] Binary tree개발하면서/Algorithm,DS,PS 2010. 12. 2. 22:56
이진트리란 ? 모든 노드의 자식노드가 2개 이상을 넘지 않는 트리를 말한다. 왼쪽자식노드는 부모노드의 값보다 작이야 하며 오른쪽 자식노드는 부모노드의 값보다 커야한다. 이진트리 의 종류 모든 레벨의 노드가 꽉 차있는 트리를 말한다. Full Binary Tree의 총 노드수는 2 ^ n -1 이다.(n은 마지막 레벨) 높이가 h인 트리의 경우 h-1까지는 모두 채워져있고 마지막 높이 h는 다 채워져있지는 않지만 왼쪽에서 오른쪽으로 순서대로 채워져있는 트리 이진트리를 순회하는 방법은 preorder, inorder, postorder가 있다. 루트 방문순서를 기준으로 이름이 붙여진것으로 이해하면 좋다 pre : 처음, in : 중간, post : 나 쓰레드 이진트리란 ? 이진트리를 구성하다보면 null 포..
-
[Algorithm] Tree 기초개념개발하면서/Algorithm,DS,PS 2010. 12. 2. 22:52
>다양한 트리를 배우기전에 트리에 나오는 명칭에 대해 알아보는 시간을 가져보자. node란 A, B, C, D, E, F, G, H, I, J, K, L처럼 데이터를 가지는 분기점을 말하고, node와 node사이의 연결선을 edge라 한다. B의 parent node는 A 이며, parent node가 없는 node를 root라하며 여기서는 A이다. B의 child는 E, F 이다. degree(차수)란 child node의 수를 말한다. A의 Degree는 3, C의 Degree는 1이다. leaf node란 child node를 가지지 않는 node로서, 여기선 K, L, F, G, M, I, J 를 말한다. B 의 subtree는 위 그림과 같이 E, K, L과 F 이다. level이란 root ..
-
KMP String matching개발하면서/Algorithm,DS,PS 2010. 11. 16. 01:21
문자열 S, P가있고, S에서 P를 검색한다고 할때, 가장 기초적인건 아래와 같이 검색을 합니다. 비효율적인부분이 있습니다. 그래서 Knuth, Morris, Pratt 세 사람이 만든 KMP 알고리즘을 지금 설명하려고 합니다. 제가 이해한것을 풀어쓰는거라 잘못 이해한 것이 있을 수도 있습니다. 그럴때는 말씀해주시면 감사하겠습니다. KMP는 패턴을 만들어서 검사에 실패했을때 다음 검사에서 불필요한 부분을 생략하는데 있습니다. 위 그림은 검사에 실패했을때 P를 오른쪽으로 한칸 이동하지만 KMP는 안해도 되는부분은 과감히 건너뜁니다. KMP는 크게 나눠보면 찾고자하는 문자열에 패턴을 구하고 그 패턴을 이용해서 검사를 하는 것입니다. 문자열 페턴 구하는것을 설명하기에 앞서 suffix, prefix에 대해 알..
-
넥슨 면접 1번문제개발하면서/Algorithm,DS,PS 2010. 2. 12. 11:32
현재 소장님이 작성하신 메모리 저장구조를 분석하고 있습니다. 일하다가 찾은 사이트에서 재미난 문제가 있어서 풀어봤습니다.(정말 일하다가? ㅋㅋㅋㅋㅋ) Nexon 면접문제 (좀 오래됐음;;;) 뭐 genrator구하는것은 쉽게 되는데 1부터 5000까지의 숫자 중 generator인지 아닌지를 체크해주는 것이 메모리 저장구조에 있는 것을 써먹으면 좋을 것 같아 적용을 시작했습니다.... 8bit * 625 = 5000~!! 딱 떨어지네요 문제도 이걸 원한 게 아닐까 생각합니다. generator에 해당하는 비트에 체크를 해주고 나중에 이 비트를 검사해서 selfnum여부를 판별하는 구조입니다. #include #include const unsigned char mask[8] = {0x1, 0x2, 0x4,..