그래프의 정의그래프는 연결되어 있는 원소 간 관계를 표현하는 자료구조이다.실세계의 지하철 노선도, 컴퓨터 네트워크 등의 예를 생각하면 된다.그래프의 구성 요소 그래프는 vertex(정점)과 정점들을 잇는 edge(간선)으로 구성된다.위 사진에서 0,1,2,3,4가 정점에 해당하고, 정점을 잇는 선이 간선이다. 그래프 G가 있을 때, G에 포함된 모든 정점들의 집합을 V(G), 모든 간선들의 집합을 E(G)라고 표기한다.G = (V,E)라고 쓰기도 한다. 그래프의 종류그래프는 무방향성 그래프와 방향성 그래프로 나뉜다.무방향성 그래프무방향성 그래프는 각 vertex가 서로 연결됐음만을 나타내는 그래프이다.이 때 vertex 0과 1에 대해서 (0,1)과 (1,0)는 동일한 ..

누적합 알고리즘의 정의 누적합 알고리즘은 말 그대로 어떠한 구간의 누적된 합을 구하는 알고리즘이다. 수열 \(A_n\)에 대하여 특정 인덱스 a에서 b까지의 구간 합을 구하는 알고리즘이라고도 볼 수 있다. 예시 [ 1,2,3,4,5 ] 로 이루어진 크기가 5인 배열 arr가 있다. 이 때 arr[1] 부터 arr[3]의 구간 합을 구해보자. (방법 1) 가장 쉬운 방법으로, 2부터 4까지 인덱스를 하나씩 증가시키며 배열을 방문하여 요소들을 더한다. 1 1+2 1+2+3 = 6 만일 배열의 처음부터 해당 인덱스까지의 합을 나타내는 배열 [ 1,2,6,10,15 ]을 구하려고 하면 어떨까? 1 1+2 1+2+3 1+2+3+4 1+2+3+4+5 위를 보면 알 수 있듯이, 0을 제외한 모든 인덱스에서 자신 이전..

힙의 정의 A Heap is a special Tree-based data structure in which the tree is a complete binary tree. 힙은 트리, 그 중 완전 이진 트리를 기반으로 한 자료구조이다.힙이 되기 위해서는 완전 이진 트리이면서, 부모 노드가 가진 데이터 값은 자식 노드가 가진 데이터 값보다 무조건 크거나(이 경우 Max Heap), 혹은 작아야(이 경우 Min Heap) 한다.  위 사진을 보면, Max Heap의 경우 모든 부모 노드는 자식 노드보다 데이터의 값이 크고 Min Heap의 경우 모든 부모 노드가 자식 노드보다 데이터의 값이 작은 것을 확인할 수 있다. 따라서 루트 노드에 Min Heap의 경우 항상 트리의 최솟값이, Max Meap의 경우..

이진 트리 정의트리 중, 모든 노드의 차수(degree)가 2가 넘지 않는 것을 이진트리라 한다.유한 개의 노드들의 집합으로서노드 수가 0이거나 하나의 root 노드와 왼쪽 서브트리, 오른쪽 서브트리로 구성되어 있으며, 각 서브트리는 다시 이진트리다. 이진트리 종류편향 이진 트리 (Skewed Binary Tree): 트리의 노드가 왼쪽/오른쪽 중 한 쪽으로만 치우쳐진 트리이다.포화 이진 트리 (Full Binary Tree): 트리의 깊이가 k일 때, 2^k-1 개의 노드를 가진 이진트리이다. (= 트리의 깊이까지 노드가 모두 꽉 차 있는 상태의 트리)완전 이진 트리 (Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨은 노드로 꽉 차 있으며, ..

트리의 정의사이클 없이 모든 정점이 연결되어 있는 그래프이다. (따라서 정점이 V개면 간선의 개수는 V-1개)노드(정점)와 노드를 연결하는 링크(간선)들로 구성되어 있다.보통 루트 노드가 존재하는 트리를 트리라 부르고 사용한다.Root(루트)라고 불리는 노드가 하나 존재한다.루트 노드는 0개 이상의 자식 노드를 가진다.나머지 노드들은 n(>=0)개의 서브 트리(부분집합)로 이루어져있다.트리 안에 서브 트리가 있고, 서브 트리 안에 또 서브 트리가 있는 재귀적 자료구조이다. 위 이미지에서 루트 노드는 2이며, 7과 5를 자식 노드로 가진다.각 7과 5노드를 시작으로 서브트리가 구성되어 있으며, 각 서브트리에서 7과 5는 루트 노드의 역할을 한다. 트리는 자료의 계층적 구조..

큐의 정의데이터의 삽입과 삭제가 서로 다른 곳(top,rear)에서 발생하는 선형구조이다.- 데이터 삽입 발생 위치 : rear- 데이터 삭제 발생 위치 : front 가장 먼저 들어온 데이터를 front가 참조하며 데이터 삭제 시 가장 먼저 삭제된다.이를 FIFO(First In First Out) 구조라고 한다. 큐의 연산enqueueQueue의 가장 뒤쪽(rear)에 데이터를 삽입한다.dequeueQueue의 가장 앞쪽(front)의 데이터를 삭제하고 반환한다.peekQueue의 가장 앞쪽(front)의 데이터를 반환한다.isFullQueue가 꽉 차있는지 확인한다.isEmptyQueue가 비어있는지 확인한다. 큐의 구현 큐의 구현은 스택과 마찬가지로 ..

스택의 정의데이터의 삽입과 삭제가 top이라 불리는 한쪽 끝에서만 발생하는 선형 구조이다. 가장 늦게 들어간 데이터가 가장 먼저 삭제되고, 가장 먼저 들어간 데이터가 가장 늦게 삭제된다.이를 LIFO(Last In First Out)구조 , 혹은 FILO(First In Last Out)구조라고 할 수 있다.  스택의 연산push스택의 가장 위(top)에 데이터를 삽입한다.pop스택의 가장 위(top) 데이터를 삭제한다.peek스택의 가장 위(top) 데이터를 반환한다.isEmpty스택이 비어있는지 확인한다.isFull스택이 꽉 차있는지 확인한다.getSize스택에 현재 저장된 데이터의 수를 반환한다. 스택의 구현스택을 구현하는 방법에는 두 가지 방법이 있다.배..

Big O : OBig O describes an upper bound on the time.학문적으로, Big O는 시간의 상한선을 의미한다.사람은 모두 최대 100살까지 산다고 가정하고, 이 때 사람의 나이를 x라고 하자.이 때 x따라서 사람의 나이를 Big O로는 O(N), O(N^2), O(N^3) 모두로 나타낼 수 있다.이를 다시 알고리즘 관점으로 가져오면 실제 런타임 속도는 Big O로 표현한 속도보다 작거나 같다는 것을 의미한다. Big Omega : ΩBig omega is the equivalent concept but for lower bound.학문적으로, Big Omega는 시간의 하한선을 의미한다.다시 사람의 나이 비유를 빌려오자면, Big omega로는 Ω(N..