그래프란 ?      그래프는 '정점의 모음' 과 '간선의 모음' 이 결합한 것이다.정점들이 간선을 통해 연결되면 '관계'가 형성되고 이로 인해 그래프가 만들어진다.간선으로 연결된 두 정점은 서로 '인접' 관계에 있다고 표현한다.어떤 경로가 하나의 정점을 두번 이상 거친다면 그 경로는 '사이클' 이라고 표현한다.간선에 방향성이 있다면 방향성 그래프, 없다면 무방향성 그래프가 된다.      그래프의 표현 방법   정점의 집합은 배열, 리스트 등 여러 자료구조로 표현이 가능하다. 간선의 집합은 정점 사이의 인접 관계를 나타내는 방식이다. 즉 정점과 정점의 인접 관계를 어떻게 나타내는가를 잘 고민해야 한다.간선의 집합은 크게 두 가지로 표현 한다. (인접 행렬, 인접 리스트)  인접 행렬  인접 행렬은 정점..

Heap 이란 ?  Heap은 완전 이진 트리(Complete Binary Tree)*의 형태를 가진 자료구조 이며 여러 데이터들 중 최소값 데이터 혹은 최대값 데이터를 빠르게 찾기 위해 고안한 자료구조다.  (완전 이진 트리 : 트리의 모든 레벨이 꽉 채워져 있으며 왼쪽부터 오른쪽으로 채우는 트리)    Heap의 특징   힙은 완전 이진 트리의 형태를 가진다. 부모노드의 값이 자식노드의 값보다 큰 경우 최대 힙으로 표현한다. 자식노드의 값이 부모노드의 값보가 큰 경우 최소 힙으로 표현한다. 힙을 구현할때는 배열을 이용하여 구현한다. 힙에 데이터를 삽입하거나 삭제한 후에는 꼭 HeapifyUp이나 HeapifyDown을 사용하여 힙의 속성이 깨지지 않도록 한다. 힙은 모든 언어에서 기본 라이브러리로 지..

자료구조 중 Tree는 여러 형태, 여러 종류를 가지고 있다. 각각의 Tree 별로 고유한 특징이 있으며 그 특징에 따라 데이터를 관리하거나 특정 알고리즘을 수행할 때 최적의 역할로 기능한다.   Tree의 종류     이진 트리 (Binary Tree) 모든 노드들이 둘 이하 (0,1,2)의 자식 노드를 가지는 트리 같은 수의 자식 노드를 가지고 있어도 자식 노드의 위치가 왼쪽이냐 오른쪽이냐에 따라 각각 다른 이진 트리로 구분함. 이진 트리 중에서도 많은 종류의 이진트리가 있음.  이진 탐색 트리 (Binary Search Tree) 왼쪽 자식 노드는 부모보다 작고 오른쪽 자식 노드는 부모보다 큰 이진트리 탐색 과정이 트리의 높이만큼 탐색하기 때문에 O(logN) 의 시간복잡도를 가짐. 편향트리가 되어..

Tree 란?  비선형 자료구조인 Tree는 계층적인 관계 구조를 지닌다. 여러개의 노드로 이루어지며 이들이 연결된 형태로 데이터를 구성함.   Tree의 구성 요소  구성 요소로는 루트(root) 노드, 자식(child) 노드, 부모(parent) 노드, 리프(Leaf) 노드 등이 있으며 노드의 위치와 거리는 깊이(Depth) 와 높이 (Height) 로 나타낸다.  ○  노드 (Node) 트리의 구성 요소 (Data) 모든 트리는 여러개의 노드를 바탕으로 이루어짐.   ○  간선 (Edge) 노드와 노드를 연결하는 선이다. 전체적인 트리의 구조를 형성하는 역할   ○  루트 노드 (Root Node) 트리 구조의 최상단에 위치하는 노드 트리의 시작점이고 루트 노드는 부모가 없음   ○  리프 노드 (..

자료구조란?  자료구조는 데이터를 효율적으로 저장 및 관리하기 위해 이를 보관하거나 관리하는 방식을 의미함. 많은 데이터를 효율적으로 보관하면 데이터에 접근할 때 빠르게 접근하고 처리할 수 있는데 자료구조의 형태와 유형은 알고리즘에 따라 좋은 성능을 발휘하기도 함.   자료구조의 종류   자료구조는 크게 선형구조와 비선형구조로 나뉜다.  선형 구조 (Linear Data Structure) 데이터가 순차적, 수평적으로 나열되며 한 줄로 연결되어 있음. 데이터 항목들이 연속저으로 위치하기 때문에 접근과 구현이 쉬움. 단일 레벨로 표현되기 때문에 한번의 실행으로 모든 요소를 순회할 수 있음. 데이터의 전후 관계가 1:1임.  비선형 구조 (Non - linear Data Structure)   데이터가 수직..

참고용 자료구조 별 시간 복잡도      Big O 표기법 종류별 효율 적합도  시간복잡도n124816321111111log n012345n12481732n log n0282464160n21416642561024n318645124096327682n2416256655364294967296n!(팩토리얼)1224403262092278988...26313 * 1033       사진 출처 : https://www.bigocheatsheet.com/

Single Linked List 를 구현하는 예제 클래스와 메소드 예제이다.   우선 데이터와 포인터를 담아둘 Class를 정의하고 (Node) 이 Node들을 연결해 LinkedList로 만들기 위한 메소드들이 포함된 Class도 만들어주자.  LinkedList Class에는 Node의 시작 노드를 담아둘 head를 따로 정의해주고  새로운 Node를 앞에 붙일 것인지, 뒤에 붙일 것인지에 따라 해당 기능을 구현 할 함수를 따로 만들었다.  그리고 특정 값을 가진 데이터를 삭제하는 노드, 지금까지의 노드들을 확인 할 Print 함수까지 구현하면  Single Linked List를 구현할 수 있는 기능들이 완성된다.    Node Class public class Node // 단일 노드 클래스 {..

Linked List란 ?  노드와 노드를 순서대로 나열하는 선형적 구조의 자료구조    Linked List는 - 단일 연결 리스트 (single linked list) - 이중 연결 리스트 (double linked list) - 환형 연결 리스트 (circular linked list) 로 크게 나뉘어짐.   일반적으로  노드는 리스트의 원소 값(데이터)과 다음 원소를 가리키는 정보(포인터) // 여기까지가 (single linked list) 그리고 추가적으로 이전 노드의 메모리 주소를 저장하는 정보 (포인터)로 구성되어 있음. (double linked list)  환형 연결 리스트 (circular linked list) 는  리스트의 마지막 노드가 첫번째 노드의 주소값을 가리키는 리스트의 형..