W 개발 일지

AVL 트리 (Adelson-Velskii & Landis Tree) : 대표적인 균형 이진 탐색 트리 각 노드에서 왼쪽 서브 트리의 높이(hL : height of left subtree)와 오른쪽 서브 트리의 높이(hR : height of right subtree)의 차이가 1 이하인 트리 특징 - 왼쪽 서브 트리 < 부모 노드 < 오른쪽 서브 트리의 크기 관계를 갖음 *이진 탐색 트리의 특징 - 각 노드의 왼쪽 서브 트리 높이와 오른쪽 서브 트리 높이의 차이 (hL - hR)를 노드의 균형 인수(BF, balance factor)라고 함 - 각 노드의 균형 인수로 {-1, 0, +1} 값만 가지게 함으로써 균형을 유지함 루트 노드 50을 기준으로 왼쪽 서브 트리의 높이는 2, 오른쪽 서브 트리의 ..

Union-Find 알고리즘 : 정점으로 구성된 집합을 관리하는 방법으로 집합의 합병과 요소가 어떤 부분집합에 속하는가를 판정하는 두 가지 연산. find 연산으로 특정 원소들을 집합 안에 있는지 없는지 판별하고, 없다면 두 원소들이 속한 트리들을 합병한다. Union = 2개의 원소로 이루어진 집합을 합치는 연산. = 합집합 Find = 특정 원소가 속한 집합을 찾아주는 연산. 총 세 가지 방법이 있다. 첫번째 방법 : 부모 노드 활용 Find 연산 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 //자기 자신을 가지는 노드로 초기화. void initgroup() { for(i=0;i 1 -> 2 -> 3 -> 5 -> 10 -> 13 Find 연산 연결리스트의 검색 연산으로 찾으려는..

트리는 사이클이 없는 연결 그래프 그래프에 대한 설명글은 👇🏻 https://tildacoderecorder.tistory.com/107 [ 자료 구조 ] 그래프의 개념과 구조 그래프 : 연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조 ( 트리는 1:N 관계 표현 ) 그래프 G = 객체를 나타내는 정점(Vertex)과 객체를 연결하는 간선(Edge)의 집합. G = (V, E) 그래프의 종 tildacoderecorder.tistory.com 신장 트리 : n개의 정점으로 이루어진 무방향 그래프G에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리 깊이 우선 신장 트리 : 깊이 우선 탐색을 이용해 생성된 신장 트리 너비 우선 신장 트리 : 너비 우선 탐색을 이용해 생성된 신장 트리 최소 ..

Heap : 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나키 값이 가장 작은 노드를 찾기 위해 만들어진 자료 구조 최대 히프 max heap : 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리, 부모 노드의 키 값 >= 자식 노드의 키 값, 루트 노드 : 키 값이 가장 큰 노드 최소 히프 min heap : 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리, 부모 노드의 키 값 heap_size = 0; return h; } Colored by Color Scripter cs 구조체 heapType에 크기가 100인 1차원 배열 heap와 히프의 원소 갯수를 나타내는 heap_size를 선언한다. 공백 히프 h를 생성하고 공백이기 때문에 heap_size에 0을 넣어준다. 최대 H..

https://tildacoderecorder.tistory.com/104 이진 트리에 대한 개념 설명은 아래 글 참조 👇🏻 [ 자료구조 ] 트리와 이진트리의 개념과 구조 - C언어 트리 : 원소들 간에 1:n 관계를 가지는 비선형 자료구조, 원소들 간에 계층 관계를 가지는 계층형 자료구조, 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무) 모양의 구조 트리는 하나 tildacoderecorder.tistory.com 이진 탐색 트리 Binary search Tree : 이진 트리를 탐색용 자료구조로 사용하기 위해 원소 크기에 따라 노드 위치를 정한 것 모든 원소는 서로 다른 유일한 키를 갖는다. 왼쪽 서브 트리에 있는 원소들의 키는 그 루트의 키보다 작다. 오른쪽 서브 트리에 있는 원소들의 키..

트리 Tree 트리 : 원소들 간에 1:n 관계를 가지는 비선형 자료구조, 원소들 간에 계층 관계를 가지는 계층형 자료구조, 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무) 모양의 구조 트리는 하나의 루트 노드를 가지며 각 자식 노드와 부모 노드는 간선(edge)로 연결되어 있다. 트리의 이해 차수 노드의 차수 : 노드에 연결된 자식 노드의 수. ex ) 위 노드를 예로 들어 F의 차수는 2, G의 차수는 1, H의 차수는 0 트리의 차수 : 트리에 있는 노드의 차수 중 가장 큰 값 ex ) 위 트리의 차수는 2 단말 노드 : 차수가 0인 노드. 자식 노드가 없는 노드. ex ) 위 노드에서는 A, C, E, H가 해당 높이 노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨 ex..

연결 큐 1차원 배열을 이용하기 때문에 크기가 정해져 있는 원형 큐의 문제점을 보완해 나온 것이 연결 리스트를 이용한 연결 큐. 원형 큐에 대한 설명은 아래 글로 👇🏻 https://tildacoderecorder.tistory.com/102 [ 자료구조 ] enQueue()와 deQueue() 함수를 이용한 원형큐 큐의 개념과 구조 큐 : 스택과 다르게 "선입선출"의 구조를 가지고 있다. 먼저 들어간 것이 먼저 나오는 구조. FIFO = First In First Out 순차큐의 문제점을 보완해 나온 것이 원형큐 = 1차원 배열을 사 tildacoderecorder.tistory.com 큐의 원소는 연결 리스트의 노드이고, 각 노드를 포인터로 연결한다. front = 첫 번째 노드를 가리키는 포인터 변..

스택에 대한 설명 👇🏻 https://tildacoderecorder.tistory.com/101 [자료구조] push( ) 와 pop( ) 함수를 이용한 스택 스택의 개념과 구조 : 스택은 마지막에 삽입한 원소는 맨 위에 쌓여 있다가 가장 먼저 삭제 됨 / 후입선출 구조 ( LIFO, Last-In-First-Out ) 스택에서의 삽입 연산 : push 스택에서의 삭제 연산 : pop 기본 tildacoderecorder.tistory.com 큐의 개념과 구조 큐 : 스택과 다르게 "선입선출"의 구조를 가지고 있다. 먼저 들어간 것이 먼저 나오는 구조. FIFO = First In First Out 순차큐의 문제점을 보완해 나온 것이 원형큐 = 1차원 배열을 사용하면서 논리적으로 처음과 끝이 원처럼 연..