union and find는 여러 개의 원소가 존재하고 특정 원소가 어떤 집합에 속해있는지 확인할 때, 집합끼리 연결해줄 때 이용하는 자료구조이다. 처음에 아무것도 연결이 안되어 있을 때 uf 배열은 부모노드의 번호를 가리키고 있다. uf[1] = 3, uf[5] = 6 으로 해주었을 때 부모 노드가 바뀌게 된다. 만약 union(5,1)로 서로 자기 자신이 아닌 부모 노드가 존재할 때는 find 함수를 써야한다. find 함수를 써서 uf[x] = x 인경우까지 찾아줘야 한다. 그리고 나온 값들로 union을 하게 된다. find(5) => 6 -> find(6) => 6 이므로 멈춘다 , find(1) => 3 find(3) => 3 멈춘다 그리고 -> union(6,3) 을 하게 된다. find(x..

그래프는 연결되어 있는 원소간의 관계를 정의한 것을 그래프라고 한다. 그래프는 양방향 그래프, 단방향 그래프가 있는데 양방향 그래프는 위의 그림과 같이 방향이 표시 되어 있지 않지만 둘 다 연결되어 있는 것이다. 단방향 그래프는 방향이 존재한다. 이것에 대한 표현은 연결리스트나 행렬로 할 수 있다. 그래프의 탐색에는 두 가지 방법이 있다. DFS/ BFS DFS DFS는 Depth first search 로 깊이 우선 탐색이라고 한다. 노드에 방문하고 해당 노드에 연결된 첫번째 노드부터 쭉 따라 들어가면서 탐색 하는 것이다. DFS는 스택으로 구현을 하게 된다. 연결리스트 DFS // not yet 인접행렬 DFS 3 x 3행렬로 해봤을 때 dfs 인접행렬 코드 void dfs(int** matrix, ..

이진트리 탐색 시에 원활하게 하는 방식이 더 있는데 root를 기준으로 왼쪽은 root보다 작은 값들을, 오른쪽은 root보다 큰 값들이 오게 하는 것이다. 그래서 찾는 값을 봤을 때 root보다 크면 오른쪽에서 작으면 왼쪽에서만 찾게되어 더 빠르게 찾을 수 있게 된다. function binarySearch(int n) { node_t node = binarySearch.root; // root를 가져온다 while(node != NULL && node.data != n){ if(node.data > n) node = node.left; else node = node.right; } if(node == NULL) fprintf(stderr, "error"); return node; } 이진탐색트리 삽입..

트리는 선형적인 데이터는 아니지만 데이터끼리 부모와 자식들로 연결된 계층적 구조이다. 트리에 대한 용어들은 루트(root) , 차수(degree), 깊이(depth), 높이(height), leaf node, level, sub tree이 있다. root는 트리의 처음 볼 위치로 어디서든 기준을 잡고 볼 수 있다. degree는 특정 노드를 기준으로 자식의 수가 얼마나 되는지를 나타낸다 depth는 루트노드와 얼마나 떨어져있는지를 나타낸다. 루트노드에서의 특정 노드 사이의 간선의 개수이다. height는 트리에서 깊이가 가장 깊은 것의 깊이를 나타내거나 +1 한 것을 나타낸다 height의 시작을 1 또는 0으로 할 수 있기 때문 leaf node는 자식이 없는 노드들을 말한다. subtree는 부모와의..