15. 자바와 자료구조

1. 자료구조

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

1. 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현방법들

2. 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨

3. 자료의 효율적인 관리는 프로그램의 수행 속도와 밀접한 관련이 있음

4. 여러 자료구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 하므로 자료구조에 대한 이해가 필요

2. 선형 자료구조

한 줄로 자료를 관리한다.

1. 배열(Array)

선형으로 자료를 관리, 정해진 크기의 메모리를 먼저 할당 받아 사용함 -> 자료의 물리적 위치와 논리적 위치가 같음

2. 연결 리스트(LinkedList)

선형으로 자료를 관리, 자료가 추가될 때마다 메모리를 할당 받고, 자료는 링크로 연결됨 -> 자료의 물리적 위치와 논리적 위치가 다를 수 있음

3. 스택(Stack)

가장 나중에 입력 된 자료가 가장 먼저 출력되는 자료 구조(Last In First Out) -> 지역 변수는 스택 메모리에 저장

4. 큐(Stack)

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

3. 트리 (Tree)

부모 노드와 자식 노드간의 연결로 이루어진 자료구조       

(jdk 클래스 -> TreeSet, TreeMap(Tree로 시작되는 클래스는 정렬을 지원)

1. 힙(heap)                     

Priority queue를 구현(우선 큐)                       

Max heap

부모 노드는 자식  노드보다 항상 크거나 같은 값을 가지는 경우

Min heap                

부모 노드는 자식 노드보다 항상 작거나 같은 값을 가지는 경우                    

2. 이진 트리(heap)

부모 노드에 자식 노드가 두 개 이하인 트리             

3. 이진 검색 트리

검색이 목적인 트리

1. 자료의 중복을 허용하지 않는다.

2. 왼쪽 자식 노드는 부모 노드보다 작은 값, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가짐

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

4. inorder traversal 탐색을 하게 되면 자료가 정렬되어 출력됨 -> (노드 기준 왼쪽을 보고 이후 부모를 본 후 오른쪽을 본다.)

4. 그래프

정점과 간선들의 유한 집합 G = (V, E)

정점(vertex)

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

간선(edge)

객체들의 연결 관계를 나타냄(링크)

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

그래프를 구현하는 방법

-> 인접 행렬, 인접 리스트

그래프를 탐색하는 방법

-> BFS(너비 우선 탐색), DFS(깊이 우선 탐색)

5. 해싱(Hashing) 

자료를 검색하기 위한 자료 구조

1. 키(key)에 대한 자료를 검색하기 위한 사전(dictionary) 개념의 자료 구조 -> key는 유일!! 이에 대한 value를 쌍으로 저장!

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

-> 특정 함수를 나누기 했을 때 나머지 값의 위치에 넣는다거나 이런식의 함수 사용(인덱스는 순서와 무관함)

3. 해시 함수에 의해 인덱스 연산이 산술적으로 가능 -> O(1)

4. 저장되는 메모리 구조를 해시테이블이라한다.

왼쪽이 기본 해시테이블 그러나, 해시테이블은 안쓰는 공간이 발생할 수 있다.

그러므로 오른쪽 그림처럼 링크드 리스트를 이용한 체이닝을 이용함(다만 체이닝은 구현이 많이 복잡해) 

 

아직 나 또한 자료구조 및 알고리즘 공부를 많이 한 게 아니기에.. 이 부분은 찬찬히 진행해 보도록 하겠다!!