자료구조
-
Data Structure - Hash Table(해시 테이블)Programming/Data Structure(자료 구조) 2019. 4. 7. 18:26
- Hash Table(해시 테이블) - Hash Table(해시 테이블)의 정의 - 해시함수를 사용하여 키를 해시값으로 매핑하고 이 해시값을 index(주소)로 삼아 데이터의 값(value)을 키(index)와 함께 저장하는 자료구조 - 데이터가 저장되는 곳을 버킷(buckey)이라고 부른다 - 해시 테이블의 기본 연산은 삽입, 삭제, 탐색이 있다 //다른 내용은 추후 추가 예정
-
Data Structure - Graph(그래프)Programming/Data Structure(자료 구조) 2019. 4. 7. 18:17
- Graph(그래프) - Graph(그래프)의 정의 - 노드(node)와 그 노드의 연결선인 엣지(edge)를 모아 놓은 자료 구조 - 연결되어 있는 객체간의 관계를 표현하기 위한 자료 구조 - 계층 관계인 트리와는 다르게 네트워크 관계이다 Graph(그래프)와 Tree(트리)의 차이 Graph(그래프)의 특징 - 네트워크 모델이다 - 2개 이상의 경로가 가능하다 - 트리처럼 root라는 개념이 없다 - 부모 - 자식 관계가 없다 Graph(그래프)의 탐색 방법 1. DFS(깊이 우선 탐색) - 그래프의 시작 정점에서 출발하여 먼저 시작 정점 v를 방문하였다고 표시한다. v에 인접한 정점들 중 아직 방문하지 않은 정점 u를 선택한다. - 만약 그러한 정점이 없다면 탐색은 종료한다 - 만약 아직 방문하지..
-
Data Structure - Tree / Binary Search TreeProgramming/Data Structure(자료 구조) 2019. 4. 7. 17:48
- Tree - Tree(트리)의 정의 트리는 노드로 이루어진 자료구조 최상위 노드는 루트(root) 노드라고 정의한다 노드와 노드를 연결하는 선을 edge(엣지 or 링크) 라고 정의한다 트리는 비선형 자료구조로 계층적인 관계를 가지고있다 (ex. Directory 구조) 트리는 그래프의 일종으로 사이클이 존재하지 않는 DAG(Directed Acyclic Graph), 즉 방향성이 있는 비순환 그래프의 일종이다 Tree(트리)의 특징 루트 노드는 0개 이상의 자식 노드를 갖는다 자식 노드 또한 0개 이상의 자식 노드를 갖는다 부모 노드가 없는 노드는 최상위 노드(root)이다 최상위 노드에서 임의의 노드로 가는 경로는 유일하다 (다른 임의의 노드 간의 경로도 유일하다) 자식 노드는 한개의 부모 노드만..
-
Data Structure - Stack / Queue / Linked List 정리Programming/Data Structure(자료 구조) 2019. 4. 4. 23:06
- Stack - Stack의 정의 - 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다.- 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸시(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 보관한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다. -> wiki pedia 출처 Stack의 대표 연산 - top(): 스택의 가장 윗 데이터를 넘겨준다.만약에 비었다면 이..