bdfgdfg

최소 비용 신장 트리 트리는 그래프의 한 유형. 다음 그래프를 보고 정점 B에서 정점 D에 이르는 모든 경로를 찾아서 열거해본다. 이렇게 두 개의 정점을 잇는 간선을 순서대로 나열한 것을 가리켜 '경로'라 한다. 그리고 위의 네 경로와 같이 동일한 간선을 중복하여 포함하지 않는 경로를 가리켜 '단순 경로'라 한다. 단순 경로가 아닌 예를 들어보면 B-A-C-B-A-D -> B와 A를 잇는 간선이 두 번 포함됨. 그렇다면 A-B-C-A는 단순 경로가 일까? 단순 경로가 맞다. A정점이 두 번 등장하지만 중복된 간선이 포함되지 않기 때문이다. 이렇게 단순 경로이면서 시작과 끝이 같은 경로를 가리켜 '사이클'이라 한다. 간단히 말해 사이클은 어느 정점에서 다른 경로를 통해 다시 돌아올 수 있다면 사이클이라 한..

깊이 우선 탐색(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. ..