해나의 컴공생존기

AVL Tree Idea 아이디어는 다음과 같다. 위의 tree 구조를 살펴 보자. 보기에 아름다운(?) 구조 인가? 아마 대부분 그렇게 생각하지 않을것이다. Tree 가 왼쪽으로 쏠려 있는 모양을 하고 있기 때문이다. 그럼 위의 그림을 직관적으로 봤을떄 어떻게 고치면 높이가 최소화된 Tree 모양이 나올까? 아마 4가 root인 모양으로 변형 시키면 높이가 좀더 낮아질것이라고 생각했을 것이다. 어떤가 ? 아까 Tree 에 비해 좀더 height가 낮아진 균형이 잡힌 tree 구조로 보일 것이다. 이런식으로 tree구조를 만들어 나가는 과정을 가지게 될것이다. AVL Tree Definition Each Node has Two Labels: L and R L : Height of Left Subtree,..

Definition of Binary Search Tree 값은 아무거나 넣을 수 있다. 노드 3개를 묶어서 보았을 때 중간 노드의 값보다 큰 값은 오른쪽 작은 값은 왼쪽으로 들어가게되는 형태이다. Code for Node class Node { int k; Node *l, *r; };​ Search Algorithm Node *Search(Node *N, int x) { if (N == Null) return NULL; if (N -> k == X) return N; else if (N->k r,X) else return Search(N->1, X); };​ Search Correctness To Prove : 만약 x가 노드에 있다면 Search() 는 그 노드..

1. vector Vector: Variable-Size Array(사이즈가 늘어나고 줄어들 수 있는 배열) Sorted Search: O(log n), Insert: S+ O(n) , Delete: S+ O(n) Unsorted Search: O(n), Insert: S + O(1), Delete: S + O(1) 2. Dummy Nodes Standarad Linked List에 대부분 포함되는 구조. 처음에 만들때 노드를 두개 만들고 하나는 마이너스 무한대 하나는 플러스 무한대 값을 집어넣는다. 이 두 값은 실제로 사용하는 값은 아니고, 미리 경계를 정해놓는 것이다. 이렇게 해놓으면 못찾았을때 (실패했을 때), P와 L이 NULL인 경우가 없어지게 된다. 3. Circular List Circula..

Linked List 연속적인 노드 Node : unit of storage (item) Nodes are linked with pointers Linked list는 배열과 다르게 메모리 아무데나 있을 수 있다. 대산 한 노드에 가면(=한 노드의 주소를 알아서 그곳의 내용을 읽으면) 다음에 갈 노드의 주소가 적혀있다. 즉 노드들이 포인터들도 연결이 되어 있는 것이다. Linked List의 노드의 구조를 살펴보면 다음과 같다. Whole List 이런식으로 구성이 되어있다. (화살표 등은 사람이 보기 쉽게 표현한것이다.) 마지막 노드에는 더이상 갈 곳이 없으므로 null값을 넣는다. 첫번째 노드로 갈때는 어쩔수 없이 그 노드가리키는 포인터를 가지고 있어야 한다. Code for List class No..

Equivalence Relation 정의 관계의 정의 Given a set A, a Relation on A is any subset of AxA Ex) A = {1, 2, 3, 4}, R = {(1,3), (3,4), (1,1), (2,2)} We write 1R3 to mean (1,3) ∈ R An extreme example Relation '

Queue Insert/Delete만 제공 First in, First out( 먼저 들어오는게, 먼저 나가는 것) 성능: Insert O(1) , Delete O(1) Queue 구현 Stack과 다르게 Queue는 Head와 Tail 두개가 필요하다. 앞서 다룬 stack보다 좀더 생각할 거리가 늘어나게 된다. 만약 새 값이 insert 될때 Tail과 Head는 어떻게 될까? head는 그대로 있고 Tail은 위로 한칸 움직일 것이다. 반대로 값이 delete 되면 Head가 위로 한칸 올라갈것이다. 그렇다면 다음과 같은 상황에서 Tail에 새 값이 새로 insert가 되면 어떻게 될까? 간단하다 제일 밑의 빈공간에 Tail이 가리키게 된다. 아래의 그림과 같이 말이다. 그러면 이 상황에서 좀 더 ..

Stack Insert/Delete만 제공 Push/Pop이라고 부름 Last in, First out(나중에 들어오는게, 먼저 나가는 것) 성능: Push: O(1), Pop: O(1)(넣는것을 push, 빼는것을 pop) Stack 구현 Stack Pointer는 값이 다음에 들어올 자리를 뜻한다. Stack Code int Stack[N]; int SP; int init() {SP = 0} int isEmpty() {return SP == 0;} int Push() { Stack[SP] = x; SP++; } int Pop() { SP--; return Stack[SP]; }​ # 미로찾기 이런 미로 문제를 해결하는 알고리즘 중에 DFS 와 BFS가 있다. 오늘은 DFS로 미로를 찾는 과정을 알아볼..

Problem Defintion Text : 간단한 문자열 Pattern: 간단한 문자열 To Do : 패턴을 발생하는 곳 찾기 Text : abababcabcabcdabccbaabdabcabcdabcd 다음과 같은 text에서 abcabcd 를 찾는 문제라고 생각해보자. 사람이라면 한글자 한글자 보겠지만 굉장히 느린방법이고 사람중심적인 방법이다. 1) Naive 알고리즘 Naive 알고리즘은 아까 위에서 설명한 사람이 한 것과 같은 방식의 알고리즘이다. 사람이 할때는 패턴을 하나씩 옮겼지만 컴퓨터로 이를 구현할때 어떻게 표현해야 할까? 코드로 표현하면 다음과 같다. // n 은 문자열의 길이 // m은 패턴의 길이, output은 결과 int naivematch ( char T[], int n, cha..

대부분의 자료구조는 Search, Insert, Delete가 중요하다. 오늘은 배열의 Search, Insert, Delete 를 보려고한다. 배열 상태에 따라 방법이 달라진다 Packed vs Unpacked : 빈자리가 있나 없나 Sorted vs Unsorted : 정렬이 되어있나 없나 총 4가지 경우를 보려고 한다. Case 1 ) Packed, Unsorted 가장 간단한 방법 Item의 개수를 표시하는 변수가 따로 필요 하다. => 위 배열을 보면 item이 5개 있으니 어딘가에 5라고 저장 해놓으면 해결된다. Search : n개의 배열에서 어떤 값 x가 있는지 없는지 확인, O(n) Insert : [Search, O(n)], O(1)(상수시간) Delete : [Search, O(n)]..

우선 Merge Sort에 대해 알아 보기 전에 Merge에 대해 알아보자. Merge 와 Merge Sort 는 서로 같은 뜻 같지만 실제로는 둘이 조금 다르다. Merge 알고리즘은 soring 된 배열 두개를 합쳐서 새로운 배열을 만드는 알고리즘이다. 두 배열을 앞에서부터 비교해 나가면서 작은것들을 복사해서 한 배열에 넣는 알고리즘이다. 이러한 알고리즘을 이용하는 것이 Merge Sort 이다. 어떤 배열을 나눈다음에 서로 2그룹씩 합치면서 점점 올라오면서 정렬하는 것이 Merge Sort의 기본적인 로직이다. int sort(int a[], int n) { int h; int b[n]; h = n / 2; // copy a[] to b[] sort(b,h); // 반 나눈거의 앞부분 sort(b+..