Algorithm37 백트래킹 (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. 최단 경로 (플로이드-와샬(Floyd-Warshall)) 목차 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와샬 알고리즘은 모두 그래프에서 최단 경로를 찾는 알고리즘입니다. 각 알고리즘은 특정한 조건에서 사용됩니다. 다익스트라 : 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾을 때(음의 가중치가 없는 경우) 벨만-포드 : 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾을 때(음의 가중치가 존재하는 경우. 단, 음의 사이클이 있으면 최단 경로 문제의 해를 찾는 것은 불가능) 플로이드-와샬 : 모든 노드쌍에 대한 최단경로를 모두 찾을 때(음의 가중치가 없어도 있어도 모두 사용가능. 단, 음의 사이클이 있으면 최단 경로 문제의 해를 찾는 것은 불가능) 플로이드-와샬(Floyd-Warshall) 플로이드-와샬 알고리즘은 모든 정점 간의 최단 경.. 2024. 2. 15. 최단 경로 (벨만-포드(Bellman-Ford)) 목차 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와샬 알고리즘은 모두 그래프에서 최단 경로를 찾는 알고리즘입니다. 각 알고리즘은 특정한 조건에서 사용됩니다. 다익스트라 : 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾을 때(음의 가중치가 없는 경우) 벨만-포드 : 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾을 때(음의 가중치가 존재하는 경우. 단, 음의 사이클이 있으면 최단 경로 문제의 해를 찾는 것은 불가능) 플로이드-와샬 : 모든 노드쌍에 대한 최단경로를 모두 찾을 때(음의 가중치가 없어도 있어도 모두 사용가능. 단, 음의 사이클이 있으면 최단 경로 문제의 해를 찾는 것은 불가능) 벨만-포드(Bellman-Ford) 벨만-포드 알고리즘은 간선이 음의 가중치를 가질 때, 하.. 2024. 2. 14. 이전 1 ··· 4 5 6 7 8 9 10 다음
