CS3 [알고리즘] BFS BFS(Breadth-First Search)는 그래프에서 모든 노드를 넓이 우선으로 탐색하는 대표적인 완전 탐색 알고리즘이다. 이 탐색 방식은 가까운 노드부터 먼저 탐색하고, 그 다음으로 인접한 노드들을 차례차례 탐색한다. 즉, 모든 노드를 같은 깊이 기준으로 탐색한 뒤, 그 다음 깊이의 노드로 넘어가는 방식이다. 이러한 특성 때문에 최단 거리 탐색 문제에서 매우 강력한 탐색 알고리즘이라고 할 수 있다.1. BFS의 탐색 원리BFS는 DFS와 마찬가지로 그래프 탐색 알고리즘이다. 노드(정점)와 간선(연결)을 기반으로 탐색을 진행하며, 차이점은 탐색의 우선순위가 깊이(Depth)가 아닌 넓이(Breadth)에 있다는 점이다.1.1. BFS의 동작 방식BFS는 큐(Queue) 자료구조를 이용해 탐색을 진행.. 2025. 4. 24. [알고리즘] DFS DFS(Depth-First Search)는 완전탐색을 위한 그래프 탐색 알고리즘으로 그래프의 노드를 탐색할 때 가장 깊은 곳까지 탐색 후 더 이상 탐색할 수 없을 때 이전 단계로 돌아오는 방식으로 탐색하여 모든 노드를 탐색한다. 이처럼 가장 깊은 곳까지 탐색 후 한 단계 이전으로 돌아오는 방식으로 탐색하기 때문에 스택이나 재귀로 구현할 수 있다.1. DFS의 탐색 원리DFS는 그래프 탐색 알고리즘이기 때문에 노드(수학에서는 정점)가 탐색의 기준이 되며 노드들이 연결된 경로를 간선(edge)라 한다. 여기서 깊이 우선 탐색이라 함은 시작 노드를 기준으로 간선을 쭉 따라가 더 이상 다른 간선으로 연결되지 않은 노드까지 탐색을 우선 진행한다는 의미이며 이와 상반되는 개념은 BFS(넓이 우선 탐색)이 있다. .. 2024. 12. 25. [알고리즘] 그리디 알고리즘 그리디(Greedy)란 영어 단어로 “탐욕스럽다”라는 뜻을 지닌다. 알고리즘 분야에서 “탐욕스럽게” 문제를 해결한다는 것은, 매 순간마다 당장 최선이라고 생각되는 선택을 반복해서 전체 문제를 해결하려는 접근 방식을 의미한다. 이러한 ‘탐욕적 선택(Greedy Choice)’을 통해 전역적으로도 최적해(Optimal Solution)에 도달할 수 있기를 기대하는 것이 그리디 알고리즘(Greedy Algorithm)이다.1. 문제 해결 최적화 기법그리디 알고리즘을 이해하려면, 국소적 최적화(Local Optimization)와 전역적 최적화(Global Optimization) 개념을 함께 살펴봐야 한다.1.1 국소적 최적화 (Local Optimization)정의: 각 단계에서 당장 가장 유리한 선택을 하.. 2024. 12. 18. 이전 1 다음
