그래프(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)로 표현될 수 있..

트리(Tree) 란? 비선형 구조는 선형구조와는 다르게 데이터가 계층적(혹은 망)으로 구성되어있습니다. 선형구조와 비선형구조의 차이점은 구성형태뿐만 아니라 용도에서도 차이점이 있습니다. 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져있습니다. 그렇다면 트리는 무엇을 표현하기 위한 자료구조일까요? 컴퓨터의 디렉토리(directiory) 구조가 트리의 대표적인 예가 될 수 있습니다. 어떠한 프로그램, 사진, 영상 등을 찾을 때 우리는 폴더에서 폴더로 들어가면서 찾곤 합니다. 이렇게 계층적인 구조를 갖는 것이 트리라 할 수 있습니다. 또 다른 예로는 조직도, 족보 등이 있습니다. 관련 용어 Root Node : 트리 구조에서 최상위에 존재하는 A와 같은 노드 No..

배열(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 = ..

큐(Queue) 란? 큐(Queue)의 사전적 의미는 무엇을 기다리는 사람, 차량 등의 줄 혹은 줄을 서서 기다리는 것을 의미하는데 이처럼 줄을 지어 순서대로 처리되는 것이 큐라는 자료구조입니다. 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO(First In First Out)의 형태를 가지며, 뜻 그대로 먼저 들어온 데이터가 가장 먼저 나가는 구조를 말합니다. Queue는 C++ 표준 라이브러리(STL, Standard Template Library)에 정의 되어 있어 필요할 때마다 만들어 사용하지 않고 include하여 사용하시면 편리합니다. Enqueue 큐 맨 뒤에 데이터 추가 Dequeue 큐 맨 앞쪽에 데이터 삭제 큐(Queue)의 특징 1. 먼저 들어간 자료가 먼..

스택(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..