자료구조 정리

------------------------------------------------------------------------------

1. 자료구조 기초 
1-1 Array 배열 
- 배열은 인덱스를 가지고 있다. 순차적으로 데이터 삽입, 삭제되는 형태의 자료구조 
- 데이터를 순차적으로 삽입, 삭제할때 가장 효과적
- 인덱스를 사용하기 때문에 검색이 빠르다. 
- 중간 삽입 삭제가 어렵다. 
- 배열의 길이를 바꿀 수 없다. 가변 배열은 리소스 낭비가 크다. 
- 배열은 인덱스에 따라 값을 유지하기에 엘리먼트가 삭제되어도 빈자리가 남는다. ( 불필요 메모리 차지 ) 
- 삭제한 데이터를 뒤에 위치한 엘리먼트로 메꾸면 데이터 순서에 따라 빈틈없이 연속적 배치 가능 - > 리스트라 한다. 

------------------------------------------------------------------------------

1-2  List 리스트
리스트는 배열이 갖는 인덱스 구조의 장점을 버린 대신 빈틈을 없애는 방법을 선택하였다. 따라서 데이터의 삽입, 삭제에 대한 데이터 낭비는 줄고, 검색 시간이 길어졌다는 특징 
- 빈틈없는 데이터 적재
- 순서가 있는 데이터의 모임 
- 리스트에서 인덱스는 몇번째 데이터인가 정도
- 순차성을 보장하지 않는다. 

1-2-1 Array List 순차 리스트
- 내부적으로 배열을 사용하기 때문에 인덱스를 이용하여 데이터에 접근이 가능하다.
- 데이터의 조회 속도 증가/ 데이터를 추가하거나 삭제하면, 각 순서가 일정하게 변경되어야 한다. 삽입과 삭제에 오랜시간 소요된다. 

1-2-2 Linked List 연결 리스트
- 배열을 사용하지 않고, 하나의 데이터에 다음 엘리먼트의 위치정보를 포함한다. 
- 특정 데이터를 조회하는 인덱스가 존재하지 않기 때문에 조회 속도가 느리다. 
- 데이터의 추가, 삭제시에 다른 데이터의 영향을 주지 않는다. -> 상대적으로 빠르다.
- 노드:데이터 + 포인터 (주소)
- 포인터: 각 노드안에서 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

두 리스트는 장담정을 가지고 있다.-> 고정된 데이터의 검색이 필요하면 Array List 사용, 검색이 필요없는 가변적 데이터가 필요한 경우 Linked List를 사용

------------------------------------------------------------------------------

