yoongrammer

목차그래프 순회 (Graph traversal) 알아보기그래프 순회(traversal)는 모든 정점을 방문하는 작업입니다. 그래프는 탐색하는 동안 동일 정점으로 다시 이동할 수 있는 싸이클이 있을 수 있습니다.동일한 정점이 다시 처리되지 않도록 하려면 처리 후 정점을 방문(Visited)했다는 표시를 하여 중복 방문을 피하도록 합니다. 대표적으로 두 가지 방법이 있습니다.깊이 우선 탐색 (DFS: Depth First Search)너비 우선 탐색 (BFS: Breath First Search)깊이 우선 탐색 (DFS: Depth First Search)깊이 우선 탐색 (DFS: Depth First Search)은 그래프에서 최단 경로를 찾는 간선 기반 알고리즘입니다.DFS는 형제 정점을 탐색하기 전에 ..

목차그래프 표현 및 구현그래프는 일반적으로 두 가지 방식으로 표현합니다.인접 행렬 (adjacency matrix)인접 리스트 (adjacency list)인접 행렬(adjacency matrix)인접 행렬은 그래프를 2차원 배열에 저장하는 방법입니다. 부속된 간선을 찾는 것은 빠르지만 |V| x |V| 만큼의 공간이 필요하여 저장 측면에서 비효율적입니다. (|V| : 정점 수)노드 수보다 간선 수가 많은 dense graph이거나 빠르게 부속(incident)된 간선을 찾을 때 주로 사용합니다.각 행과 열은 정점을 나타냅니다.1. 방향성 그래프 (Directed Graph)방향성 그래프를 인접행렬로 표현하면 다음과 같습니다.각 정점이 인접하다면 1을 저장하고 그렇지 않다면 0을 저장합니다.2. 무방향성..

목차그래프 (Graph) 알아보기그래프(Graph)는 정점(Vertex)의 집합 V와 간선(Edge)의 집합 E로 구성된 비선형 데이터 구조입니다.정점(Vertex) : 자료를 저장하려는 자료의 단위, 노드(Node)라고도 말함.간선(Edge) : 정점 사이를 연결하는 선으로 두 정점 쌍 (u, v)로 표현함.그래프(G)는 정점들의 집합 V와 간선들의 집합 E를 사용하여 (V, E)로 나타냅니다.G = (V , E)V = {1, 2, 3, 4, 5}E = {(1,2), (1,5), (2,3), (2,4), (2,5), (3,4), (4,5)}그래프 용어Directed edge & Undirected edge방향성(유향) 간선 (Directed edge)방향을 가진 정점의 쌍 (u, v)으로 화살표로 표현..

