입문자 독자를 위한 그래프 탐색 기법에 대한 이해

소개글

"입문자 독자를 위한 그래프 탐색 기법에 대한 이해"에 대한 내용입니다.

목차

1.서론
1.1.그래프 탐색 기법에 대한 이해의 필요성
1.2.스택과 큐의 소개
1.2.1.스택의 개념
1.2.2.큐의 개념

2.깊이 우선 탐색과 넓이 우선 탐색의 소개
2.1. 깊이 우선 탐색
2.1.1. 깊이 우선 탐색의 개념
2.1.2. 깊이 우선 탐색의 과정
2.2. 넓이 우선 탐색
2.2.1. 넓이우선탐색의 개념
2.2.2. 깊이 우선 탐색의 과정

3. 깊이 우선 탐색과 넓이 우선 탐색의 특징과 응용분야
3.1.깊이 우선 탐색과 넓이 우선 탐색의 특징과 차이점
3.2.깊이 우선 탐색과 넓이 우선 탐색의 응용분야

본문내용

1.1. 그래프 탐색 기법에 대한 이해의 필요성
본 레포트는 이산수학의 수강생 중 그래프에 대한 입문자를 대상으로 하여 그래프 탐색 기법의 이해에 도움을 주고자 함에 목표를 두고 있다. 이를 위해 세 가지의 세부 목표로 나누어 본 레포트를 진행하고자 한다. 첫째, 그래프 탐색 기법의 필요성에 대해 이해한다. 둘째, 그래프 탐색 기법의 종류 중 대표적인 방법이라 할 수 있는 깊이 우선 탐색과 넒이 우선 탐색의 개념에 대해 이해한다. 셋째, 깊이 우선 탐색과 넓이 우선 탐색의 응용분야와 두 방법의 차이를 이해하여 필요 목적에 따라 적절히 선택하고 이를 활용한다.
그래프의 모든 노드를 방문하는 것을 그래프 탐색이라고 한다. 하나의 노드로부터 시작하여모든 노드들을 차례대로 한 번씩 방문하는 것이다. 예를 들어 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지, 혹은 특정 도시에서 다른 도시로 갈 수 있는지 없는지를 그래프 탐색을 통해 구할 수 있다. 오늘날 4차 산업혁명 시대를 맞이하여 컴퓨터의 활용가치가 높아짐에 따라 각종 알고리즘의 응용분야에서 그래프의 중요도가 높아지고 있다. 특히 이에 대한 전문 지식을 탐구하는 공과대학의 전공자들은 그래프에 대한 이해를 바탕으로 다양한 알고리즘 관련 문제들을 해결하고 연구해나가는데 필요한 창의력을 갖출 수 있을 것이다.

1.2. 스택과 큐의 소개
그래프 탐색 기법 중 깊이 우선 탐색과 너비 우선 탐색에 대해 잘 이해하기 위해서 이것의 기본이 되는 자료구조인 스택(Stack)과 큐(Queue)에 대한 이해가 선행되어야 한다. 자료구조란 단어 그대로 자료를 표현하고 자료를 표현하고 이를 처리하는 방법을 의미한다.

1.2.1. 스택의 개념
먼저 스택(stack)은 모든 원소들의 삽입(insert)과 삭제(delete)가 리스트의 한쪽 끝에서만 수행되는 제한 조건을 가지는 선형 자료 구조(linear data structure)로서, 삽입과 삭제가 일어나는 리스트의 끝을 top이라 하고, 다른 한쪽 끝을 bottom이라 한다.

참고 자료

전산용어사전편찬위원회, 『컴퓨터 인터넷 IT용어 대사전』, 일진사, 2005
김대수, 『4차산업혁명 시대의 이산수학』, 생능출판, 2019
정순석, “이산수학의 필요성”, 충청매일, 2019.02.13, 1p
안경잡이개발자, 15. 너비우선탐색, 안경잡이개발자 네이버 블로그, https://m.blog.naver.com/ndb796/221230944971
Reakwon, 알고리즘 : 그래프 이론 그림으로 보는 BFS 기본, 개념, 설명, reakwon 티스토리,
https://reakwon.tistory.com/7?category=300867
_Shin, 깊이우선 탐색(DFS), 넓이우선 탐색(BFS), _Shin 티스토리,
https://devshin.tistory.com/entry/%EA%B9%8A%EC%9D%B4%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS-%EB%84%93%EC%9D%B4%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89BFS