개발하면서/Algorithm,DS,PS
-
[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,..