-
[JAVA/자료구조] 자료구조(Data Structure)Language/Java 2021. 6. 8. 12:56
자료구조란?- 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현 방법이다.
- 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 된다.
- 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있다.
- 여러 자료구조 중 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야하므로 자료구조에 대한 이해가 중요하다.
자료구조 종류
- 배열(Array)
- 선형으로 자료를 관리, 정해진 크기의 메모리를 먼저 할당받아 사용한다.
- 자료의 물리적 위치와 논리적 위치가 같다. - 연결 리스트(LinkedList)
- 선형으로 자료를 관리, 자료가 추가될 때마다 메모리를 할당 받고 자료는 링크로 연결된다.
- 자료의 물리적 위치와 논리적 위치가 다를 수 있다. - 큐(Queue)
- 가장 먼저 입력 된 자료가 가장 먼저 출력되는 자료구조
- First In First Out - 스택(Stack)
- 가장 나중에 입력 된 자료가 가장 먼저 출력되는 자료구조
- Last In First Out - 트리(Tree)
- 부모 노드와 자식 노드간 연결로 이루어진 자료구조
- 이진트리: 부모노드에 자식 노드가 두 개 이하인 트리 - 힙(heap)
- Priority queue를 구현(우선 큐)
- Max heap: 부모 노드는 자식 노드보다 항상 크거나 같은 값을 갖는 경우
- Min heap: 부모 노드는 자식 노드보다 항상 작거나 같은 값을 갖는 경우
- heap정렬에 활용할 수 있다. - 이진 검색 트리
- 자료의 중복을 허용하지 않는다.
- 왼쪽 자식 노드는 부모 노드보다 작은 값, 오른쪽 자식 노드는 부모 노드보다 큰 값을 갖는다.
- 자료를 검색하는데 걸리는 시간이 log(n)이다.
- inorder traversal탐색을 하게 되면 자료가 정렬되어 출력된다. - 그래프(Graph)
- 정점과 간선들의 유한 집합 G = (V,E)
- 정점(vertex): 여러 특성을 가지는 객체, 노드(node)
- 간선(edge): 이 객체들의 연결 관계를 나타냄, 링크(link)
- 간선은 방향이 있는 경우와 없는 경우가 있다.
- 그래프를 구현하는 방법: 인접 행렬과 인접 리스트
- 그래프를 탐색하는 방법: BFS(bread first search), DFS(depth first search) - 해싱(Hashing)
- 자료를 검색하기 위한 자료구조
- 키에 대한 자료를 검색하기 위한 사전 개념의 자료구조
- Key는 유일하고 이에 대한 value를 쌍으로 저장한다.
- index = h(key): 해시 함수가 key에 대한 인덱스를 반환해줌 해당 인덱스 위치에 자료를 저장하거나 검색하게 됨
- 해시 함수에 의해 인덱스 연산이 산술적으로 가능 => O(1)
- 저장되는 메모리 구조를 해시 테이블이라 한다.
- jdk클래스: HashMap, Properties
'Language > Java' 카테고리의 다른 글
[JAVA] 제네릭(Generic) 프로그래밍 (0) 2021.06.10 [JAVA/자료구조] 배열(Array) (0) 2021.06.08 [JAVA] Object 클래스와 Class클래스 (0) 2021.06.07 [JAVA] 인터페이스(interface) (0) 2021.06.07 [JAVA/디자인패턴] 템플릿 메서드(Template Method) (0) 2021.06.06