C67 Chapter 02. ASCII Code Vs. Uni-Code 보호되어 있는 글 입니다. 2022. 2. 3. Chapter 1. 컴퓨터 구조에 대한 첫 번째 이야기 보호되어 있는 글 입니다. 2022. 1. 12. 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. 이전 1 ··· 6 7 8 9 10 11 12 ··· 17 다음
