ComputerVision Jack

그래프 이해와 종류 그래프(Graph) 그래프는 정점과 간선의 집합이다. 정점(vertext)은 연결의 대상이되는 개체 또는 위치를 의미한다. 간선(edge)은 정점 사이의 연결을 의미한다. 무방향 그래프(undirected graph) 연결 관계에 있어서 방향성이 없는 그래프 방향 그래프(directed graph) 간선에 방향 정보가 포함된 그래프 = 다이 그래프(digraph) 이러한 무방향 그래프와 방향 그래프는 간선의 연결 형태에 따라서 완전그래프(complete graph)로 구분된다. 완전 그래프란 각각의 정점에서 다른 모든 정점을 연결한 그래프를 뜻한다. 때문에 정점의 수가 동일한 완전 그래프라 하더라도, 방향 그래프의 간선의 수는 무방향 그래프의 간선의 수에 두배가 된다. 가중치 그래프(..

테이블(Table)과 해쉬(Hash) 테이블(Table) 우리가 흔히 사용하는 표가 테이블이다. 하지만 자료구조의 관점에서 테이블에 저장되는 데이터는 키(key)와 값(value)가 하나의 쌍을 이룬다. 따라서 키(key)가 존재하지 않는 값은 저장할 수 없고 모든 키는 중복되지 않는다. 이러한 테이블은 서전 구조 또는 맵(map)이라고 불린다. 예제 : 배열 기반의 테이블 구현하기 키를 인덱스 값으로 하여 그 위치에 데이터를 저장한다. 하지만 키의 값의 범위가 크다면 문제가 발생한다. 배열 기반 테이블 문제점 키의 범위(고유 인덱스)가 배열의 인데그 값으로 사용하기에 적당하지 않다. 키의 범위를 수용할 수 있는 매우 큰 배열이 필요하다. 예제 : 해쉬 함수를 이용한 테이블 구현하기 해쉬 함수(Hash ..

탐색의 이해2 이진 트리의 단점 저장 순서에 따라 탬색의 성능에 큰 차이를 보인다. 따라서 이러한 단점을 해결한 트리를 가리켜 '균형 잡힌 이진트리'라고 한다. AVL 트리 2 - 3 트리 2 - 3 - 4 트리 Red - Black 트리 B 트리 AVL 트리 (AVL Tree) AVL 트리는 G.M.Adelson-Velskii와 E.M.Landis에 의해 고안되었다. AVL트리는 토드가 추가될 때, 그리고 삭제될 때 트리의 균형 상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는다. 균형 인수(Balance Factor) AVL 트리가 균형을 잡기 위해 지표로 사용하는 것 균형 인수 = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이 AVL 트리는 균형 인수의 절대값이 2 이상인 경우에 균형을 잡기 위..

탐색의 이해 탐색(Search) 탐색은 알고리즘보다 자료구조에 더 가깝게 연관되어 있다. 어떻게 탐색해야할지 생각하기 보다 효율적인 탐색을 위한 저장 방법을 고려해야한다. 또한 효율적인 탐색이 가능한 대표적인 저장 방법은 트리이다. 보간 탐색(Interpolation Search) 보간 탐색은 이진 탐색의 비효율 성을 개선한 알고리즘이다. 이진 탐색은 무조건 탐색 위치의 중간을 찾아 간다면, 보간 탐색은 비율을 통하여 그 값을 찾아간다. Index = target - arr[left] / (arr[right] - arr[left]) * (right - left) + left #여기서 left는 가장 왼쪽 인덱스 right는 가장 오른쪽 인덱스를 지칭한다. 탐색 Item에 대한 구조체 정의 탐색 키 (Se..

정렬(Sorting) 버블 정렬(Bubble Sort) 인접한 두 개의 데이터를 비교해 가면서 정렬을 진행하는 방식 두 데이터를 비교하여 정렬 순서상 위치가 바뀌어야 하는 경우에 두 데이터의 위치를 바꿔 간다. 두개의 세트로 움직인다고 생각하면 편하다. 예제 : 버블 정렬 구현하기 이중 for문을 이용하여 구현한다. i는 단순히 마지막 원소를 밀어 넣는 개념이고 j는 이동하며 두개의 세트로 바꿔 나간다. 버블 정렬(Bubble sort) 성능 평가 비교의 횟수 : 두 데이터간의 비교 연산의 횟수 이동의 횟수 : 위치의 변경을 위한 데이터의 이동 횟수 빅오를 결정하는 기준은 비교의 횟수이다. 빅오 연산을 적용하면 O(n^2) 이다 선택 정렬(Selection Sort) 선택 정렬은 정렬 순서에 맞게 하나씩..

우선 순위 큐 우선 순위 큐(Queue) 우선 순위 큐의 연산 결과는 들어간 순서에 상관 없이 우선 순위가 높은 데이터가 먼저 나오는 것이다. enqueue : 우선 순위 큐에 데이터를 삽입하는 행위 dequeue : 우선 순위 큐에서 데이터를 꺼내는 행위 우선 순위 큐 구현 방법 배열을 기반으로 구현하는 방법 연결 리스트를 기반으로 구현하는 방법 힙(heap)을 이용하는 방법 하지만 배열과 연결 리스트로 구현할 경우 삽입 위치를 찾기위해 처음부터 마지막 까지 자료를 모두 비교 해야하는 단점이 존재한다. 따라서 힙을 이용하여 구현한다. 힙(heap) 소개 힙은 이진트리이며 완전 이진 트리이다. 그리고 모든 저장된 값은 자식 노드보다 크다. 따라서 최 상단 루트 노드는 가장 큰 값을 갖는다. 예제 : 힙 ..

트리(Tree) 트리 계층적인 관계(Hierarchical Relationship)을 표현하는 자료구조 노드(Node) : 트리의 구성 요서에 해당하는 A, B, C, D...같은 요소 간선(Edge) : 노드와 노드를 연결하는 연결선 루트 노드(root Node) : 트리 구조에서 최 상위에 존재하는 A와 같은 노드 단말 노드(terminal Node) : 아래로 다른 노드가 연결 되어 있지 않은 H, I, J, E, F, G 노드 내부 노드(internal Node) : 단말 노드를 제외한 모든 노드 이진트리(Binary tree)와 서브 트리(Sub tree) 서브 트리 큰 트리에 속한 작은 트리를 지칭한다. 이진 트리 루트 노드를 중심으로 두 개의 서브 트리로 나누어진다. 나뉘어진 두 서브 트리도..

큐(Queue) 큐 큐는 선입선출 자료구조의 일종이다. 영어로 FIFO(First - In - First - Out) 구조의 자료구조이다. 큐의 ADT정의 Enqueue : 큐에서 데이터를 넣는 연산 Dequeue : 큐에서 데이터를 꺼내는 연산 예제 : 배열로 큐 구현(queue) 큐의 과정에서 머리(앞 부분)을 참조하여 dequeue 연산을 진행하고 꼬리(뒷 부분)을 참조하여 enqueue연산을 진행한다. 또한 기본적인 큐 구현에 있어서 front포인터와 rear포인터를 사용하여 구현하고, 자료 이동 없이 편리하게 사용하기 위해 원형 큐 (circular queue)를 사용한다. 원형 큐가 텅 빈 상태 : F와 R이 동일한 위치 원형 큐가 꽉 찬 상태 : R이 가리키는 위치의 앞을 F가 가리킨다. 예..