반응형 Data Structure36 Data Structure - Graph Structure 왜 그래프 구조인가 - 가장 보편적인 구조 atomic -> 선형구조 -> 부분 순서 구조 -> 자유 구조 -> 해슁 구조 그래프의 형식적 정의 G(V,E) - vertex / edge / {vertex, edge} induced subgraph / simple graph와 general graph / connectedness, connected component / path와 trail, cycle Graph는 vertex와 edge로 이루어진 한정된 자료구조를 의미함. / vertex는 정점, edge는 정점과 정점을 연결하는 간선. / 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조( ex: 지도, 지하철 노선도의 최단 경로, 전기회로의 소자들, 도로 등) / 그래프는 여러개의 고립된 부분.. 2022. 4. 17. Data Structure - Priority Queue 우선순위 큐 (Priority Queue) 일반적인 Queue는 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 linear Data Structure. 하지만 Priority Queue는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 Queue. 일반 queue - 처음 줄 선 순서대로 / 특수 queue - 우리가 지정한 어떠한 순서대로 Priority Queue의 속성 : ㆍ모든 항목에는 우선순위가 있음. ㆍ우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 queue에서 제외됨. ㆍ두 요소의 우선 순위가 같으면 queue의 순서에 따라 제공됨. Priority Queue가 지원하는 기능 ㆍenqueue() : queue에 새 요소.. 2022. 4. 14. Tree Structure 노트10 - Suffix Tree Search Tree 구성의 종류 - key 전체를 비교하는 방법 / key의 일부를 비교하는 방법 / 각 node마다 동일한 기준으로 비교하는 방법 / 각 node마다 비교하는 기준이 다른 경우 Trie 구조가 필요한 Text Application의 전형적인 예) - Dictionary : memory를 작게 만드는 것이 중요한 작업 - 자동차 네비게이션에서 주소 찾기 or 우편번호 주소 찾기 Digital Search Tree - key 값을 binary로 바꿔서 각 level마다 비교대상을 다르게 함. - level i node에서 볼때 왼쪽 subtree의 모든 값은 i번쨰 bit = 0, 오른쪽 subtree의 i번째 bit = 1 Trie는 기본적으로 multi-way branch tree. .. 2022. 4. 14. Tree Structure 노트9 - Trie 탐색 트리 트라이 문자열 탐색을 위한 Trie(Prefix tree) 내용이 있다는 것과 그것이 '인식될 수 있는 형식'으로 표현된 것은 다르다. 주소 시스템 같이 내용이 많은걸 할때 씀. 휴대 전화에서 쓰이는 것 같은 예측 문자나 자동 완성에 필요한 사전을 저장하는 것들도 일반적인 응용중 하나/ 주로 문자열이 key인 경우가 많음./ 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 루트는 빈 문자열에 연관된다. Trie의 장단점 : ㆍ트라이는 문자열 검색이 빠름. ㆍ문자열 탐색시, 하나하나 모두 비교하면서 탐색을 하는 것 보다 시간 복잡도 측면에서 훨씬 효율적임. ㆍ각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있음. 구현.. 2022. 4. 11. Tree Structure 노트8 - Red-Black Tree Dynamic Operation을 위한 다양한 트리 자료구조가 있을 때, 사람들(coder)가 이해하기 좋은 구조와 사람에게는 어렵지만 컴퓨터에서 효율적으로 동작하는 구조 중 어느것이 좋은가? Dynamic Tree Structure를 선택하는 기준 - Tree기반의 자료구조(Splay Tree, Min-max Tree, Split Tree, Leftist Tree..)/ 얼마나 많은 데이터를 처리해야 하는가?/ inserting이 자주 일어나는가 그리고 이 작업이 연속적인가?/ on-memory에서 효율적으로 동작하는가? 아니면 disk를 사용하는가? Red-Black Tree는 복잡한 자료구조지만, 실사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행시간을 보임(worst-case guarant.. 2022. 4. 11. Tree Structure 노트7 - 2-3 Tree 높이균형트리 2-3 Tree 2-3 Tree는 내부노드의 차수가 2 또는 3인 균형 탐색트리이다. AVL 트리의 단점인 삽입과 삭제 시의 전체 트리를 재구성하는 부분을 최대한 줄이는 것이 핵심. - 노드 하나에 항목이 2개의 값이 있으며 링크는 3개가 있을 수 있음. - 노드 안에 항목의 수가 2개 있을 수 있고 각 항목은 크기대로 순서를 갖음. - 해당 노드가 가리키는 3개의 링크는 왼쪽부터 순서대로 링크 되어 있음. 단점 : 하나의 노드 안에 2개의 데이터가 모두 존재할 때 해당 노드를 분할하는 작업이 만만치 않음. 특징 : - 각 노드는 2개 이하의 항목과 3개 이하의 링크를 가짐. - 노드 안의 각 항목은 item1 2022. 4. 9. 이전 1 2 3 4 5 6 다음 반응형