School/DataStructure

Data-Structure - Arrays and Structure

KMP Pattern Matching 이 KMP패턴 매칭 문제는 비교한 정보를 최대한 활용하자는 취지에서 나타난 알고리즘입니다. 먼저 pattern에 해당하는 failure함수를 작성해 주어야 합니다. failure 함수는 접두사를 활용합니다. 이는 maximum length - 1 of the prefix and suffix that matches in the partial patterns으로 정의됩니다. 즉 j = 4일 때 위의 예시에서 "abcab"인데 -> ab c ab로 나눌 수 있고 |ab| - 1은 1이기 때문에 failure[4] = 1이 됩니다. 비슷하게 j = 5일 때는 "abcabc"인데 -> abc abc로 나눌 수 있고 ( 겹치는 부분 허용 ) |abc| - 1은 2이기 때문에 f..

Data-Structure - Tree

Terminology Definition tree는 위와 같이 정의됩니다. root라는 특수한 노드가 있고 이 root라는 노드를 기준으로 disjoint한 Tree의 set으로 나누어 집니다. 이를 subtree라고 합니다. Representation of Trees 대게 list로 위와 같이 Child Node를나열해서 Tree를 표현할 수도 있습니다. 하지만 이는 일반적이지 않은 방법이고 아래와 같이 Left Child-Right Sibling Representation을 사용하기도 합니다. (underground yea~) Left Child-Right Sibling Representation 이와 같이 left-child는 leftmost child를 가리키고 right sibling필드는 이..

Data-Structure - Linked-List ( Application - 3 )

Equivalent Relations Equivalent Relation이란 symeetric, relfexive, transitive을 모두 다 만족하는 관계를 말합니다. 간단한 예시는 위와 같습니다. 이는 매우 중요한데, 그 이유는 equivalent relation이 signal net을 검증하기 때문입니다. equivalence를 결정하는 알고리즘은 아래와 같습니다. 2D array representation 위의 알고리즘을 구현하기 위해서는, 2차원 배열 pairs[n][m]이 사용되어야 합니다. 여기서 m은 related pairs의 개수고, n은 objects의 개수입니다. 하지만 이는 엄청난 공간 낭비를 할 수 있습니다. 그 이뉴능 아주 적은 배열의 값만이 사용될 수도 있기 때문입니다. 또..

Data-Structure - Linked-List( Application - 2 )

Available Space List (1) Available spcae list 또는 avail lsit는 우리가 새로운 node가 필요할 때 평가해서 그 때 그 떄 사용할 수 있습니다. 또한 처음에는 avail는 NULL로 초기화 됩니다. 우리는 node를 malloc()하거나, free()하는 것이 아니라, 아래서 볼 getNode()이나 retNode()를 사용하면 됩니다. 이는 getNode()메소드의 기본적인 작동 방식을 묘사한 것입니다. avail이 있다면 이 avail은 avail->link를 가리키게 하고 avail을 필요로 하는 node에게 avail을 주어주는 방식으로 작동됩니다. 이는 retNode()메소드의 기본적인 작동 방식을 묘사한 것입니다. node->link를 avail을 ..