backtracking(3)
-
Knight’s Tour Problem(임시_)
Knight’s Tour Problem Knight’s Tour Problem is a problem where we have to find a path for a knight to visit all the cells of a chessboard without visiting any cell twice. 기사 투어 문제는 기사가 체스판의 모든 칸을 두 번 방문하지 않고 모든 칸을 방문할 수 있는 경로를 찾아야 하는 문제입니다. Knight's Tour Problem은 그래프 이론에서 흔히 나오는 문제로, 기사가 이동할 수 있는 8개의 방향 중 어떤 방향으로 움직여야 체스판의 모든 칸을 한 번씩만 방문할 수 있는지를 찾는 문제입니다. 이를 해결하기 위해서는 깊이 우선 탐색(DFS)이나 휴리스틱 등 다양한 ..
2024.02.12 -
3.8.2 Solving n Queen Problem (N 퀸 문제)
CS - 3. Common Algorithms - 3.8 Back Tracking Algorithm - 3.8.2 Solving n Queen Problem Solving n Queen Problem N Queen Problem is a famous problem in Computer Science. It is a problem of placing n queens on an n x n chessboard such that no two queens attack each other. The problem is to find all possible solutions to the problem. N 여왕 문제는 컴퓨터 과학에서 유명한 문제입니다. 두 여왕이 서로 공격하지 않도록 n x n 체스판 위에 n개의 여..
2024.02.10 -
3.5 Graph - 3.5.2 Depth First Search(DFS)
CS - 3. Common Algorithms - 3.5 Graph - 3.5.2 Depth First Search(DFS) Depth First Search 💡Depth first search is a graph traversal algorithm that starts at a root node and explores as far as possible along each branch before backtracking. 깊이 우선 검색은 루트 노드에서 시작하여 각 분기를 따라 가능한 한 멀리 탐색한 후 역추적하는 그래프 탐색 알고리즘입니다. 먼저, 깊이 우선 탐색(Depth First Search, DFS)에 대해 설명드리겠습니다. DFS는 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(b..
2024.01.29