그래프(Graph) 란? 그래프란 비선형(non-linear) 자료구조이며, 노드(Node)와 엣지(Edge)로 구성되어있다. 노드(Node) : 노드는 꼭짓점(vertex)로 표현됩니다. 엣지(Edge) : 엣지는 두 노드를 연결하는 선(line)으로 표현됩니다. 위 그래프를 V(vertex) = {0, 1, 2, 3, 4}, E(edges) = {01, 12, 23, 34, 04, 14, 13}으로 표현할 수 있습니다. 그래프는 많은 일상 생활의 문제점을 해결하기 위해 사용됩니다. (네트워크의 표현 등) 그래프의 표현 그래프를 인접 행렬(Adjacency Matrix) 또는 인접 리스트(Adjacency List)로 표현 할 수 있습니다. 인접 행렬 인접행렬은 2차원 배열(v x v)로 표현될 수 있..

배열(Array)이란? 배열은 거의 모든 프로그래밍 언어에서 기본적으로 제공되는 자료형으로 많은 고급 자료구조들에서 사용된다. 배열은 주로 여러 개의 동일한 자료형의 데이터를 한꺼번에 만들 때 사용된다. 배열의 가장 기본적인 특징은 '인덱스, 요소' 쌍의 집합이라는 것이다. 즉, 인덱스가 주어지면 해당하는 요소가 대응되는 자료구조이다. 배열에서는 모든 요소가 동일한 자료형이며 인덱스를 사용하여 직접 접근 할 수 있다. 배열의 추상 자료형 (객체) '인덱스, 요소' 쌍의 집합 (연산) create(n) : n개의 요소를 가진 배열을 생성한다. retrieve(i) : 배열의 i번째 요소를 반환한다. store(i, item) : 배열의 i번째 위치에 item을 저장한다. 배열과 메모리 함수의 파라미터로서의..

연결리스트(Linked List) 란? 1. 연결리스트는 동적으로 크기를 조절(동적할당)하므로 배열을 사용하는것 보다 메모리를 효율적으로 사용 할 수 있다. 2. 일반적으로 배열이나 배열 큐, 스택을 사용할때, 배열 중간에 데이터를 삽입하기 위해서는 처음이나 끝에서 차례차례 이동시켜야하기 때문에 불필요한 연산을 많이 하게된다. 이 때 이러한 Sequential 표현에서 데이터 이동의 문제점을 해결할 수 있는 방법이 바로 연결리스트이다. 단순 연결 리스트에서는 데이터를 가지고 있는 공간인 Node와 그 다음 주소를 저장하는 공간인 next Node로 구성되어있고, Node의 마지막 데이터 공간의 nest Node에는 Null 값이 들어간다. Node = 데이터 값을 가지고 있는 공간 next Node = ..

스택(Stack) 이란? 1. 가장 늦게 들어간게 먼저 나가는 방식. 2. 가장 늦게 들어간 자료가 가장 먼저 나가는 구조를 후입선출(LIFO, Last In First Out)이라고도 부른다. 3. 스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있다. 4. 스택의 가장 위를 top이라고 하고, 삽입과 삭제가 top에서 일어난다. 스택은 그래프의 자료구조의 탐색방법중 DFS(Depth First Search) 깊이우선 탐색에 사용됩니다. 스택은 자료가 들어가는곳과 나가는곳이 동일하기 때문에 하나의 포인터(top)로 자료 관리가 가능하다. 구현 코드 (C++) #include #define MAXVALUE 2 using namespace std; template class Stack { public: int t..