1-3 Queue 큐 
- 큐는 선형 리스트에서 한쪽에서는 삽입 작업이 이루어지고, 다른 한쪽에서는 삭제가 이루어지도록 구성한자료구조이다. 
- 가장 먼저 삽입된 자료가 가장 먼저 출력되는 선입선출 방식으로 처리한다. 
- 가장 먼저 삽입된 자료의 기억공간을 가리키는 포인터로 삭제 작업이 이루어지는 Front 포인터
- 가장 마지막에 삽입된 자료가 위치한 기억장소를 가리키는 포인터로 삽입 작업이 이루어지는 Rear 포인터 
- Queue 는 순서를 기다리는 대기 행렬 처리에 사용되거나 운영체제의 작업 스케줄링에 사용된다. ( ex // 줄 서서 기다리기, 버퍼 )
- 먼저 들어간 정보가 먼저 나오고, 나중에 들어간 정보가 나중에 나온다. 
- 일반적인 큐는 선형이지만, 크기가 제한되어있다. 빈공간 사용하려면 모든 자료 꺼내거나 자료를 한칸 씩 옮겨야 한다는 단점이 있다
- 이를 해결하려면 순환큐, 선형큐가 있다.  

1-3-1 Liner Quere 선형 큐
- 선형 큐는 큐의 삭제가 이루어질대마다 큐의 원소들을 각각 왼쪽으로 다시 당기는 형식이다. 
- 무수히 이행되도 실제용량을 고정이다. 
- 한번 삭제가 이루어질 때마다 모든 배열의 원소를 옮기는 것으로 너무 비효율적이다. 최악의 자료구조이다. 
1-3-2 Circular Queue 순환 큐
- 후단이 배열의 맨 끝에 있을 때 삽입이 되면 배열의 첫부분으로 정보를 삽입하는것이다.
- 순환 링크트 리스트처럼 배열의 끝과 시작의 구분이 없어지는 것이다.
- 삽입 삭제가 빠르고, 용량은 고정되지만 함수구현이 까다롭다.
- 큐를 유연하게 사용하기 위해 배열의 시작과 끝이 경계선을 모호하게 만든다.
- 공백상태와 1개의 데이터가 있는 상태를 구별하기 위해 후단의 위치를 마지막 데이터 다음 공간으로 한다. 
- 공백 상태와 가득참상태를 구별하기 위해 실제 사용할 공간보다 더미노드를 위한 노드를 한개 더 선언한다. 

- 연결리스트는 자료들을 임의의 기억공간에 기억시키되 자료 항목의 순서에 따라 노드의 포인터 부분을 서로 연결시킨 구조 
- 연결을 위한 포인터 부분이 필요하기에 순차 리스트 

1-3 Queue 큐 
1-4 Stack 스택
1-5 Deque 데크 
1-6 Graph 그래프
1-7 Tree 트리 

이중에 선형구조(순차적)는 배열, 리스트, 큐, 스택, 데크 
비선형구조는 그래프, 트리
------------------------------------------------------------------------------

1-4 Stack 스택
- 스택은 리스트의 한쪽 끝으로만 자료의 삽입 삭제가 이루어진다. 
- 스택은 가장 마지막에 들어온 데이터부터 빠져나가는 후입선출 방식이다. (LIFO)
- 스택의 가장 마지막 삽입 위치를 가르키는 TOP/SP(StackPointer)
- 스택의 가장 밑 바닥을 나타내는 Bottom
- 스택의 자료 입력 명령어인 PUSH
- 스택의 자료 출력 명령어인 POP이 있다.

스택의 쓰임새를 알려면 프로그램, 운영제체, 메모리공간 알 필요가 있다. 

- 코드 영역, 데이터 영역, 스택 영역, 힙 영역 
- 스택의 용도는 대략 7가지 정도가 있다.
1. 부 프로그램 호출 시, 복귀주소를 저장할 때
2. 함수 호출의 순서 제어
3. 인터럽트가 발생하여 복귀주소를 저장할 때, 
4. 후위 표기법으로 표현된 산술식이 연살할 때
5. 0주소지정방식 명령어의 자료 저장소 
6. 컴파일러를 이용한 언어 번역 시, 
7. 재귀 프로그램의 순서 제어

------------------------------------------------------------------------------

1-5 Deque 데크 
- 데크는 Stack과 Queue의 장점을 빼서 따로 구성된 자료구조로, 삽입 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료구조이다.
- 입력이 한쪽으로만 발생하고 출력은 양쪽에서 일어날 수 있는 입력 제한, 입력 제한 데크: Scroll 
- 입력은 양쪽에서 일어나고 출력은 한쪽에서만 이루어지는 출력 제한이 있다. 출력 제한 데크 Shelf 

------------------------------------------------------------------------------

1-6 트리 
- 트리를 정점(node)와 (branch)를 이용하여 사이클로 이루어지지 않도록 구성된 그래프의 특수한 형태이다. 
- 트리는 계층 모델로 노드가 N개인 트리는 항상 N-1의 가지를 갖는다.
- 또한 루트에서 어떤 노드로 가는 경로는 유일하다. 트리의 순회는 Pre-order, In-Order, Post-Order로 이루어진다.
- 노드(Node) 트리의 기본 요소, 자료 항목과 다른 항목에 대한 가지를 합친 것. 
- 가지(Branch Edge) 노드와 노드를 연결하는 간선
- Root Node 트리의 맨 위에 있는 노드이다.
- 차수, Degree 각 노드에서 뻗어나온 가지의 수, 
- 트리의 차수 : 노드들의 차수 중에서 가장 많은 수를 의미

- 단말 노드 ( Terminal node = leaf node ) - 자식이 하나도 없는 노드이다.
- 비단말 노드 ( Non-Terminal Node) - 자식이 하나라도 있는 노드이다.
- 자식 노드 ( Children Node) : 어떤 노드에 연결된 다음 레벨 노드들을 의미한다.
- 부모노드 ( Parent Node) : 동일한 부모를 가지는 노드를 의미한다.  
- 형제노드 ( Sibiling) : 동일한 부모를 갖는 노드를 의미한다. 
- Level 루트 노드의 레벨을 1로 가정한 후 어떤 레벨이 L이면 자식 노드는 L+1이다.
- 깊이 Depth, Height : 어떤 트리에서 노드가 가질 수 있는 최대 레벨을 의미

트리 종류는, 일반 트리, 이진 트리, 완전 이진트리, 균형 이진트리, 포화 이진트리, 균형 트리 등으로 되어있다. 
1-6-1 Binary Tree 이진 트리 
- 각 노드가 최대 두개의 자식을 가지는 트리이다. 모든 트리가 이진 트리는 아니다. 
- 이진 트리의 순회는 중위 순회 ( left - 현재 - right ), 전회 순회 ( 현재 - left - right ), 후위 순회 ( left - right - 현재 ) 가 있다. 
- 이진 탐색 트리는 모든 노드가 모든 왼쪽 자식들 <= n <= 모든 오른쪽 자식들의 특정 순서를 따르는 이진 트리이다. 
1-6-2 Complete Binary Tree 완전 이진 트리 
- 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리이다. 
1-6-3 Full Binary Tree 균형 이진트리 
- 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다. 
1-6-4 Perfect Binary Tree 포화 이진트리
- 균형 이진트리이면서 완전 이진트리로, 모든 단말노드는 같은 높이에 있어야 하며, 모든 내부 노드가 두개의 자식노드를 갖는다.
1-6-5 B-Tree 
- 레드블랙트리 AVL 트리가 이 일종이며 시간 복잡도 O(logN)에 삽입, 찾기 등을 무리없이 가능한 균형 잡힌 트리이다. 

트리의 쓰임새는 다양한데, 정렬에서 Heap 정렬 등이 쓰이는 최소 힙 ( 부모노드 <= 자식노드, 오른차순)과 최대 힙 ( 부모노드 >= 자식노드, 내림차순 ) 또한 완전 트리구조로 되어있다.

------------------------------------------------------------------------------

1-7 Graph 그래프 
-그래프는 단순히 노드와 그 노드를 연결하는 간선을 하나로 모아놓은 자료구조이다. 
즉, 연결되어 있는 객체 간의 관계를 표현 할 수 있는 자료구조이다. 
- 그래프는 노드와 다르게 루트 노드 개념과 부모 자식 관계가 없다. 2개 이상의 경로가 가능하며, 순회는 DFS와 BFS로 이루어진다. 
- 간선의 유무는 그래프에 따라 다르며 간선에 따라 Weight 가중치를 매길 수 잇다. 
- 정점 ( Vertex, Node ) 데이터의 위치를 나타내는 개념이다.
- 간선 ( Edge, Branch ) 노드를 연결하는 선이다.
- 인접 정점 ( Adjacent Ventex) 간선에 의해 직접 연결된 정점이다. 
- 노드의 차수 ( Degree ) 무방향 그래프에서 하나의 정점에 인접한 정점의 수이다.
- 진입 차수 ( in-degree) 방향 그래프에서 외부에서 오는 간선의 수이다. 
- 진출 차수 ( out-degree ) 방향 그래프에서 외부로 향하는 간선의 수이다.
- 결로의 길이 : 경로를 구성하는데 사용된 간선의 수이다. 
- 단순 경로 : 경로 중에서 반복되는 정점이 없는 경우를 의미한다. 

그래프의 종류는 크게 무방향 그래프, 방향 그래프, 가중치 그래프, 연결 그래프와 비연결그래프, 순환 그래프와 비순환 그래프, 완전 그래프 등으로 구성되어 있다. 

이를 구분하기 위해서는 오일러 경로( Eulerian Tour )의 개념을 알고 있어야 한다. 
오일러 경로란, 그래프에 존재하는 모든 간선을 한번만 통과하면서 처음 정점(Vertex)으로 되돌아오는 경로를 의미한다. 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다. 

1-7-1 가중치 그래프
- 간선에 비용이나 가중치가 할당된 그래프이다.
1-7-2 무방향 그래프
- 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다. 정점 A와 정점 B를 연결하는 간선은 (A,B) 혹은 (B,A)와 같이 정점의 쌍으로 표현한다. 
1-7-3 방향 그래프
-  간선에 방향성이 존재하는 그래프이다. 
- A->B로만 갈 수 있는 간선은 <A,B>로 표시한다. 무방향 그래프와 다르게 <B,A>로 나타낼 수 없다. 즉, <A,B><B,A>는 다른 의미이다. 
1-7-4 비연결 그래프
- 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 그래프이다.
1-7-5 연결 그래프
- 무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우이며 트리가 이에 해당된다. 
1-7-6 비순환 그래프
- 사이클이 없는 그래프이다.
1-7-7 순환 그래프
- 단순 경로의 시작 정점과 종료 정점이 동일한 그래프이다. 
1-7-8 완전 그래프
- 그래프에 속해 있는 모든 정점이 서로 연결되어있는 그래프이다.( 무방향 완전 그래프의 정점 수(n)일 때, 간선의 수를 구하는 공식 (n*(n-1)/2)

------------------------------------------------------------------------------