C/자료구조와 알고리듬16 Chapter 16. Backtracking Note) DFS와 BFS의 단점 - DFS는 인접행렬의 크기가 커져서, 순회하는 트리의 구조가 깊어질수록 탐색이 상당히 느려지는 단점이 있음. - BFS의 경우, 인접행렬이 커질수록 큐의 크기도 기하급수적으로 커짐. 즉, 메모리의 사용량이 상당히 증가함. - 순회하는 트리의 깊이와도 상관없으며, 메모리 사용량도 줄일순 없을까? Def) Backtracking - 탐색하는 도중에, 지금의 서브 트리에 정답이 없을거 같다면 해당 서브 트리를 더이상 순회하지 않고 되돌아 가는 기법 - 이런 방식을 가지치기(Prunning)이라 함. - 어떤 노드의 유망성(Promising)을 판단하여, 유망하지 않다면 해당 노드를 가지치기하고, 부모 노드로 되돌아감(Backtraing) Note) Backtracking을 .. 2021. 12. 12. Chapter 15. BFS Def) 너비 우선 탐색(BFS, Breadth First Search) - 현재 정점과 인접한 모든 정점을 방문한 후, 다시 이들 정점과 인접한 모든 정점을 찾아 방문하는 방식. - 시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어진 정점을 나중에 방문. - 보통 큐를 이용하여 구현 Thm) BFS 구현 With 큐 #define _CRT_SECURE_NO_WARNINGS #include #include enum { FALSE = 0, TRUE = 1, MAX_COUNT = 101, }; typedef struct queue { intnArray[MAX_COUNT]; size_tuCnt; size_tuFront; size_tuRear; } queue_t; void enqueue(queue_t*.. 2021. 12. 2. Chapter 14. DFS Def) 그래프 순회(Graph Traversal) - 하나의 정점에서 시작하여 모든 정점들을 한 번씩 방문하는 작업 - 많은 문제들이 그래프 순회를 이용하여 해결될 수 있음. ex. 두 정점 사이의 연결 경로가 있는지 검사, 최단 거리 검사 등등 - 대표적인 그래프 순회 방법으로는 깊이 우선 탐색(Depth First Search), 너비 우선 탐색(Breadth First Search) Def) 깊이 우선 탐색(DFS, Depth First Search) - 현재 정점과 인접한 정점 중 하나를 선택하여 이동하는 과정을 반복. 더이상 이동할 정점이 없을 경우, 뒤쪽으로 백트래킹(Backtracking)하여 다시 이동할 경로를 탐색. - 시작 정점으로부터 거리가 멀어지는(깊이가 깊어지는) 방식으로 정점을.. 2021. 11. 28. Chapter 13. 그래프(Graph) Def) 그래프(Graph) - 개체 간의 연결 관계를 표현할 수 있는 비선형 자료구조 - ex. 도시들 간의 연결, 지하철 노선도, SNS 친구 관계도 등 Note) 그래프의 구성 요소 - 그래프 G = (V, E) - 정점 V(Vertex, Node) 그래프를 구성하는 기본 단위. 노드. 데이터를 저장하거나 상태를 표현 - 엣지 E(Edge, Link) 정점과 정점을 잇는 선. 간선. 방향을 가질 수도 있음. 가중치(Weight)를 가질 수도 있음. Note) 그래프 관련 용어 가중치(Weight) 엣지에 부여된 수치. 비용(Cost) 인접 정점(Adjacent Vertex) 엣지로 연결되어 있는 정점 차수(Degree) 정점에 연결된 다른 정점의 개수 경로(Path) - 특정 정점에서 다른 정점으로.. 2021. 11. 26. 이전 1 2 3 4 다음
