응파카 성장일지

Graph는 Vertex(정점) 과 Edge(간선) 으로 이루어진 자료구조이다. 그래프 관련 용어 차수(Degree) : 정점에 연결된 간선의 수 인접(Adjacent) : 두 정점이 간선으로 연결되어 있는 상태 경로(Path) : 한 정점에서 다른 정점으로 이어지는 간선의 연속 사이클(Cycle) : 경로의 시작 정점과 끝 정점이 동일한 경우 가중치(Weight) : 간선에 할당된 가중치 값을 의미한다 최단 경로(Shortest Path) : 두 정점 사이의 가장 짧은 경로이다. 컴포넌트(Component): 그래프에서 연결된 정점들의 집합을 의미한다. 무향 그래프에서 컴포넌트는 연결 요소(Connected Component)라고도 한다. 이웃(Neighbor): 한 정점과 인접한 정점이다. 강결합(S..

해시 값과 해시 함수 해시 함수 Key를 input으로 주면 output으로 해시값을 도출하는 함수 input = Key output = Hash, Hash Value 해시 함수는 동일한 key에 대해 언제나 동일한 해시값 도출 그 결과인 해시값을 안다고 해도 input을 추측하기는 어렵다. 값이 다른 input이 주어져도 output이 동일 할 수 있다 → ‘해시 충돌 발생 가능’ 해시 테이블 Key-value구조로 데이터를 저장 output인 해시값을 테이블의 인덱스로 사용한다. Key(input) 의 결과 → [해시함수] → hash값(output) output을 인덱스로 갖는 배열 buckets value인 실제 값을 저장하는 entries buckets는 entries의 주소를 저장한다. 따라서..