Minimum-cost Spanning Tree Spanning tree - connected undirected weighted tree를 말한다 ( 모든 점들이 연결되어 있어야 하며 cycle이 없는 tree) - BFS / DFS 로 찾을 수 있다 - cost : 모든 엣지의 weight의 합 - 점이 n개면 엣지는 n-1개 (당연) -> spanning tree중에서 엣지들의 가중치 합이 최소인 트리를 찾는 알고리즘! 1. Kruskal Algorithm - edge를 이용! - 큭큭. 엣지잇게 엣지중에서 엣지하나선택 ㅋㅋ - 엣지를 오름차순으로 정리 - 젤작은거부터 하나씩 고름 ! 이때 사이클이 발생하지 않을때만 고른다! 모든간선에대해 다하면 끗 or n-1개 고르면 끗 복잡도는 O(eloge)..

* 선형 자료 구조 : array, linked list, stack, queue 비선형 자료구조 : tree, graph, hash ! Concepts • graph 정의 : 하나 이상의 노드들의 집합 V와 두 노드)의 쌍으로 구성된 edhe들의 집합 E로 이루어진 자료구조 ( 노드와 엣지의 집합으로 구성된 자료구조. pair(V, E) ) - tree는 graph의 특수한 경우 ! (Graph가 더 큰 범위) • 종류 Directed graph ( = digraph ) - 화살표 있는거 - self-loop 있음 Undirected graph - 화살표 없는거 - self-loop 없음 Weighed graph - 각 엣지에 가중치가 부여되는 것 (거리를 의미~~ 거리가 서로 다름~~ 노드사이의 거리..

Concept 정의 : M-way Search Tree + AVL tree - M-way search tree : 자식 노드가 최대 m개이고 최대 m-1개의 키를 갖는 탐색 트리 - 최소 𝑚/2(위로올림) 개의 자식을 가짐 쓰이는 곳 - database 와 file system에서 쓰임. 복잡도 O(log n)

레드블랙트리 개념 - 모든 노드의 컬러가 red / black 인 binary search tree - 모든 빈 노드(null pointer)가 외부 노드로 대체된다 (external node = 맨끝에잇는 리프노드. 네모) (자녀가 없음 -> 자녀를 nill 노드라고 설정함) - 복잡도 O(log n) !!! - rank : 해당 노드에서부터 external node까지 블랙노드 개수 lemma (부명제) - h 부모가 레드면 자식은 무조건 블랙 (삽입시 어기게됨) - 레드규칙 이라고 부름 - 루트에서(임의의 노드에서) 외부까지 모든경로에서 블랙 개수는 같다! (자기 자신은 제외) -> delete연산시 위반가능. 연산 1. insert 굿노트에 정리함~~

Merge sort A. concept : 두 sorted list를 합친다. 각각 리스트의 맨첨 애를 비교해서 작은 애를 새로운 리스트에 넣는 방식 -> 리스트를 1개 될때까지 다 절반으로 divide 한 담에 차례로 merge 합니다 처음에는 sorted안되어있으니까 다 1개인걸로 쪼개놓으면 sorted니까 쪼개서 합치는 것!! B. Code C. Analysis : O(nlogn) !! - (worst average 둘다) T(1)=1, T(n)=2T(n/2)+n 알고리즘 정리한거 참고 Quick Sort = 분할 정복 divide-and conquer 알고리즘. (그대로 해결할 수 없는 문제를 작은문제로 분할하여 문제 해결함) 1. 피벗 하나를 정해서 앞에는 피벗보다 작은걸 배치, 뒤에는 피벗보다..

Concept * • Hash : 많은 양의 데이터들을 그보다 작은 크기의 테이블로 대응시켜 저장할 수 있는 알고리즘 데이터를 특정 위치에 쌍으로 저장하는 것인듯! 해시란 데이터를 다루는 기법 중에 하나로 검색과 저장이 아주 빠르게 진행됩니다! 데이터를 검색할 때 사용할 key와 실제 데이터의 값이 (value가) 한 쌍으로 존재하고, key값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴하게 됩니다. hash function h(k)을 사용하여 key를 주소로 mapping해주어 빠르게 searching이 가능하도록 하는 방법이다. hashing은 key와 주소가 직접 연결된 구조가 아니라 hash function을 통한 key와 임의의 주소로 연결되는 구조이다..

정의 : 모든 노드에 대해서 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이차가 1이하는 BST (이진탐색트리) 리프노드의 height=0 균형도 값 = 좌측서브트리의 높이-우측서브트리의 높이. 이게 1보다 커지면 회전을 한다 *아무것도 없는것 : -1로 가정함 ! (NULL=-1) 이 값이 양수 -> 왼쪽 치우침 / 음수 -> 오른쪽 치우침 높이 결정법 MAX(좌 서브트리높이, 우서브트리높이) + 1 (둘중 더 큰 값 + 1 이 높이가 됩니당) LL: 왼쪽으로 치우쳐있으므로 오른쪽으로 회전함 RR: 오른쪽으로 치우쳐 있으므로 왼쪽으로 회전 (이건 반대로 회전) (얘넨 그대로 회전) LR : 왼쪽으로 치우쳤는데 왼쪽노드의 오른쪽서브트리가 더 무거울때 함 (왼쪽무겁-의 오른쪽무겁 이라서 LR) ..

Concepts ; Heap 이란 정의 : 여러개의 값들 중에서 가장 큰 값 / 가장 작은 값을 빠르게 탐색하도록 만들어진 binary tree 자료구조 • complete binary tree (완전 이진 트리) 임 ; 맨 아래 레벨 빼고 다 채워져있고, 맨 아래 레벨애들은 왼쪽부터 채워저 있는 것 -> 높이가 h일때 총 노드 개수는 2^h ~ 2^(h+1) -1 가 존재한당 (h-1 높이에서는 2^(h-1) -1 ) ( full : 자식이 0개 또는 2개인 것 ) • 부모노드의 키가 자식보다 같거나 크다 (MAX heap) - root 가 젤 큼 ( MIN heap은 자식이 더 크겠지용 ) 기능 • push : 해당 값을 완전 이진트리가 되도록 젤 왼쪽 자식 노드에 넣는다 그리고 부모값과 비교해서 계..

** 갑자기 포인터 이해하기 그냥 포인터 = 변수의 주소를 저장. -> 해당 변수의 값 변경 가능 ! (그걸 위함) 포인터의 포인터 = 변수의 주소를 담고있는 포인터변수의 주소를 저장 -> 포인터변수안의 값 접근, 변경 가능 ! 포인터 변수안에는 변수의 주소가 저장되어 있음 -> 주소 변경 가능 = 해당 포인터 변수가 다른 주소를 가리키게 할 수 있다 ! -> 실습 스택 코드에서 push할 때 top노드의 이중포인터 사용하는것은 top은 첫번째 노드의 주소 가지고 있는데 push하면 첫번째 노드가 달라지므로 top이 다른 주소를 저장해야댐 !! -> 걍 top의 값을 변경해줘야하니까 *한번 더붙임 !! -> 걍 *을 붙이는 것은 해당 변수 내부의 값을 바꿔주기 위해서 하나 더 붙여준다고 생각하자 !! (..

Tree ? * 여태는 다 Linear list ; 선형적으로 연결된 데이터에 유용 ! serially ordered data tree는 -> 계층구조 데이터 저장에 유용 ! hierarchically ordered data = 자료와 그 다음 자료의 위치 정보가 저장된 비선형의 자료구조 > 트리 성질 - 루트 노드 제외하고 모두 하나의 부모 노드를 가진다 - 여러개의 자식 노드를 가질 수 있다 - 한 노드에서 다른 노드로 가기 위한 경로가 유일하다 ! (-> 트리의 조건 !) > 쓰이는 곳 - file system - compiler - graphics - database (index) > 기본 용어 • root : top of the hierarchy • leaf / terminal node : 맨 ..