반응형 자료구조23 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 편향적인 상태를 방지하여 트리의 높이를 항상 일정. - 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소 이상. 부모 자식간의 관계만 중요하기 때문에 왼쪽 자식과 오른쪽 자식에 대해서는 크기 제한 X - 최대값 or 최솟값이 Root에 위치하기에 해당 값을 찾을 시 연산이 효율적. - 최대 힙(Max Heap): 부모노드 값 ≥ 자식 노드 값 - 최소 힙(Min Heap): 부모노드 값 ≤ 자식 노드 값 완선된 Heap은 아래와 같습니다. - Max Heap이므로 Root Node에 위치한 값은 최대값입.. 2021. 2. 27. 그래프 정의 및 구현 방식 (인접 행렬 & 인접 리스트) 그래프는 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 정점을 연결하는 간선(edge)들의 집합 E로 구성된 자료 구조로 객체들의 상호 관계를 표현하기 위해 고안된 자료 구조입니다. 여러 도시들을 연결하는 도로망, 사람들 간의 지인 관계, 웹사이트 간의 링크 관계 등이 우리 주변에서 찾을 수 있는 연결 구조의 예라고 할 수 있습니다. 여러 객체들이 서로 연결되어 있다는 점에서 그래프는 트리와 별로 다를 것이 없습니다. 그래프 표현 ▶ 인접리스트와 인접행렬 메모리 or 시간 사용 특성이 굉장히 다르기 때문에, 적절한 표현 방식 선택 인접리스트(adjacency list) - 각 정점마다 하나의 연결 리스트를 갖는 방식 |V|개의 연결 리스트에 실제 간선 수만큼의 원소가 들어.. 2021. 2. 25. 그래프 표현 (인접 리스트 / 인접 행렬) 정점 u - v 간 간선 여부 확인 - 인접 리스트는 adList[u]의 처음부터 읽어나가면서 각 원소를 일일이 확인 - 인접 행렬은은 정점 u, v가 주어졌을 때, 단 한 번의 배열의 접근으로 연결 여부 확인 공간 복잡도 - 인접행렬: V × V 개수 만큼 공간 필요 - 인접리스트: 정점 개수 V와 실제 간선의 개수 E에 좌우 (V + E) (만약 간선의 개수가 V에 수렵한다면 인접행렬 비슷한 공간복잡도를 가짐) 결론 - 간선의 수가 V2에 비해 훨씬 적은 그래프를 희소 그래프 → 인접 리스트 - 간선의 수가 V2에 비례하는 그래프를 밀접 그래프 → 인접 행렬 방향성 그래프 (인접 리스트) import java.util.ArrayList; import java.util.Iterator; import j.. 2021. 2. 25. 이전 1 2 3 다음 반응형
