전체 글128 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 깊이 우선 탐색 DFS(Depth First Search)와 너비 우선 탐색 BFS(Breadth First Search)은 그래프를 탐색할 때 사용되는 알고리즘이다. 📌그래프란, vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, dege는 정점과 정점을 연결하는 간선이다. 1. 깊이 우선 탐색(DFS) 시작 정점으로부터 최대한 깊이 탐색한 뒤, 더이상 탐색 할 곳이 없을 경우 옆으로 이동 💡깊이 우선 탐색은 루트 노드(혹은 다른 임의의노드)에서 시작해 다음 분기(branch)로 넘어 가기 전에 해당 분기를 완변하게 탐색하는 방법이다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 .. 2021. 11. 12. 그리디 알고리즘(Greedy Algorithm) 1. 그리디 알고리즘이란? 그리디 알고리즘 : "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법이다. 예를 들어 위 그림에서 0부터 시작해 아래로 내려가며 요소의 수를 더해 가장 큰 결과를 만들어야 하는 문제가 있다고 할 때 그리디 알고리즘은 순간마다 최적의 해답을 찾기 때문에 처음 시작인 0에서 1보다 9가 큰수이기 때문에 9를 선택한다. 이후 9인 지점에서 12와 16중에 큰수인 16을 선택하여 최종 결과는 9+16으로 25가 된다. 하지만 실제 가장 큰 수를 만들수 있는 경로는 1을 거쳐 99로 가는 것이다. 이처럼 문제해결에서 그리디 알고리즘으로 해결 할 수 없는 문제에 그리디 알고리즘을 적용한 경우에는 최적해를 보장해주지 못한.. 2021. 11. 3. 이전 1 ··· 19 20 21 22 다음
