KKanging

최소신장 트리(MST: Minimum Spanning Tree)란 그래프의 정점이 다 포함되어있는 트리( 신장 트리 (spanning tree)) 가중치 그래프가 주어질 경우 간선들의 비용 합이 최소가 되는 신장 트리 cycle이 발생하면 안됨 그래프란 → 노드(정점 vertex)와 그 노드를 연결하는 간선을(edge) 하나로 모아놓은 자료구조 무방향 그래프: 간선이 방향이 없는 그래프 방향 크래프: 간선의 방향이 있는 그래프 그래프의 표현 방법 인접 행렬 인접 리스트 인접행렬 가중치 그래프란 그래프의 간선에 가중치(weight)를 부여한 것 트리란 → 그래프의 한 종류 → Cycle이 불가능 (그래프에서 사이클(Cycle)이란 어떤 특정 정점에서 출발하여 간선과 정점들을 지 나 다시 처음에 출발했던 특..

*** AVL트리는 이진탐색트리의 종류입니다. 이진탐색트리의 개념을 모른다면 보는 것을 추천합니다 https://kkangmg.tistory.com/15 1. AVL 트리 이진 탐색 트리의 단점 이진 탐색 트리는 평균 복잡도가 O(logn)으로 효율적인 트리이다. 하지만 트리의 균형(balance)이 깨지면 O(n)으로 비효율적인 트리가 된다. 비효율적인 이진 탐색 트리 AVL 트리란 발명자인 Adelson-Velsky and Landis 에서 따온 이름 이진 탐색 트리의 종류 자가 균형 이진 탐색 트리이다. 이진탐색트리의 단점을 보완하여 트리의 균형을 유지한다. 검색, 삽입 , 삭제 연산에서 평균과 최악 둘 다 O(logn)의 시간 복잡도를 가진다. 원리 트리의 높이를 통해 균형도(Balance Fac..

그래프란 정점끼리의 연결을 나타내는 자료구조이다. 정점과 간선으로 이루어져 있다. 정점(vertex): data를 표현하는 단위(node) 간선(edge): data 끼리의 연결을 나타내는 선 vertex는 총 6개이고 edge는 총 8개의 간선이 있다. 그래프와 트리의 차이점 트리와 그래프 둘 다 정점끼리의 연결구조를 가지고 있다. 하지만 cycle의 유무에 따라 그리고 계층적인 구조를 가지냐에 따라 나뉜다. 그래프(graph) cycle을 가짐 계층 구조를 가지지 않음 → 오로지 정점끼리의 연결만 나타낸다. 트리(tree) cycle을 가지지 않음 계층 구조를 가지고 있음 → root로부터 다른 정점들이 계층적임 cycle이란 if vertex의 집합을 {v1,v2,v3,v4,v5,v6}가 있다면 특..

이진 탐색트리(Binary Search Tree) 이진 탐색트리는 이진 트리의 종류로 부모노드의 오른쪽자식은 자신보다 크고 왼쪽자식은 자신보다 작다 연결리스트로 표현한다. 이진 탐색트리 연산 삭제 삽입 삭제 이진 탐색트리의 탐색 만약 15라는 수를 찾는다면 root node 부터 탐색한다. 비교하는 수와 현재 노드의 수를 비교해 크면 오른쪽 작으면 왼쪽에서 찾는다. 15는 10보다 크므로 오른쪽으로 간다. 15는 20보다 작으므로 왼쪽으로 간다. 15를 찾았으므로 true 반환 만약 못찾으면 null을 만나므로 false 반환 이진 탐색트리의 삽입 삽입은 무조건 맨아래 노드에 삽입한다 어디에 삽입할지는 이진 탐색을 통해 이루어진다 위 예시에서 13을 삽입하고 싶으면 우선 13이 어디에 삽입 해야하는지 탐..

이진트리 많아야 두 개의 자식 노드를 가짐 왼쪽 자식과 오른쪽 자식으로 구분 완전이진트리처럼 트리의 균형이 유지가 되지 않음 균형이 없는 트리이기 때문에 연결리스트로 표현하는 게 적합 root node로부터 이진트리를 표현한다. 연결리스트로 표현 돼서 배열처럼 트리의 원소를 찾기 힘들다. 그래서 이진트리는 순회 알고리즘을 이용해서 노드의 수나 정점을 찾는다. 이진트리의 순회 방법 전위 (VLR) 중위 (LVR) 후위 (LRV) 기준은 visit을 기준으로 전위 중위 후위를 나눈다 전위(Preorder traversal) root node부터 시작한다. Visit 하고 왼쪽(left)으로 가고(visit)한다. 왼쪽이 없으면 오른쪽으로 간다.(Right) 위 순서대로 방문한다. 중위(Inorder trav..

힙이란 완전이진 트리로 구성되었다. 트리의 구성이 균형을 이룬다 부모노드와 자식 노드 관계에 특징을 이룬다. 힙의 종류 최대 힙 트리 (Max heap) 완전이진트리로 구성 부모 노드의 키 값은 자식 노드의 키 값보다 크거나 같음 왼쪽 오른쪽 자식의 크기 구분 없음 최소 힙 트리(Min heap) 완전 이진트리로 구성된 트리 부모 노드의 키 값은 자식 노드의 키 값보다 작거나 같음 왼쪽 오른쪽 자식의 크기 구분 없음 힙의 응용 우선 순위 큐, 프린터 스풀러 등등 힙 정렬: 최대 힙 (내림 차순 정렬) , 최소 힙 ( 오름차순 정렬) 최대 힙 구조 이 글에서는 최대 힙의 예시와 구현만 하였습니다. 최대 힙의 예 배열 표 삽입 연산 그리고 heapify 연산을 한다 heapify 연산이란 ? 위 그림과 같이..

완전 이진트리란? 완전 이진트리 자식 노드가 왼쪽부터 순서적으로 채워진 이진트리 높이가 균형을 유지 완전 이진트리 표현 배열로 표현한다. 이유는 완전이진트리의 속성인 균형이 유지되기 때문 완전 이진트리 자료구조 0부터 시작해도 되지만 노드의 인덱싱의 조금 더 가시성이 좋기 때문에 1부터 시작해도 된다. 1부터 시작할 경우 배열 인덱스 i의 부모노드: i/2의 바닥함수(내림) 노드 배열 인덱스 i의 왼쪽 자식: 2i의 노드 배열 인덱스 i의 오른쪽 자식: 2i + 1의 노드 완전 이진트리의 레벨 i에서 노드의 수는 2^(i-1)개 완전이진트리의 높이가 h일 경우 최대 노드의 수는 2^h -1개 완전 이진트리에서 노드의 수 n일 경우 트리의 높이는 O(logn) 완전이진트리를 사용한 알고리즘의 수행시간은 트..

트리란 트리는 계층적인 구조를 표현할 때 사용할 수 있는 자료구조 cycle을 가지지 않는 그래프 트리 관련 용어 노드(node) : 트리 자료구조에서 data의 단위 간선(edge): 트리나 그래프에서 정점이나 노드끼리 연결되어 있는 선 루트 노드(root node): 부모가 없는 최상위 노드 단말 노드 or 말단 노드(leaf node): 자식이 없는 노드 크기(size): 트리에 포함된 모든 노드의 개수 깊이(depth): 루트 노드로부터의 거리 높이(height): 깊이 중 최댓값 차수(degree): 각 노드의 (자식 방향) 간선 개수 이런 형태도 트리일까? 이 형태는 cycle이 발생하기 때문에 트리가 아니다. 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1 이유는 cycle이 ..

덱(Deque, Double-Ended Queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조를 말합니다. 이 이름은 Double-Ended Queue에서 나왔습니다. 스택과 큐의 일반적인 특성을 모두 가지고 있어서 스택처럼 LIFO(Last In First Out) 구조, 큐처럼 FIFO(First In First Out) 구조로 사용할 수 있습니다. 덱이란? 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조를 말함 스택과 큐의 일반적인 특성을 모두 가지고 있음 덱이란 앞쪽 뒤쪽 모두 삽입 삭제가 많이 이루어지는 작업에 적합 인덱스 조회 후 삽입 삭제에는 불리함 덱의 구현 원형 배열 연결 리스트 이 글에선 원형 배열로만 구현하겠습니다. 덱의 자료구조 설계 add_front: 덱의 앞쪽에 요소를 추..

queue란 자료구조에 대해 알아보겠습니다. 큐(Queue)는 스택과 마찬가지로 컴퓨터 과학에서 핵심적인 개념입니다. 어떤 표를 사기 위해 줄서는 걸 생각해보면 이해하기 쉽습니다. 줄 서는 것과 같이 먼저 들어간 항목이 먼저 나오는 (First In First Out) 원칙을 따르는 자료구조입니다. 큐란? 데이터의 삽입과 삭제가 서로 다른 위치에서 일어나는 자료구조 FIFO: First-In-First-Out 큐의 응용 은행 대기, 식당 대기, 항공기 이착륙 다양한 분야의 시뮬레이션 등 큐 구현 방법 단순 배열 원형 배열 연결리스트 이 글에선 원형 배열 큐만 다룹니다. 배열 큐의 자료구조 설계 삽입(enqueue) , 삭제(dequeue) isFull(가득 찼는지 검사) isEmpty(비었는지 검사) 자..