현서의 개발 일지📚

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을 ..

Java Programming - Collection Framework

컬렉션 프레임워크 소개 애플리케이션을 개발하다 보면 다수의 객체를 저장해 두고 필요할 때마다 꺼내서 사용하는 경우가 많다. 만약 10개의 Product 객체를 저장해 두고, 필요할 때마다 하나씩 꺼내서 이용한다고 가정해봅시다. 어떻게 Product객체를 효율적으로 추가, 검색, 삭제할지 고민하게 되는데, 가장 간단한 방법은 배열을 이용하는 것입니다. 배열은 쉽게 생성하고 사용할 수 있지만, 저장할 수 있는 객체 수가 배열을 생성할 때 결정되기 때문에 불특정 다수의 객체를 저장하기에는 문제가 있습니다. 물론 배열의 크기를 크게 생성하면 되겠지만, 이것은 좋은 방법이 될 수 없습니다. 배열의 또다른 문제점은 객체를 삭제했을 때 해당 인덱스가 비게 되어 낱알이 듬성듬성 빠진 옥수수가 될 수 있습니다. 그렇게 ..

Data-Structure - Linked list ( Applications )

Polynomials 우리는 다음과 같은 polynomials를 구조체를 통해서 구현을 했었습니다. 근데 이는 linked-list를 통해서도 더욱 효율적이고 간편하게 만들 수 있습니다. 바로 이렇게 생긴 구조체와 자기참조 구조체를 통해서 linked-list를 구현하면 됩니다. data칸에 float형 coef(계수)와 int형 expon(지수)를 넣고 다음 linked-list를 가리킬 link를 만들어 주면 됩니다. 간단합니다!! 각각의 a, b다항식을 위와같이 linked-list로 표현을 해 주었습니다. 기본적인 추가 규칙은 구조체를 활용해서 간단히 구현했을때와 다른것이 없습니다. 그냥 expon(지수)를 비교해서 각각의 경우에 다르게 처리해 주면 끝입니다. 하지만 linked-list답게 포인..