자료구조
-
최소 비용 신장트리자료구조 2022. 8. 9. 18:41
📌최소 비용 신장트리 💡최소 비용 신장트리 정의 가중치가 부여된 무방향 그래프에서 신장 트리의 비용 가중치 : 두 vertex 사이의 거리 혹은 연결하는 비용 = 신장트리를 구성하는 에지들의 비용의 합 최소 비용 신장트리 : 가장 비용이 적은 신장 트리 응용 분야 도로 건설 : 도시를 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제 ex) 통신, 배관 최소 비용 신장트리 알고리즘 최소 비용 신장트리 알고리즘 1) 그래프 내에 존재하는 Edge들만 사용한다. 2) 정점의 개수가 n일 때, n - 1개의 Edge들만 사용한다. 3) 사이클을 형성하는 edge는 사용불가하다. 최소 비용 신장트리를 구하기 위한 알고리즘들 1) 크루스칼 2) 프림 3) 솔린 💡크루스칼 알고리즘(Kruskal Algorit..
-
기초적인 그래프 연산들자료구조 2022. 8. 9. 18:18
📌 기초적인 그래프 연산들 💡깊이 우선 탐색(Depth First Search) DFS 알고리즘 출발 정점, v의 인접리스트부터 방문한다. v에 인접하면서 아직 방문하지 않은 정점 w를 선택한다. w를 시작점으로 하여 다시 DFS를 시작한다. 순환 알고리즘을 이용하여 구현한다.(재귀) 💡너비 우선 탐색(Breath First Search) BFS 알고리즘 출발 정점, v의 인접 리스트부터 방문한다. v에 인접한 모든 vertex부터 방문한다. 그 다음, v에 인접한 첫번째 vertex에 인접한 vertex 중에서 아직 방문하지 않은 vertex 들을 차례대로 다시 방문한다. -> Queue 자료구조를 사용하여 구현 💡연결요소(Connected Component) 무방향성 그래프가 연결되어 있는지 검사한다..
-
그래프의 개념과 표현자료구조 2022. 7. 17. 18:51
📌 그래프의 개념과 표현 💡 그래프 소개 그래프(Graph)란? 연결되어 있는 객체 간의 관계를 표현하는 자료구조 - 지하철 노선도, SNS 친구 관계, 컴퓨터 네트워크 💡 그래프 데이터 타입 그래프 G의 두가지 구성요소 V(G) : G에 포함된 Vertex(정점)들의 집합 E(G) : G에 포함된 Edge(간선)들의 집합 무방향성 그래프(Undirected Graph) Vertex 의 쌍을 나타내는 Edge가 방향성이 없다. (u, v), (v, u) 는 동일한 Edge 를 표현하는 것이다. EX) 지하철 노선도 방향성 그래프(Directed Graph) 각 Edge에 방향성이 존재하는 그래프 (u, v) : v -> v 인 Edge를 표현하는 것이다. u : Tail v : Head 💡 그래프에서 사..
-
이진 검색 트리자료구조 2022. 7. 17. 16:46
📌 이진 검색 트리 💡 이진 검색 트리(Binary Search Trees) 히프의 문제점 임의의 데이터를 갖는 노드를 삭제할 경우의 시간 복잡도 : O(N) 트리에서 특정 데이터를 갖는 노드를 검색하는 시간 복잡도 : O(N) 이진 검색 트리란? 트리 내에서 특정 데이터(Key 값) 을 갖는 노드를 효율적으로 검색 - O(Log N), 하지만 정렬된 상태를 유지해야한다. 이진 검색 트리의 정의 모든 노드는 유일한 키 값을 가지고 있다. 왼쪽 서브 트리에 저장된 키 값 루트 노드의 키 값 양쪽 서브 트리도 이진 검색 트리이다. 💡 검색 연산 기본 개념 if(key == root -> data) return if(key data..
-
히프의 개념과 응용자료구조 2022. 7. 17. 03:18
📌 히프의 개념과 응용 💡 히프(Heap)의 정의 최대 트리와 최대 히프 최대 트리(Max Tree) 트리의 모든 노드에 대해서 노드의 데이터 값이 자식 노드의 데이터 값보다 크거나 같은 트리 최대 히프(Max Heap) 최대트리 이면서, 완전 이진트리. 최소 트리와 최소 히프 최소 트리(Min Tree) 트리의 모든 노드에 대해서 노드의 데이터 값이 자식 노드의 데이터 값다 작거나 같은 트리 최소 히프(Min Heap) 최소트리 이면서, 완전 이진트리. 최대 히프의 root 노드는 항상 모든 노드들보다 큰 값을 가지고 있다. 최소 히프의 root 노드는 항상 모든 노드들보다 작은 값을 가지고 있다. 이는 가장 큰 값과 가장 작은 값을 찾기 쉬운 자료구조이다. 💡 우선 순위 큐(Priority Queue..
-
스레드 이진트리자료구조 2022. 7. 17. 02:41
📌 스레드 이진트리 💡 스레드 이진트리(Threaded Binary Tree) 스레드 이진트리의 기본 개념 n개의 노드를 갖는 이진 트리에는 2n 개의 링크가 존재한다. 2n 개의 링크 중에 n+1 개의 링크 값은 null이다. null 링크를 다른 노드에 대한 pointer 로 대체한다. (= Threads) 니는 루트를 제외한 모든 노드는 부모 노드가 있기 때문에 트리의 링크 수는 n-1 개이다. 스레드의 이용 ptr -> left_child = NULL 일 경우, ptr -> left_child 를 ptr의 중위행선자를 가리키도록 변경한다. 중위행선자(inorder predecessor) : 중위 순회에서 현재 노드 바로 앞에 나오는 노드 ptr -> right_child = NULL 일 경우, p..
-
이진트리의 추가 연산자료구조 2022. 7. 15. 00:57
📌 이진트리의 추가 연산 💡 이진트리의 추가 연산 추가 연산의 종류 이진트리의 복사 이진트리가 동일한지 검사 이진트리의 노드 수 계산 이진트리의 단말 노드 수 계산이진트리의 모든 노드들을 모두 한번씩 다 방문해야 한다. 트리의 모든 노드들을 방문할 필요성 이진트리의 순회 알고리즘 등을 응용한다. 💡 이진트리의 복사 문제 설명 입력 이진트리의 노드 구조와 동일한 새로운 이진트리를 생성하고 루트 노드의 주소 반환 후위순회 알고리즘을 사용한다. 💡 이진트리의 복사 알고리즘 struct node *copy(struct node *original){ # original 트리를 복사한 새로운 이진트리를 반환한다. struct node *temp; if(original != NULL){ temp = (struct n..
-
이진트리의 순회자료구조 2022. 7. 12. 14:37
📌 이진트리의 순회 💡 이진트리순회(Binary Tree Traversal) 문제 정의 이진 트리의 모든 노드를 한번씩 방문한다. 트리에 있는 노드의 순서를 결정한다. 순회방법 중위순회(L-V-R) 전위순회(V-L-R) 후위순회(L-R-V) 💡 중위순회 void inorder(struct link *ptr){ if(ptr){ inorder(ptr -> left_child); printf("%d", ptr -> data); inorder(ptr -> right_child); } } 💡 전위순회 void preorder(struct link *ptr){ if(ptr){ printf("%d", ptr -> data); preorder(ptr -> left_child); preorder(ptr -> right_..
-
트리와 이진트리의 개념자료구조 2022. 7. 12. 14:21
📌 트리와 이진트리의 개념 💡 트리의 개념 트리란? 계층적 구조의 자료를 표현할 때 사용 ex) 가계도, 회사의 조직도, 폴더 구조 등 트리의 정의 하나 이상의 노드로 이루어진 유한 집합 Root(루트) 라고 하는 노드가 하나 존재한다. 나머지 노드들은 n(n >= 0) 개의 집합 T[1], ... ,T[n]으로 분할 이처럼 분할된 트리를 루트의 서브트리라고 한다. 💡 트리에 관련된 용어들 Level 1 : 노드의 차수(Degree), 트리의 차(Degree) Level 2 : 단일노드(Leaf node or Terminal node) Level 3 : 부모노드, 자식노드, 형제노드 Level 4 : 조상노드, 자손노드, level, 트리의 높이 or 깊이 💡 이진트리의 개념 이진트리(Binary Tre..
-
이중 연결 리스트자료구조 2022. 7. 12. 13:50
📌 이중 연결 리스트 💡 이중 연결 리스트의 개념 이중 연결 리스트(Double Linked List)란? 한 노드에 두 개의 Link 가 저장 이중 연결 리스트는 양방향으로 이동가능 단일 연결 리스트의 경우, 한 방향으로만 이동이 가능. struct node{ struct node *llink; // 이전 노드 포인트 int data; struct node *rlink; // 다음 노드 포인트💡 이중 연결 리스트의 종류 체인 처음 노드의 llink와 마지막 노드의 rlink는 NULL ptr = ptr -> llink -> rlink = ptr -> rlink -> llink 원형 이중 연결 리스트 원형 이중 연결리스트에 노드를 추가하는 방법 새로 추가되는 링크의 노드를 먼저 바꾸는 것이 좋다.void..