지나가던 컴공생

선형 자료구조 : queue, stack, array 등 비선형 자료구조 : binary tree 등 이진트리는 트리 자료구조를 활용해 데이터 탐색 속도 증진을 위해 사용하는 구조이다. 완전 이진트리인 경우 힙정렬(Heap sort)를 이용해 배열을 사용해도 괜찮았지만, 완전 이진트리가 아닌 경우에는 데이터의 낭비를 줄이기 위 해 포인터를 사용하는 것이 좋음. 이진트리에 사용되는 자료구조에 따라 각 탐색, 삽입, 삭제의 시간 복잡도는 아래와 같다. 이진트리에서 데이터를 참색하는 방법은 크게 3가지가 있다. Ⅰ. 전위순회(Preorder Traversal) (1) 자기 자신을 처리 (2) 왼쪽 자식을 처리 (3) 오른쪽 자식을 처리 Ⅱ. 중위순회(Inorder Traversal) (1) 왼쪽 자식을 처리 ..

ㅇ 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결 하는 알고리즘 -> 최소 비용 신장트리를 만들기 위함 ex) 여러 개의 도시들을 연결 하고자 할 때 비용을 최소한으로 하기 위해 사용 - 거리(cost)가 짧은 순서대로 그래프에 포함 시키면 됨 - 모든 노드를 최소비용으로 연결만 시키면 되기에 모든 간선 정보를 오름차순으로 정렬 한 뒤에 비용이 적은 간선부터 그래프에 포함 - 최소 비용 신장트리에서는 사이클이 발생하면 안 됨 1. 정렬된 순서에 맞게 그래프에 포함 2. 포함시키기 전에 사이클 테이블 확인 3. 사이클을 형성하는 경우 간선을 그래프에 포함시키지 않음 ★ 사이클이 발생하는지 여부는 Union-Find 알고리즘을 사용 #include #include #include using nam..

Union-Find는 그래프 알고리즘으로써, '합집합 찾기'라는 의미를 가진다. 여러개의 연결되지 않은 노드 집합들이 있다고 가정하자. (1) - (2) - (3) - (4) (5) - (6) - (7) - (8) 1,2,3,4와 5,6,7,8을 각각 연결되어있는 노드들이다. 여러한 그래프에서 '연결성'을 프로그래밍 언어로 표현하는 것이 Union-Find 알고리즘이다. Union-Find 알고리즘의 원리는 노드의 집합중 가장 작은 값을 가지는 노드가 부모 노드라고 가정하고, ex) 1,2,3,4의 부모노드는 모두 1이다. 부모노드가 같으면 연결되어 있다고 생각하는 것이다. find는 해당 노드의 부모 노드를 찾는 알고리즘이고 ex) find(3)을 하면 1을 반환 union은 노드의 집합을 연결하는 알..

ㅇ 시작 노드와 가까운 순서대로 맹목적 탐색이 이루어진다. ㅇ 스택을 이용하여 구현하지만 재귀함수를 이용하면 재귀함수는 스택의 원리를 이용하고 있기 때문에 스택이 없어도 구현 가능하다. 1. 스택에서 최상단 노드를 확인한다. 2. 최상단 노드에 방문하지 않은 연결된 노드가 있으면 그 노드를 스택에 넣고 방문처리한다. 인접노드가 없다면 스택에서 최상단 노드를 제거한다. 아래 코드는 baekjoon 1260번 문제의 양식에 맞게 작성한 코드 이다. // dfs #include #include #include using namespace std; int n,m,startNode; vector visit; vector node; void dfs(int start) { if(visit[start]) return;..

ㅇ 시작 노드와 가까운 순서대로 맹목적 탐색이 이루어진다. ㅇ 큐를 이용하여 구한다. ㅇ 사용 예) 미로찾기 등 1. 큐에서 하나의 노드를 꺼낸다. 2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다. 아래 코드는 baekjoon 1260번 문제의 양식에 맞게 작성한 코드 이다. // bfs #include #include #include #include using namespace std; int n,m,startNode; // n : 정점의 개수, m : 이어져있는 노드의 수, startNode : bfs를 시작할 노드 vector visit; // 방문한 노드를 표시하기 위함 vector node; // vector 배열을 받기 위함 void bfs(int st..