그래프(Graph)란? 그래프는 정점(Vertice)과 간선(Edge)으로 구성된 비선형 데이터 구조이다. 정점(Vertice): 노드(node)라고도 하며 정점에는 데이터가 저장된다. (위의 그림에서 0, 1, 2, 3, 4, ) 간선(Edge): 노드간을 연결하는 선이며 노드간의 관계를 나타낸다. 그래프와 트리의 차이 트리는 그래프의 한 종류이다. 하지만 서로 차이점이 존재한다. 아래 그림에서 자세히 설명한다. 그래프의 구현 방법 그래프의 구현 방법에는 일반적으로 인접행렬(Adjacency Matrix), 인접목록(Adjacency List) 두 가지가 있다. 근접 행렬(Incidence Matrix), 인접리스트(Incidence List) 방식도 있지만 본 글에서는 인접행렬과 인접목록 구현 방법에..
트리(Tree)란? Tree란 선형 데이터 구조인 배열, 연결 목록, 스택 및 큐와 달리 계층적인 데이터 구조이다. 트리의 최상위 노드를 루트라고 하며 요소 바로 아래에 있는 요소를 자식이라고 한다. 아래 예시에서 d는 b의 자식이며, d는 b의 부모이다. 마지막에 자식이 없는 요소는 잎(leaf)이라고한다. tree ---- a
큐(Queue)란? Queue란 Stack과 마찬가지로 작업이 수행되는 특정 순서를 따르는 선형 구조이다. 선입선출(FIFO: First In First Out) 구조를 따른다. 스택과 큐의 차이점은 제거 방식에 있다. Stack에서는 가장 최근에 추가된 항목을 제거하지만, Queue에서는 가장 처음에 추가된 항목부터 제거한다. Queue에서는 주로 아래 네 가지 기본 작업이 수행된다. Enqueue: 큐에 항목을 추가한다. (큐가 가득 차면 Overflow condition) Dequeue: 먼저 항목이 추가된 순서대로 큐에서 항목을 제거한다. 큐가 비어 있으면 Underflow condition) Front: 큐의 첫번째 항목을 가져온다. Rear: 큐의 마지막 항목을 가져온다. 식당에서 주문 받는 ..
스택(Stack)이란? Stack은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 데이터 구조이다. 후입 선출(LIFO: Last In First Out) 구조를 따른다.( Stack의 삽입과 삭제는 같은 방향에서 일어난다.) 후입 선출이란? 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조이다. Stack에서는 주로 아래 세 가지 기본 작업이 수행된다. Push: 스택에 항목을 추가한다. (스택이 가득 차면 Overflow condition) Pop: 스택에서 항목을 제거한다. 항목은 푸시된 순서의 반대로 제거된다. (스택이 비어 있으면 Underflow condition) Peek or Top: 스택의 최상위 항목을 반환한다. 식당에 쌓여있는 접시를 예로 들면 편하다. 접시는 순서대로 쌓아두지만 ..
