Chapter 14. 그래프의 탐색
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 그래프의 탐색은 그 어떤 자료구조보다도 복잡한 편입니다. 그래프는 정점의 구성뿐만 아니라 간선의 연결에도 규칙이 존재하지 않기 때문입니다. 그래서 그래프의 탐색을 위한, 다시 말해서 그래프의 모든 정점을 돌아다니기 위한 별도의 알고리즘 두 가지를 소개합니다. 깊이 우선 탐색 Depgh First Search(DFS) 너비 우선 탐색 Breadgh First Search(BFS) 우선은 깁이 우선 탐색의 방법을 먼저 설명하겠습니다. 아래의 그래프는 앞서 보였던 비상 연락망입니다. 현재 L 학생에게 비상 메시지가 전달되었습니다. 따라서..
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 그래프의 구현 관점에서 무방향 그래프와 방향 그래프의 유일한 차이점은 연결 리스트에 추가하는 노드의 수에 있기 때문에, 이 둘의 구현 방법에는 차이가 없다고 볼 수 있습니다. 굳이 따지자면 무방향 그래프를 구현할 때 연결 리스트에 추가해야 하는 노드의 수가 방향 그래프에 비해 두 배 많기 때문에 무방향 그래프의 구현이 좀 더 복잡하다고 할 수 있습니다. 그래서 무방향 그래프를 대상으로 구현해 보고자 합니다. 헤더 파일은 다음과 같습니다. //ALGraph.h //수정 날짜 : 2021.03.27 //작성자 : KOEY #ifndef..
Chapter 14. 그래프의 이해와 종류
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 어플을 사용하면 버스와 지하철의 노선도를 확인할 수 있습니다. 그리고 출발지와 목적지를 입력하면, 그에 맞는 최적의 경로를 알 수도 있습니다. 이러한 프로그램의 구현에 사용되는 것이 바로 그래프 알고리즘입니다. 그래프 알고리즘은 수학자 '오일러'에 의해 고안되었습니다. 오일러는 1736년도에 그 유명한 '쾨니히스베르크의 다리 문제'를 풀기 위해서 그래프 이론을 사용했다고 합니다. 쾨니히스베르크의 다리 문제에 대해 조금 찾아보면 흥미로울 것입니다. 다음 그림은 어느 초등학교 5학년 3반 학생들의 비상연락망 구조를 표현한 것입니다. 위..
Chapter 13. 충돌(Collision) 문제의 해결책
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 충돌 문제는 테이블의 핵심 주제라고 할 수 있습니다. 충돌 문제를 해결하는 것이 뭔가 특별할 것 같지만 사실 개념 자체는 간단합니다. 만약 충돌이 발생하면, 충돌이 발생한 그 자리를 대신해서 빈자리를 찾는 것입니다. 그리고 빈자리를 찾는 방법에 따라서 해결책이 구분됩니다. 충돌이 발생했을 때 그 해결방법으로 우선 '선형 조사법'과 '이차 조사법'에 대해 설명하겠습니다. 선형 조사법은 충돌이 발생했을 때 그 옆자리가 비어 있는지 확인하고 빈자리에 데이터를 저장하는 방법입니다. 해쉬 함수가 다음과 같이 정의되어 있고, int HashF..