Algorithm/Concepts18 최소 스패닝 트리(Minimum Spanning Tree, MST) 목차 최소 스패닝 트리(Minimum Spanning Tree, MST) / Union-Find 신장 트리(Spanning Tree)는 그래프 내의 모든 정점을 연결하고 사이클이 없는 그래프를 의미함.(루트 노드가 없는 트리라고 생각) 트리 : n개의 노드, n-1개의 간선 (모든 노드가 연결, 순환이 없는 그래프) 신장 트리 : 루트노드가 없는 트리 최소 스패닝 트리(MST,minimum spanning tree) 그래프에 간선이 여러개 존재할텐데, 그중에서 스패닝 트리로 만들수 있는 모양중 가중치의 합이 최소가 되는 것 최소 스패닝 트리를 만드는 방법 (크루스칼 알고리즘, MST 알고리즘중 가장 많이쓰이고 빠른편) 먼저 간선을 가중치값을 오름차순으로 정렬 그후에 하나씩 연결을 진행하는데, 연결을 하는.. 2024. 3. 20. Union-Find 목차 Union-Find Union-Find 알고리즘은 두 요소가 같은 그룹에 속하는지를 판단하거나, 두 요소를 같은 그룹으로 합치는 연산을 효율적으로 수행하는 데 사용됩니다. 이 알고리즘은 그래프의 연결성을 확인하거나, 최소 스패닝 트리를 찾는 크루스칼 알고리즘과 같은 다양한 알고리즘에서 중요한 역할을 합니다. Union-Find 알고리즘은 다음 두 가지 주요 연산으로 구성됩니다. Find 어떤 요소가 속한 그룹(또는 집합)의 대표를 찾는 연산. 이 연산을 통해 두 요소가 같은 그룹에 속하는지 확인 가능 두 요소의 Find 연산 결과가 같다면, 두 요소는 같은 그룹에 속한다고 판단 가능 parent[x]를 찾는 과정 Union 두 그룹을 하나의 그룹으로 합치는 연산. 두 요소가 속한 그룹을 Union .. 2024. 3. 20. 백트래킹 (Backtracking) 목차 백트래킹 (Backtracking) 백트래킹 알고리즘은 DFS의 한 형태로 깊이 탐색을 하다가 가능성이 없는 곳이면 빠르게 포기하고, 가능성이 있는 경로만을 따라 해를 찾아나가는 것입니다. 즉, 가지치기 라고 할 수 도 있습니다. 백트래킹은 여러가지 예시를 살펴보면서 이해하는 것이 좋습니다. 대표적인 백트래킹 문제인 N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제입니다. 퀸은 상하좌우 어디로든 가고싶은만큼 이동할 수 있고,대각선으로도 원하는 만큼 이동할 수 있습니다. https://www.cs.usfca.edu/~galles/visualization/RecQueens.html 예시 [백준 9663] N-Queen 현재 col기준으로 앞 .. 2024. 3. 19. 전위 / 중위 / 후위순회 (Preorder/ Inorder / Postorder Traversal)(이진트리 탐색) 목차 이진 트리(Binary Tree)를 탐색하는 방법 이진 트리를 탐색하는 방법(4가지) 전위 순회(Preorder Traversal) 중위 순회(Inorder Traversal) 후위 순회(Postorder Traversal). 레벨순회(Levelorder Traversal) 또는 BFS(Breadth-First Search; 너비 우선 탐색) 참고 : 전위 순회, 중위 순회, 후위 순회는 모두 DFS의 변형으로 간주 전위 순회, 중위 순회, 후위 순회의 명칭은 루트가 어디 있는지 기준입니다. 즉 ,전 -> 루트가 앞 / 중 -> 루트가 중간 / 후 -> 루트가 뒤 전위, 중위, 후위 순회의 각 탐색 방법은 재귀적으로 구현할 수 있으며, 각 노드를 한 번씩 방문하므로 시간복잡도는 모두 O(n)입니다... 2024. 3. 15. 이전 1 2 3 4 5 다음
