# Foundation/자료구조 (16) # Foundation/자료구조 우선순위 큐 ADT 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. 아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다. https://github.com/AeroCodeX/ 우선순위 큐 ADT 데이터에 우선순위가 존재하여, 저장된 데이터 중, 우선순위가 가장 높은 데이터부터 내보내는 ADT. 우선순위가 있는 메세지 로직에서 주로 사용된다. 분할된 우선순위 큐 ADT (Separated Priority Queue) 우선순위 큐를 구현할 수 없거나, 우선순위의 범위가 충분히 작은 경우.각 레벨마다 대응되는 큐를 하나씩 만들어 사용하는 방법도 있다. 우선순위 큐 ADT의 구현과 성능Unsorted List/Array데이터를 삽입할 때 : O(1)가장 큰 값을 탐색할 때 : O(n)가장 큰 값을 제거할 때 : 최.. 2019. 2. 9. 10:47 # Foundation/자료구조 힙 ADT 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. 아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다. https://github.com/AeroCodeX/ 힙 ADT 최대/최소를 효율적으로 찾기위한 완전 K진트리 기반 ADT. (Based Complete K-ary-Tree ADT)힙 ADT를 구현화하면 자료구조로 간주하며, 보통 이진트리로 구현 함. 최댓값을 찾기위한 힙은 Max Heap 이라고 하며,최솟값을 찾기위한 힙은 Min Heap 이라고 부른다. Complete 트리를 기반으로 하면, 배열로 구현했을 때 삽입의 성능을 향상시킬 수 있다. 데이터를 삽입할 위치의 인덱스가 size와 동일해지기 때문. 힙의 특징 Max Heap힙의 루트는 항상 최댓값을 갖는다.부모는 항상 자식보다 .. 2019. 2. 8. 14:16 # Foundation/자료구조 이진트리 ADT 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. 아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다. https://github.com/AeroCodeX/ 이진트리 ADT 모든 노드의 차수가 2 이하인 트리.이진트리 ADT를 구현화하면 자료구조로 간주한다. 이진트리의 상태 & 종류Rooted Binary-Tree (루트 이진트리)루트 노드만 존재하는 이진트리. Full/Strictly Binary-Tree (정 이진트리)모든 노드의 차수가 0 또는 2. Complete Binary-Tree (완전 이진트리)트리의 높이 - 1 레벨까지는 꽉찬 트리.단, 마지막 레벨의 노드는 좌측부터 채워져 있어야 한다. Perfect Binary Tree (포화 이진트리)마지막 레벨까지 꽉찬 트리. + P.. 2019. 2. 6. 16:38 # Foundation/자료구조 트리 ADT 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. 아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다. https://github.com/AeroCodeX/ 트리 ADT 다음 성질을 만족하는 그래프 ADT를 트리라고 한다.순환회로가 없고,각 노드를 참조하는 노드의 개수가 1개 또는 0개인 그래프. 트리는 ADT? 자료구조?A tree is a widely used abstract data type (ADT)— or data structure implementing this ADT. 트리는 넓은 의미에서 ADT로 사용되나,구현화된 트리는 자료구조로 사용한다. 출처 : 위키백과(en) 트리에서 사용되는 용어 노드의 종류루트 노드 (Root Node) : 부모가 없는 최상위 노드단말 노드 (Le.. 2019. 2. 6. 15:15 # Foundation/자료구조 그래프 ADT 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. 아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다. https://github.com/AeroCodeX/ 그래프 ADT 유한한 정점(=노드, 점)과 두 정점을 잇는 변(=간선, 엣지)으로 정의되는 추상적 자료형.간선의 특성에 따라 그래프의 종류가 결정된다.방향성 有. (Undirected Graph)방향성 無. (Directed Graph)가중치가 있음. (Weighted Graph) 그래프 ADT의 구현방식 그래프는 전통적으로 2가지의 방식으로 구현할 수 있다.인접 배열 (Adjacency Matrix)인접 리스트 (Adjacency List) 구현에 따른 그래프의 성능 인접 배열?메모리 사용량은 항상 O(n^2)두 노드간 정보를 조회하.. 2019. 2. 6. 11:44 # Foundation/자료구조 덱 (데크) 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. 아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다. https://github.com/AeroCodeX/ 벡터의 한계벡터는 첫 지점에서 데이터 삽입/삭제의 성능이 떨어짐.→ 앞에도 청크를 붙이면 되는거 아냐?→ 덱(데크)의 등장 덱 (데크) 앞 뒤로 유동적인 확장이 가능한 고수준 배열.벡터처럼 여러개의 배열(청크)가 모여 하나의 데크를 이룬다. 앞이 꽉 찬 상태에서, 앞에 데이터 삽입을 시도하면, 앞에 새로운 청크를 덧붙이고.뒤가 꽉 찬 상태에서, 뒤에 데이터 삽입을 시도하면, 뒤에 새로운 청크를 덧붙인다. 덱 (데크)의 특성 여러개의 독립적인 배열(청크)을 접한한 것 이다.논리적 수용량의 제한이 없다.어느 위치에서든 데이터를 가져오는 것.. 2019. 2. 4. 11:00 # Foundation/자료구조 환형 배열 (원형 배열) 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. 아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다. https://github.com/AeroCodeX/ 배열의 특성과 한계 메모리 위에서 일렬로 인접하게 저장된다.한번 정해진 데이터의 수용량을 확장하기 힘들다.어떤 위치든 빠르게 데이터를 얻을 수 있다. (상수시간)처음이나 중간에 데이터를 삽입하려면 데이터를 한칸씩 뒤로 밀어내야 한다. (선형시간)처음이나 중간에 데이터를 삭제하려면 데이터를 한칸씩 앞으로 당겨야 한다. (선형시간)마지막 위치에서 데이터를 삽입/삭제하는 것은 빠르다. (상수시간) 환형 배열 (원형 배열) 배열의 처음과 끝을 유동적으로 바뀔 수 있게 변경한 형태.인덱스 관리비용을 지불하고, 첫 지점에서의 삽입/삭제 성능을 얻.. 2019. 2. 3. 21:53 # Foundation/자료구조 큐 ADT 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. 아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다. https://github.com/AeroCodeX/ 큐 ADT 터널에서 차가 들어가고 빠져나가는 것 처럼,먼저 삽입한 데이터가 먼저 빠져나오는 자료구조 인터페이스. First-In First-Out (FIFO)Last-In Last-Out (LILO) 큐 ADT의 특성 먼저 삽입한 데이터가 먼저 빠져나옴. (FIFO or LILO)큐의 First에서만 조회/삭제가 일어남.큐의 Last에서만 삽입이 일어남. 구현에 따른 큐의 성능 큐의 First에서만 조회/삭제가 일어나고, Last에서만 삽입이 일어나기 때문에.한 쪽에서는 조회/삭제 성능이 좋고, 반대쪽은 삽입 성능이 좋은 구현을 사용하.. 2019. 2. 3. 21:37 이전 1 2 다음
