전체 글152 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. 팬케이크 정렬(Pancake sort) 목차 팬케이크 정렬(Pancake sort) 설명 팬케이크 정렬 알고리즘은 무작위로 쌓여있는 팬케이크를 정렬하는 방법이라고 생각하면 됩니다. 뒤집개를 이용해서 제일 꼭대기부터 뒤집개까지를 잡고 뒤집어 가며 정렬하는 것입니다. 같은 말로 0~k까지의 순서를 확 뒤집는 flip을 사용한 정렬방법이라고 할 수 있습니다. 정렬 방법 무작위로 쌓여있는 팬케이크 중에서 가장 큰 팬케이크 찾아 그 펜케이크 밑에 뒤집개를 두고 크게 한번 뒤집습니다. 그러면 제일 큰 팬케이크가 제일 위에 쌓이게 됩니다. 그다음에 이제 전체 팬케이크 탑을 한번 뒤집게 되면 제일 큰 팬케이크가 아래로 오게 됩니다.. 다음으로 제일 아래 깔린 팬케이크를 제외하고 그다음으로 큰 팬케이크를 찾고 거기를 기준으로 뒤집개를 두고 뒤집습니다. 그러면.. 2024. 3. 15. 전위 / 중위 / 후위순회 (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 ··· 12 13 14 15 16 17 18 ··· 38 다음
