본문 바로가기

old/자료구조
10

그래프(Graph) 그래프는 엄밀히 말하면 자료구조가 아니지만, 많은 책들이 자료구조에서 소개하고 있다. 그래프란? 2개 이상의 항목이 어떤 관계를 맺고 있는지 노드(정점)과 엣지(선)을 이어 표현하는 것. 2020. 11. 14.
힙(Heap) 힙이란? 1. 이진 트리의 일종으로, 여러 개의 값 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있도록 구성된 자료구조 - 최대 힙(Max Heap) : 부모 노드의 값이 항상 하위 노드의 값보다 큰 경우 - 최소 힙(Min Heap) : 부모 노드의 값이 항상 하위 노드의 값보다 작은 경우 2. 컴퓨터에서 프로세스가 만들어질 때 메모리를 할당하는 데, 이 때 메모리를 할당하는 방법 중 하나. 용도 프로세스의 우선순위를 결정하는 방법으로 최대 힙을 사용할 경우. - 우선순위 숫자가 큰 프로세스가 최상위에 위치한다. - 프로세스를 요청할 때는 최상위 노드(루트 노드)에 있는 프로세스를 반환한다. - 루트 노드가 반환되면 나머지 노드를 우선순위 숫자에 근거하여 트리 구조를 재구성하고, 가장 높은 .. 2020. 11. 14.
이진 트리(Binary Tree) 이진 트리란? 트리 자료구조 중에서 모든 노드가 최대 2개의 자식 노드를 가질 수 있는 구조. 자식 노드를 각각 왼쪽 자식 노드, 오른쪽 자식 노드라고 한다. 왼쪽 서브 노드의 값은 루트의 값보다 작고, 오른쪽 서브 노드의 값은 루트보다 큰 값을 가지도록 구성한다. 용도 주로 빠른 검색이 필요한 곳에서 사용. 그래서 이진 검색 트리라고도 한다. 프로그램 로직을 구성하면서 사용자가 입력한 정보를 관리한다. (주로 수식 표현) 모양에 따른 분류 포화 이진 트리(Full Binary Tree) : 레벨의 노드가 꽉 차 있는 트리 완전 이진 트리(Complete Binary Tree) : 마지막 레벨 전까지는 노드가 꽉 차있고, 마지막 레벨의 왼쪽에서 오른쪽으로 노드가 채워져 있는 트리. (마지막 레벨이 다 채.. 2020. 11. 14.
트리(Tree) 트리란? 임의의 노드에서 다른 노드로의 경로가 하나 밖에 없는 자료구조. 노드 중에 단 하나의 루트 노드(Root Node)가 있고, 루트 노드에서 하위 노드(Sub Node)들이 연결된 비선형 계층 구조. 종류 일반 트리 이진 트리 : 다음 데이터를 가리키는 것이 2개인 단방향 트리 구조. 한 노드의 자식 노드가 최대 2개인 트리 구조. 용도 운영체제의 파일 시스템 구현 방법 배열이나 연결 리스트 용어 깊이(Depth) : 루트 노드로부터의 거리. 루트 노드로부터 특정 노드까지 가기위한 간선의 수. 루트 노드의 깊이는 0이다. 깊이 1의 노드를 뿌리의 자식 노드, 깊이 2의 부모 노드라고도 표현한다. 레벨 : 특정 깊이를 가지는 노드의 집합. 잎(Leap) : 자식 노드가 없는 노드. 2020. 11. 14.

최근댓글

최근글

skin by © 2024 ttuttak

티스토리툴바