bdfgdfg

깊이 우선 탐색(Depth First Search : DFS) 이름에서 알 수 있듯이 깊이를 우선하여 탐색한다. 즉 탐색의 진행 방향에 있어서 순서상으로 만나는 정점을 대상으로 바로 탐색을 진행한다. 그러다가 더이상 탐색을 진행할 곳이 없다면 이때까지 방문했던 녀석들을 하나씩 돌아가면서 다른 정점을 방문할 수 있는지 체크한다. 우선 DFS의 과정을 그림으로 살펴본다. 위 그림에서도 보이듯이 탐색의 진행이 한 길을 깊이 파고든다. (누구를 먼저 선택할 것인지에 대한 것은 구현하는 이가 결정) 그러다가 그림 3에서 길이 막힌다면 역으로 돌아가면서 수정->정희->민석까지 돌아가다가 아직 방문안한 지율을 방문하고 다시 시작점으로 돌아간다. (시작점으로 돌아가는 이유는 방문안한 녀석들을 돌아오면서 다시 다 체크하..

그래프와 관련된 용어 위 그림과 같이 그래프에서는 정점(vertex)는 연결의 대상이 되는 개체 또는 위치. 간선은 그들 사이의 연결(다리)이다. 더 간단한 그림의 예시를 본다. 다음은 비상연락망 구조를 표현한 그래프. 위의 그래프에서는 방향성이 빠져있다. 이렇듯 그래프의 연결 관계에 있어서 방향성이 없는 그래프를 가리켜 '무방향 그래프'라고 한다. 그리고 위와 같이 간선에 방향정보가 포함되어 있으면 '방향 그래프' 가중치 그래프와 부분 그래프 다음 그림에서 보이듯 간선에 가중치 정보를 넣을 수 있다. 이러한 형태의 그래프를 가리켜 가중치 그래프라 표현한다. 이 때 가중치가 되는 값은 다양하게 설정할 수 있다. 예로들어 1. A정점에서 B정점까지 걸리는 '시간' 2. A정점에서 B정점까지 걸리는 '거리'..

충돌 문제의 해결책 일반적으로 충돌의 해결책이란 것이 상식적인 선에서 벗어나지 않는다고 한다. 예를 들어 충돌이 발생하면 충돌이 발생한 그 자리를 대신해 빈 자리를 찾아야 한다. 다만 그 빈 자리를 찾는 방법에 따라서 해결책이 구분될 뿐. 1. 선형 조사법과 이차 조사법 선형 조사법 - 충돌이 발생했을 때 그 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장하는 것이 바로 '선형 조사법' 예를 들어 밑의 그림과 같이 key % 7의 해시값을 구하는 해시 함수가 있다. 1. 키가 9인 데이터는 해시 값이 2(9 % 7 -> 2)이므로 인덱스 2에 저장이 된다. 2. 이어서 키가 2인 데이터가 등장. 2 % 7 -> 2이므로 인덱스 2에 저장이 할려하지만 이미 9가 저장이 되었기에 충돌! 3. ..

해시 테이블 탐색에 있어 매우 빠른 결과를 보여주는 자료구조이다. -> 탐색의 시간 복잡도는 O(1). 즉 내가 찾고자 하는 대상을 한번에 찾아내는 방식. C++에서도 STL 컨테이너에서 제공하는 해시테이블이 존재한다. -> std::unordered_map(Key-Value), std::unordered_set(Key) 참고로 앞서 배운 이진 탐색 트리의 컨테이너는 std::map(Key-Value) 테이블(Table) 위 그림이 테이블. 자료구조 관점에서 위 그림 처럼 저장되는 데이터가 키(key)와 값(value)이 하나의 쌍을 이뤄야 테이블이라 한다. 그렇기에 테이블에 저장되는 모든 데이터들은 이를 구분하는 '키'가 있어야 데이터를 구분하는 기준이 된다. 그렇기에 테이블은 키와 관련해 다음과 같은..