응파카 성장일지

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의 주소를 저장한다. 따라서..

여러 데이터를 그룹화 해서 element로써 관리하기 위한 자료구조 Array Array 선언 시 고정된 크기의 메모리를(길이를) 할당한다. 선언시 정해진 메모리(길이)는 변하지 않는다. Array는 같은 자료형의 element만 포함할 수 있다. Array의 index는 각 value에 대한 유일한 식별자이다. (0부터 시작) 단순히 몇 번째인지를 나타내는 List의 index와는 다르다. 이 고정된 index를 사용해서 데이터에 대한 빠른 접근과 수정이 가능하다. (시간복잡도 O(1) ) Array 중간의 데이터를 삭제하면 삭제된 데이터의 index 위치에 그대로 빈 메모리가 생긴다. (메모리 낭비) 빈 메모리를 없애기 위해서는 빈 곳의 index+1 부터 한 칸씩 앞으로 재할당해줘야한다. Array..