목차해시 테이블 (Hash Table) 알아보기해시 테이블(hash table)에 대해 알아보기 전에 Direct address table에 대해 알아보도록 하겠습니다.Direct Address TableDirect address table은 키 값을 배열의 인덱스로 환산해서 데이터에 접근하는 자료구조입니다. Direct address table은 키 k가 테이블 slot T[k]에 저장되기 때문에 테이블의 크기는 전체 키(U) 개수가 됩니다.위 특징 때문에 direct address table은 중복 키가 없고, 테이블의 크기가 작은 경우에 사용할 수 있습니다. 구현 방법전체 키 집합(U = {0,1 ... ,9})의 크기만 한 테이블(T)을 배열로 만듭니다.실제 사용하는 키 집합(K = {2,3,5,..

목차우선순위 큐 (Priority Queue) 개념 및 구현일반적인 큐(Queue)는 먼저 집어넣은 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장하는 선형 자료구조입니다.하지만 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말합니다. 우선순위 큐는 다음과 같은 속성을 가지고 있습니다.모든 항목에는 우선순위가 있습니다.우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 queue에서 제외됩니다.두 요소의 우선 순위가 같으면 queue의 순서에 따라 제공됩니다.4 → 8 → 2 순으로 데이터가 들어간다고 했을 때 큐와 우선순위 큐의 처리 순서는 다음과 같습니다.(여기서 높은 값이 높은 우선순위를 갖는다고 가..

목차힙 (Heap) or 이진 힙(binary heap) 알아보기힙(heap)은 이진 힙(binary heap)이라고도 하며, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조입니다. 힙은 다음과 같은 속성을 가지고 있습니다.완전 이진트리(Complete Binary Tree) 이다.부모노드의 키값과 자식노드의 키값 사이에는 대소관계가 성립한다.키값 대소관계는 오로지 부모자식 간에만 성립되며 형제사이에는 대소관계가 정해지지 않음.힙의 종류힙에는 두가지 종류(최대 힙, 최소 힙)가 있습니다. 1. 최대 힙 (Max Heap)부모 키값이 자식노드 키값보다 큰 힙Key(parent) ≥ Key(child)가장 큰 값이 루트..

목차시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity)알고리즘을 평가할 때 시간 복잡도와 공간 복잡도를 사용합니다.시간 복잡도: 알고리즘의 수행시간을 평가공간 복잡도: 알고리즘 수행에 필요한 메모리 양을 평가시간 복잡도와 공간 복잡도는 주로 점근적 표기법 중 빅오 표기법을 이용하여 나타냅니다.이유는 최악의 경우에도 해당 알고리즘이 어떤 성능을 낼지 가늠해볼 수 있기 때문입니다.시간 복잡도(Time Complexity)알고리즘의 수행 시간을 분석할 때 시간 복잡도를 사용합니다.수행 시간은 실행환경에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행 시간을 평가합니다. 기본 연산은 다음과 같습니다.데이터 입출력 - copy, move...산술 연산 - add,..

목차점근 표기법 (asymptotic notation) 알아보기점근 표기법(asymptotic notation)을 이해하고 대표적인 세 가지 유형의 점근 표기법인 빅오 표기법(Big-O notation), 빅 오메가 표기법(Big-Omega notation) , 빅 세타 표기법(Big-Theta notation)에 대해 알아보도록 하겠습니다.점근 표기법 (asymptotic notation) 컴퓨터 알고리즘의 실행시간은 실행환경에 따라 다르게 측정됩니다. ex) 하드웨어, 운영체제, 언어 등 실행환경을 동일하게 하는 것은 어렵기 때문에 기본 연산(산술 연산, 제어 연산 등)의 실행 횟수로 성능을 분석합니다.연산의 실행 횟수는 입력 크기 n에 대한 함수로 표현합니다. ex) \(f(n) = n^2+3n+1..

목차보간 탐색 (Interpolation Search) 개념 및 구현보간 탐색 (Interpolation Search)은 정렬된 리스트에서 범위를 줄여가며 검색하는 알고리즘입니다. 보간 검색은 전화부에서 이름 (책의 항목이 정렬되는 키 값)을 검색하는 방법과 유사합니다.  동작 방식은 이진 탐색과 비슷하지만 탐색 위치를 정하는 방식이 다릅니다. 이진 탐색과 보간 탐색의 탐색 위치를 결정하는 공식은 다음과 같습니다.arr [] : 데이터가 들어있는 배열low : arr [] 배열에 시작 indexhigh : arr[] 배열에 마지막 indexx : 검색 값pos : 탐색 위치 index이진 탐색\( pos = (low + high) / 2 \) 보간 탐색\( pos = low + (x - arr [low]..

목차점프 탐색(Jump search) 개념 및 구현Jump search는 순차적으로 탐색하는 선형 탐색과 달리 블록 단위로 이동(점프)하면서 탐색하는 알고리즘입니다.정렬된 배열에서만 사용할 수 있고, 한 칸씩 이동하는 것이 아니기 때문에 선형 탐색보다 적은 요소를 탐색하게 됩니다. 이 알고리즘은 선형 탐색보다 빠르지만 이진 탐색보다는 느립니다.동작 방식배열을 블록단위로 나누기 위해 블록 사이즈 m을 구합니다.m의 최적 값은 다음과 같습니다. 여기서 n은 요소의 수입니다.m = √n한 블록에서 값을 탐색하고 없으면 다음 블록으로 이동합니다.값을 가진 블록을 찾으면 선형 탐색을 사용하여 정확한 인덱스를 찾습니다.블록 최적 사이즈 구하는 과정m에 최적 값을 구하는 공식은 다음과 같습니다.블록 크기가 m이고 n..