이론/자료구조
그래프(graph)
목차 그래프의 정의 그래프의 분류 그래프의 표현 그래프와 BFS 그래프와 DFS 1. 그래프의 정의 자료구조에서 의미하는 그래프는 다음과 같은 형태이다. 점을 정점(vertex/node)라고 부르고 점을 이어주는 선을 간선(edge)라고 부른다. 그리고, 각 정점에 연결되어있는 간선의 갯수를 차수(degree)라고 한다. 2. 그래프의 분류 - 무방향그래프와 방향그래프 위의 그림과 같이 그래프를 분류할 수 있다. 그래프의 간선에 방향이 없을 경우 무방향 그래프(undirected graph)라고 부르고, 아래와 같이 방향이 있을 경우에는 방향 그래프(directed graph)라고 한다. 이때, 방향 그래프에서 정점에서 나가는 간선의 수를 outdegree, 들어오는 간선의 수를 indegree라고 한다..
해쉬(Hash)
1. 해쉬(Hash) - 해쉬란? 해쉬란 임의의 크기의 데이터(Key)를 고정된 크기의 값(Value)로 바꾸어 저장하는 것. Key에 대한 Value를 구하는 과정을 해싱(Hashing)이라고 하고, 이 때 사용하는 함수가 해쉬 함수이다. 해쉬 함수를 이용해서 변환한 값을 인덱스로 하여 key와 value를 저장하는 자료구조를 해쉬 테이블이라고 한다. Value 자체를 인덱스로 사용하기 때문에 시간복잡도는 O(1)이다. 위의 내용은 해쉬에 대한 간단한 내용 정리이다. 아는 사람이 보면 쉽지만, 모르는 사람이 보면 무슨 소리인가 싶은 말들이다. 그래서 예시를 들어 설명해보겠다. 다음과 같이 N개의 카드번호와 사람의 성이 적혀있는 데이터가 있다고 할 때, 카드번호가 주어지면 그에 맞는 사람을 찾아내는 시간..