cs

탐욕법(그리디) 알고리즘 정의 현제 상황에서 가장 좋은 것 (최선의 선택)을 고르는 알고리즘 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 것을 착안하여 고안됨 최선의 결과를 선택해 나가지만, 최종 결과가 가장 좋은 결과라는 보장은 없다. 최선의 선택이란? 현제 상황에서 선택할 수 있는 것들 중 가장 좋은 것. 그리디 알고리즘 조건 탐욕스러운 선택 조건 탐욕적인 선택은 항상 안전하다는 것이 보장되어야 한다. '안전하다'란 이 선택으로 인해 전체 문제의 최적해를 반드시 도출 할 수 있어야 한다는 것이다. ➡그리디 문제가 나왔을 때, '이 조건이 만족하는 가?'를 생각해 충족하면 그리디 알고리즘을 사용한다. 최적 부분 구조 조건 문제에 대한 최종 해결 방법이 부분 문제에 대해서 최..

그래픽 탐색이란? 하나의 정점으로 부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것 EX) 특정 도시에서 다른 도시로 갈 수 있는지 없는지 너비 우선 탐색 (BFS, Bredth-First-Search) 정의 루트 노드(혹은 임의의 다른 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점부터 가까운 정점을 먼저 방문하고 먼 정점을 나중에 방문하는 방법 즉, 깊게 탐색하기 전에 넓게 탐색하는 것이다. 사용하는 곳 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때. 특징 1) 직관적이지 않은 점 - BFS는 시작 노드에서 거리에 따라 단계별로 탐색한다고 본다. 2) 재귀적인 동작을 하지 않는다. 3) 어떤 노드를 방문했는지 여부를 기록하여 무한루프에 빠질 위험을 제거 4) 방문..

깊이 우선 탐색 (DFS, Depth-First-Search) 정의 루트 노드 (혹은 임의의 다른 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 넓게 탐색하기 전에 깊게 탐색하는 것이다. 특징 1) 깊이 우선이 너비 우선(BFS)보다 간단하지만 느리다. 2) 자기 자신을 호출하는 순환 알고리즘의 형태를 갖는다. 3) 전위 순회(Pre-Order Traversals) 를 포함한 다른 형태의 순회는 모두 DFS의 한 종류이다. 주의점 그래프 탐색의 경우 어떤 노드를 방문했는지 검사해야 무한루프에 빠질 위험이 없다. 동작원리 a노드(시작노드) 방문 - 방문을 표시한다 a와 인접한 노드들을 차례로 순회 - 인접한 노드가 없다면 종료 a와 이웃된 노드b를 방문했다..