[자료구조] 자료구조에 대하여

💡 자료구조란 무엇인가? (Data Structure)

• 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현 방법들
• 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨
• 자료의 효율적인 관리는 프로그램의 수행 속도와 밀접한 관련이 있음
• 여러 자료 구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 하므로 자료구조에 대한 이해가 중요함

 

💡 자료구조에는 어떤 것들이 있나?

선형 자료구조 (Linear)

배열 (Array) : 정해진 크기의 메모리를 먼저 할당 받아 사용하고, 자료의 물리적 위치와 논리적 위치가 같음

 

연결 리스트 (LinkedList) : 자료가 추가될 때마다 메모리를 할당 받고, 자료는 링크로 연결됨. 자료의 물리적 위치와 논리적 위치가 다를 수 있음.

스택 (Stack) : 가장 나중에 입력 된 자료가 가장 먼저 출력되는 자료 구조 (Last In First Out)

 

큐 (Queue) : 가장 먼저 입력 된 자료가 가장 먼저 출력되는 자료 구조 (First In First Out)

 

비선형 자료구조 (NonLinear)

트리 (Tree) : 부모 노드와 자식 노드간의 연결로 이루어진 자료구조

힙 (heap) : Priority queue를 구현 (우선 큐)

Max heap : 부모 노드는 자식 노드보다 항상 크거나 같은 값을 갖는 경우

Min heap : 부모 노드는 자식 노드보다 항상 작거나 같은 값을 갖는 경우

이진 트리 (binary tree) : 부모노드에 자식노드가 두 개 이하인 트리

이진 검색 트리 (binary search tree) : 왼쪽 자식 노드는 부모 노드보다 작은 값, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가지는 이진 트리.

자료(key)의 중복을 허용하지 않음.

자료 검색에 걸리는 시간이 평균 log(n)임.

그래프 (Graph) : 정점과 간선들의 유한 집합 G = (V,E)

정점 (vertex) : 여러 특성을 가지는 객체, 노드(node)

간선 (edge) : 이 객체들의 연결 관계를 나타냄. 링크(link)

간선은 방향성이 있는 경우와 없는 경우가 있음

인접 행렬 (adjacency matrix) : 그래프의 연결 관계를 이차원 배열 adj[i][j]로 나타내는 방식.

인접 리스트 (adjacency list) : 그래프의 연결 관계를 vector의 배열 (vector<int> adj[])로 나타내는 방식.

깊이 우선 탐색 (BFS_bread first search) : 최대한 깊이 내려간 뒤, 더 이상 갈 곳이 없을 경우 옆으로 이동하는 그래프 탐색 방법

넓이 우선 탐색 (DFS_depth first search) : 최대한 넓게 이동한 뒤, 더 이상 갈 곳이 없을 경우 아래로 이동하는 그래프 탐색 방법

해싱 (Hashing) : 자료를 검색하기 위한 자료구조

검색을 위한 자료 구조.

키(key)에 대한 자료를 검색하기 위한 사전(dictionalry) 개념의 자료 구조.

key는 유일하고, 이에 대한 value를 쌍으로 저장.

index = h(key) : 해시 함수가 key에 대한 인덱스를 반환해줌. 해당 인덱스 위치에 자료를 저장하거나 검색하게 됨.

해시테이블 (hash table) : [key, value]로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있다.

내부적으로 배열(버킷)을 사용하여 데이터 저장

체이닝 (chaining) : 해시테이블과 유사한 형태로 버킷 내에 연결리스트를 할당하여 버켓에 데이터를 삽입하는 자료구조이다.

연결리스트로 데이터들을 연결하기 때문에 해시 충돌이 발생하지 않음.

연결리스트에 데이터를 계속 추가해도 주소값을 바뀌지 않음.