CS/자료구조 (5) 썸네일형 리스트형 그래프(Grape) - 그래프 G는 집합 V와 정점 사이의 관계를 나타내는 연결선의 집합 E로 구성된다. 여기서 그래프의 두 집합 정점과 간선은 유한하다고 가정하며, G = (V, E)로 표기한다. - 정점(Vertex) V는 공집합이 아닌 정점들의 유한 집합이다. - 간선(Edge) E는 공집합도 허용하는 간선들의 유한 집합이다.(정점들의 쌍으로 표현) - 정점의 차수는 그 정점에 부수(incident)된 간선들의 수이다. - 위상순서, 최단경로, 작업 네트워크 등에 이용한다. - 임의의 유한집합 S에 대한 이항관계(Binary Relation)는 무방향 그래프 혹은 방향 그래프로 나타낼 수 있다. - 그래프를 인접행렬로 표현했을 때 무방향 그래프는 반드시 대칭인 반면, 방향 그래프에서는 대칭이 아닐 수도 있다. 무방향 .. 트리(Tree) - 비선형구조로서, 정점(Vertex)과 선분(Arc)으로 이루어진 그래프의 특수한 경우이다. - 트리는 어떠한 두 정점 사이에도 사이클(Cycle)이 존재하지 않는 연결그래프로써 임의의 두 노드 사이의 경로는 오직 하나만 존재한다. - 트리의 알고리즘은 순환적(Recursive)이며, 트리 T에서 임의의 한 Edge를 제거하면 트리 T는 더 이상 연결되지 못한다. 특징 - 트리의 루트를 제거하면 Forest(사이클은 없지만 연결되지 않은 무방향 그래프)가 된다. - 루트가 아닌 노드의 부모 노드는 유일하게 결정된다. 즉, 트리에서 루트를 제외한 나머지 모든 노드들은 선행자가 하나만 존재한다. - 트리 구조에서 간선 수 e와 노드 수 n의 관계는 항상 e = n+1이다. - 이진트리에서는 서브트리를 왼쪽.. 큐(Queue) - 입출력이 서로 반대쪽으로 이루어지는 제한구조이다. 즉, 자료는 입력된 순서대로 출력되는 선입선출(FIFO) 방식이다. - 한쪽 끝에서 삽입이 일어나고 반대쪽으로 끝에서 삭제가 일어나는 선형 리스트이다. - 큐의 각 항목들을 동일한 데이터 형태이다. 특징 - 임의의 우선순위를 가진 원소를 우선순위 큐에 언제든지 삽입할 수 있고, 우선순위가 가장 높은(또는 가장 낮은) 원소를 먼저 삭제한다. 이러한 두 연산을 지원하는 자료 구조를 최대(최소) 우선순위 큐라고 하며 구현 방법으로는 최대(최소) heap을 사용한다. - 큐는 스택과 마찬가지로 배열이나 연결리스트로 구현이 가능하다. 응용 - 작업스케줄링, 전철역에서 개찰구를 통과 - 버퍼, 스풀, Radix 정렬시 버킷으로 이용 - 그래프 너비 우선 탐색(B.. 스택(Stack) - 마지막에 입력된 자료가 가장 먼저 출력되는 LIFO 방식으로 작동한다. - top이라는 인덱스 위치를 통해 삽입(push)과 삭제(pop)가 이루어지며, 초기상태의 top은 0또는 –1이 된다. - Top의 최대 크기는 스택의 크기에 의해 결정된다. - 저장장치에 물리적으로 어떻게 표현되느냐가 스택을 특징짓는 것이 아니라 스택이라는 논리적 구조의 동작이 스택의 특징을 결정한다. 응용분야 - 서브루틴 호출시 복귀 주소(return address) 저장 - 순환 프로그램(Recursive Program) 수행 시 - 인터럽트 발생 시 상태 저장 - 후위식(Postfix) 변환 - 버퍼 - 트리 운행 시(inorder, postorder, outorder) - 그래프에서 깊이 우선 탐색(DFS) - 퀵 정.. 연결 리스트란 정의 - 배열 구조의 문제점인 삽입과 삭제의 어려움을 해결하기 위해 고안한 자료구조로, 삽입과 삭제 빈번한 작업과 적합하다. - 노드(Node)를 크게 데이터 필드와 링크 필드로 나누어 다음 노드가 기억된 공간의 주소를 이전 노드의 링크 필드에 기억시키는 방식으로 모든 노드들을 하나의 리스트로 연결한다. - 논리적 데이터 순서와 물리적 데이터 순서가 동일하지 않으므로 후속 데이터 액세스를 위해서는 포인터가 필요하다. 즉, 노드들은 논리적으로는 순차적으로, 물리적으로는 비순차적으로 저장된다. 단순 연결 리스트 - 임의의 문자를 접근하기 위해서는 처음부터 순차 탐색을 해야만 한다. 그러므로 임의의 원소의 값을 수정하는 연산이 일어날 경우 탐색 시간이 많이 필요하다. 원형 연결 리스트 - 단순 연결 리스트의 .. 이전 1 다음
