백트래킹 (Backtracking) 정의 백트래킹은 모든 가능한 경우의 수 중에서 특정 조건을 만족하는 경우만을 찾아내는 기법입니다. 해결 과정에서 더 이상 진행이 불가능하다고 판단되면, 이전의 분기점으로 돌아가 다른 가능성을 탐색합니다. 사용 예 문제: N-Queen, 순열, 조합 등 과정 설명 선택: 가능한 후보 중 하나를 선택합니다. 제약 조건 검사: 선택이 문제의 제약 조건에 위배되는지 확인합니다. 목표 확인: 현재 선택이 문제 해결의 목표에 도달했는지 확인합니다. 불가능한 경우 백트래킹: 선택이 불가능하다면 이전 단계로 돌아갑니다. Sudo Code def is_safe(board, row, col): # 해당 위치에 퀸을 놓을 수 있는지 확인하는 함수 def solve_n_queen(board..
Computer Science/자료구조
너비 우선 탐색 (BFS, Breadth-First Search) BFS는 그래프의 모든 정점을 탐색하는 알고리즘 가장 가까운 정점부터 우선적으로 탐색하는 방식 특징 재귀적으로 동작하지 않는다 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다 (무한 루프의 위험) 방문한 노드들을 차례대로 저장 한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다 Prim 알고리즘, 다익스트라 알고리즘(Dijkstra’s Algorithm) 과정 설명 시작 정점 선택: 탐색을 시작할 정점을 선택합니다. 인접 정점 큐에 추가: 현재 정점에 인접한 모든 정점을 큐에 추가합니다. 큐에서 정점 추출: 큐에서 정점을 하나씩 추출하며 탐색합니다. 방문..
깊이 우선 탐색 (DFS, Depth-First Search) 정의 DFS는 그래프의 모든 정점을 탐색하는 알고리즘 중 하나로, 가장 깊은 부분을 우선적으로 탐색하는 방식입니다. 사용 예 문제: 그래프의 모든 정점 방문, 경로 탐색 등 과정 설명 시작 정점 선택: 탐색을 시작할 정점을 선택합니다. 인접 정점 탐색: 현재 정점에서 갈 수 있는 인접한 정점을 찾습니다. 깊이 우선 탐색: 인접한 정점 중 하나를 선택하여 더 깊게 탐색합니다. 방문 체크: 방문한 정점은 체크하여 중복 방문을 방지합니다. Sudo Code def dfs(graph, v, visited): visited[v] = True for i in graph[v]: if not visited[i]: dfs(graph, i, visited)
