프로그래머, 보안 관련 지식/자료구조 썸네일형 리스트형 자료구조 : Tree(3) - AVL Tree - 이번 포스팅에서는 다른 Tree 구조를 알아보는 시간을 가지겠다. Contents AVL Tree Idea AVL Tree Definition AVL Tree Height Bound Proof AVL Tree Insertion AVL tree 는 최악의 경우에서 tree height 가 크지 않은 tree 구조이다. 지난번에 다른 BST보다 훨씬 더 어려울 것이다. AVL Tree Idea 아이디어는 다음과 같다. 위의 tree 구조를 살펴 보자. 보기에 아름다운(?) 구조 인가? 아마 대부분 그렇게 생각하지 않을것이다. Tree 가 왼쪽으로 쏠려 있는 모양을 하고 있기 때문이다. 그럼 위의 그림을 직관적으로 봤을떄 어떻게 고치면 높이가 최소화된 Tree 모양이 나올까? 아마 4가 root인 모양으로 변.. 더보기 자료구조 : Tree(2) - Binary Search Tree- 지난 번에 이어서 Binary Search Tree 의 Delete 과정을 자세하게 알아보겠다. 앞의 Search 와 Insert에 비해 복잡하기 때문에 험난한(?) 여정이 될 것이다. Delete Algorithm Do search() first If Search() fails, Delete() also fails If Search() succeeds Case 1 : Node has no Child Case 2 : Node has one Child Case 3 : Node has two Children Case 1 Correctness trivial child가 없는 노드를 지울 때 아무 문제 없는지 살펴보자. 만약 8번 노드 왼쪽에 subtree 가 있으면 지워져도 그 subtree는 child가 없.. 더보기 자료구조: Tree(1) - Binary Search Tree - 오늘은 Search , Insert , Delete 모두 다 빠른 성능을 보여주는 Tree에 대해 알아보겠다. Contents Skip List idea from Linked List Binary Search Tree Definition Search Algorithm, Insert Algorithm, Delete Algorithm Proofs of Correctness and Performance Skip List 지난 포스트의 Skip List의 아이디어를 활용한 것이다. ( 링크드 리스트에서 여러개의 포인트를 설정하고 노드들 Jump 하기 ) Definition of Binary Search Tree 값은 아무거나 넣을 수 있다. 노드 3개를 묶어서 보았을 때 중간 노드의 값보다 큰 값은 오른쪽 작은.. 더보기 자료구조: Linked List Contents Definition of Linked List Implementation Performance Sample Application Definition of Linked List Consists of Nodes Node : unit of storage (item) Nodes are linked with pointers ( what does that mean? ) **Pointer: Simply Stores an Address Linked list는 배열과 다르게 메모리 아무데나 있을 수 있다. 대산 한 노드에 가면(=한 노드의 주소를 알아서 그곳의 내용을 읽으면) 다음에 갈 노드의 주소가 적혀있다. 즉 노드들이 포인터들도 연결이 되어 있는 것이다. Linked List의 노드의 구조를 살펴보.. 더보기 자료구조: Equivalence Relation(동치 관계) 이번 포스트에서는 동치관계에 대해 알아보는 시간을 가지겠다. 지난번에 이이서 stack 과 queue를 활용한 방법들을 보여줄 예정이다. Contents ( 이번 포스트의 내용 ) Another Application of stack and DFS What is an Equivalence Relation? What is an Induced Equivalence Class? How to find the Induced Equivalence Class given an Equivalence Relation? Performance Considerations Definition of Equivalence Relation First, Definition of Relation Given a set A, a Relatio.. 더보기 자료구조: Stack & Queue (3) 오늘은 지난번에 이어서 미로찾기 문제를 Queue를 이용해서 푸는 방법을 알아보겠다. Map 하고 i,j는 지난번 방법과 같다. 다만 지난번 방법하고 다르게 가까운데를 먼저 가보게끔 구현을 하게된다. 이러한 BFS 의 특징중에 하나는 제일 짧은 길을 찾을 수 있다는 것이다. 코드는 다음과 같은 형식을 가지게 된다. BFS 명시적 Queue 1 2 3 4 5 6 7 8 9 10 11 12 13 14 int Map[M][N]; int i, j; int Find() { QueueInsert(0, 0); while( ){ ( i, j ) = QueueDelete() //방문하기 직전, Queue가 Empty이면 실패 //Map[i][j] == 0인 경우만 Map[i][j] = '*'; //목적지 확인 // (i.. 더보기 자료구조 : Stack & Queue(2) 이번 포스팅에서는 앞서 배운 스택과 큐를 응용해서 어떤 것을 할 수 있는지 알아보도록 하겠다. Stack, Queue 응용 # 미로찾기 이런 미로 문제를 해결하는 알고리즘 중에 DFS 와 BFS가 있다. 오늘은 DFS로 미로를 찾는 과정을 알아볼것이다. 먼저 미로길을 찾기 위해서는 크게 2가지 Tool이 있어야 한다. 하나는 실을 풀어서 다시 제자리로 돌아올수 있는 Tool, 그래야 막혔을때 다시 뒤로 돌아올수 있기 때문이다. 이것은 Stack 의 구조를 이용해서 좌표들을 저장해놓고 다시 뒤로 스택에서 뽑으면 뒤로 돌아갈수 있게 할수 있다. 그리고 갔던길을 다시 가지 않도록 하는 Tool 이 필요하다. 갔던길에는 0대신 다른 값으로 채워넣으면 되고 나중에 돌아왔을때 다른값으로 채워진 곳은 가지 않도록 하.. 더보기 자료구조 : Stack & Queue(1) 이번 포스팅에서는 Stack과 Queue라는 자료구조에 대해 알아보자. Stack Insert/Delete만 제공 Push/Pop이라고 부름 Last in, First out(나중에 들어오는게, 먼저 나가는 것) 성능: Push: O(1), Pop: O(1)(넣는것을 push, 빼는것을 pop) Queue Insert/Delete만 제공 First in, First out( 먼저 들어오는게, 먼저 나가는 것) 성능: Insert O(1) , Delete O(1) Stack 구현 Stack Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int Stack[N]; int SP; int init() {SP = 0} int isEmpty() {return SP == 0;} int .. 더보기 자료구조: String Matching(2) 지난번에 이어서 패턴 문제를 KMP 알고리즘에서 어떻게 처리하는지에 대해 알아보겠다. KMP 알고리즘은 DFA와 비슷하면서도 조금 더 메모리를 적게 먹는 알고리즘이다. 전반적인 과정은 비슷하지만 텍스트와 패턴을 비교했을때 다른 글자가 나올경우 다른 방법으로 처리하게 된다. 위에가 text 밑에를 pattern이라고 하자. 그리고 위의 숫자가 써있는 표가 있다. 이것의 용도를 차차 설명하겠다. 일단 상황을 하나 가정하자 텍스트에 값들이 써져있다고 생각한다. 아래의 사진을 보자 일단 맨위의 숫자는 생각하지 말고 글자 위에 다음과 같은 숫자들이 있고 빨간색은 패턴과 텍스트가 서로 지금까지 일치함을 뜻한다. 그리고 이제 다음으로 볼글자가 다음과 같이 c로 같다고 생각해보자. c 위에는 어떤 숫자를 써야할까? D.. 더보기 자료구조 : String Matching(1) 이번 포스팅에서는 String Matching이 뭔지에 대해 알아보자. Problem Defintion Text : Simple String of Characters Pattern: Simple String of Characters To Do : find where in the Text Pattern Occurs String Matching 문제는 Text 에서 패턴을 발생하는 곳을 찾는 문제이다. abababcabcabcdabccbaabdabcabcdabcd 다음과 같은 text에서 abcabcd 를 찾는 문제라고 생각해보자. 일반적으로 사람이 이 일을 할때 어떻게 할수 있을까? 대보면서 한글자씩 옆으로 밀어가며 찾을 것이다. 이 방법은 상당히 느린 작업이고 이것보다 더 빠르게 찾는 방법이 존재한다. .. 더보기 이전 1 2 다음
