그리디 (greedy) 알고리즘 그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체에서 최선의 선택지라고 가정하는 알고리즘이다. 빠르게 근사치를 계산할 수 있지만, 결과적으로 전체 케이스 중 최적의 값이 아닐 수도 있다. 따라서 이 문제를 그리디 알고리즘으로 해결해도 될지 고민해 보는 것이 필요하다. 그리디 알고리즘 수행 과정 1. 해 선택 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다. 2. 적절성 검사 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다. 3. 해 검사 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 만약 전체 문제를 해결할 수 없다고 판단되면 다시 1번으로 돌아가 과정을 반복한다. 이처럼 그리디 알고리즘을 수행하는 과정은 ..
BFS(Breadth-First Search) : 너비 우선 탐색 그래프 완전 탐색 시작 노드에서 출발해 시작 노드를 기준으로 가장 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다. FIFO 탐색 -> Queue 자료구조를 이용한다. 목표 노드에 도착하는 경로가 여러개일 때 최단경로를 보장한다. 1. 시간복잡도 인접 리스트 노드의 개수가 많고, 간선 수가 적을 때 유리하다. 인접 행렬 노드의 개수가 적고, 간선 수가 많을 때 유리하다. 인접 리스트 인접 행렬 특정 간선 검색 O(degree(N) : 해당 노드의 차수 O(1) 정점의 차수 계산 O(degree(N)) O(N) 전체 노드 탐색 O(E) O(N^2) 메모리 N+E N^2 2. BFS 핵심 이론 1) 방문여부 확인용 배열 BFS도 DFS와 ..
DFS(Depth-First Search) : 깊이 우선 탐색 그래프 완전 탐색 : 모든 노드를 방문하고자 할때, 이 방법을 선택한다. 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정해서 최대깊이까지 탐색을 마친 후, 다른쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 재귀함수 또는 Stack 자료구조를 이용한다. 재귀함수를 이용하므로 stack overflow에 유의해야 한다. 스택 오버플로우(stack overflow)는 지정한 스택 메모리 사이즈보다 더 많은 스택 메모리를 사용하게 되어 에러가 발생하는 상황을 일컫는다. 1. 시간복잡도 (노드 수: N, 에지 수 E) 인접 리스트 노드의 개수가 많고, 간선 수가 적을 때 유리하다. 인접 행렬 노드의 개수가 적고, 간선 수가 많을 때 ..
