1. 개념 : 여러 데이터들의 묶음을 어떻게 저장하고 효율적으로 사용할지 정의한 것 (특정한 상황에 놓인 문제를 해결하는 데 특화됨)
데이터(data = 자료) : 문자 • 숫자 • 그림 • 소리 • 영상 등의 형태로 된 모든 단위 (실생활을 구성하고 있는 모든 값) - 데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있으며, 사용 목적에 따라 형태를 구분하고 분류하여 사용
2. 분류 :
단순 구조
2진수
정수 / 실수
문자 / 문자열
선형구조
순자 리스트(배열, Array) ---------------->
연결 리스트
단순 연결 리스트
이중 연결 리스트
원형 연결 리스트
스택(Stack)
큐(Queue)
덱
비선형 구조
트리(Tree)
일반 트리
이진 트리(Binary Tree) : 자식노드가 최대 2개인 노드들로 구성된 트리 (왼쪽, 오른쪽 자식노드로 나눌 수 있음)
그래프(Graph)
방향 그래프(비대칭 관계)
무방향 그래프(대칭 관계)
파일 구조
그래픽(graph)
1. 개념 : 각 항목을 의미하는 노드(정점 = vertex)와 간선(edge)으로 구성된 자료 구조. 검색 시스템에서 많이 활용
2. 용어 :
정점(vertex) : 노드라고도 함, 데이터가 저장되는 그래픽의 기본 요소, 연결한 객체들을 의미
간선(edge) : 정점들을 이어주는 선 (정점간의 관계)
인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점
경로(path) : 정점A에서 정점B까지 간선에 따라 갈 수 있는 길을 순서대로 나열한 것
단순경로(Simple-Path) : 경로 중 반복되는 정점이 없는 것, 같은 간선을 지나지 않는 경로
사이클(Cycle) : 경로의 시작 정점과 마지막 정점이 같은 경로를 의미
트리(Tree)
1. 개념 : 노드로 구성된 계층적 자료구조, 최상위 노드(루트)를 만들고 그 아래 자식 노드를 추가하는 방식 사이클이 없는 일방향 그래프(최소연결트리), 비선형 구조, 깊이 • 높이 • 레벨 측정 가능
2. 용어 :
노드(node)
루트 노드(root node) : 트리 구조의 시작점이 되는 최상위 노드
리프 노드(leaf node) : (=단말 노드) 트리 구조의 끝지점이 되고, 자식 구조가 없는 차수가 0인 노드
내부 노드(internal node) : 단말 노드가 아닌, 차수가 1 이상인 노드
크기(size) : 자신을 포함한 모든 자식 노드의 개수
차수(degree) : 하위 트리개수
간선수(degree) : 각 노드가 지닌 가지의 수
깊이(depth) : 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 - 루트 노드에서 시작 ↕
레벨(level) : 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 노드의 개수 (depth + 1 = level)
높이(height) : 루트 노드에서 가장 깊숙이 있는 노드의 깊이(depth) - 리프 노드에서 시작
스택(Stack) vs 큐(Queue)
스택(Stack) : LIFO(Last in Last out, 후입선출)의 제한적 접근(일방통행) (ex) 브라우저의 앞으로 가기 • 뒤로가기) 재귀함수와 활용도가 높음
큐(Queue) : FIFO(First in First out, 선입선출)의 1차선 터널 구조 = 대기열 while반복문과 활용도가 높음
=> 컴퓨터 장치들사이의 데이터 전송시 속도•시간차 극복하기 위해 임시 기억장치의 자료구조로 사용(이 과정을 버퍼(buffer)라고도 함)
댓글