1. 자료구조
> 선형구조
- 배열, 스택, 큐, 데크
- 선형리스트 : 연속 리스트, 연결 리스트
> 비선형 구조 : 트리, 그래프
> 배열 : 크기와 형이 동일한 자료들이 순서대로 나열된 자료의 집합
> 연속 리스트 : 연속되는 기억장소에 저장되는 자료구조(배열로 구현)
> 연결 리스트 : 자료들을 임의의 기억공간에 기억시키되, 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조(포인터로 구현)
> 스택 : 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조(후입선출: Last In First Out)
> 큐 : 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한 쪽에서는 삭제 작업이 이루어지는 자료구조
(선입선출 : First In First Out)
> 그래프 : 정점(vertex)와 간선(Edge)의 두 집합으로 이루어지는 자료 구조
: 사이클이 없는 그래프를 트리라고 함
- 방향 그래프 : 최대 간선 수 = n(n-1)
- 무방향 그래프 : 최대 간선 수 = n(n-1)/2
2. 트리
> 트리 : 정점(Node), 선분(Branch)를 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수 형태
- 노드 : 트리의 기본요소
- 루트 노드 : 트리의 맨 위에 있는 노드
- 디그리 : 각 노드에서 뻗어나온 가지수
- 단말 노드(잎 노드) : 자식이 하나도 없는 노드(Degree = 0)
- 비단말 노드 : 자식이 하나라도 있는 노드
- 조상 노드 : 근 노드에 이르는 경로상에 이르는 노드들(근 노드 포함)
- 자식 노드 : 노드에 연결된 다음 레벨의 노드
- 부모 노드 : 이전 레벨의 노드
- 형제 노드 : 동일 부모를 갖는 노드
- Level : 근 노드를 level 1로 가정했을 때, 내려온 층 수
- 깊이(Depth) : Tree에서 노드가 가질 수 있는 최대 레벨
- 숲(Forest) : 여러개의 트리가 모여 있는 것
- 트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수
3. 이진트리
> 이진 트리 : 차수가 2 이하인 노드들로 구성된 트리
> 운행법
1) Preorder : 전위순회 > Root -> Left -> Right 순서로 방문
2) Inorder : 중위 순회 > Left -> Root -> Right 순서로 방문
3) Postorder : 후위 순회 > Left -> Right -> Root 순서로 방문
> 수식의 표현(수식을 쓴 뒤 각 항과 연산자가 노드라고 생각)
1) 전위(PreFix) : 연산자 > Left > Right
2) 중위(InFix) : Left > 연산자 > Right
3) 후위(PostFix) : Left > Right > 연산자
> 수식 전환
1) 중위 > 전위, 후위
a) 연산자 우선순위에 따라 괄호로 묶음
b) 연산자를 해당하는 인접한 괄호의 왼쪽 바깥쪽(후위는 오른쪽 바깥쪽)으로 옮김
c) 괄호 제거
2) 전위, 후위 > 중위
a) 인접한 피연산자 두 개와 오른쪽(전위는 왼쪽)연산자를 괄호로 묶음
b) 연산자를 피연산자 가운데로 이동
c) 괄호 제거
4. 정렬(Sort)
> 삽입정렬(Insertion Sort)
- 레코드를 순서에 맞게 삽입시켜 정렬
- 각 위치의 요소들을 첫 번째 위치부터 비교해가며 자리를 조정
> 선택정렬(Selection Sort)
- 최소 값을 찾아 첫 번째 레코드 위치부터 차례로 놓는 과정을 반복
> 버블 정렬(Bubble Sort)
- 인접한 두 개의 레코드 키 값을 비교하여 위치를 교환하는 정렬 방식
> 쉘 정렬(Shell Sort)
- 매개변수의 값으로 서브파일을 구성하고 각 서브파일을 Insertion 정렬 방식으로 순서 배열하는 과정 반복
> 퀵 정렬(Quick Sort)
- 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정 반복
> 힙 정렬(Heap Sort)
- 완전 이진 트리를 이용한 정렬 방식
> 2-Way 합병 정렬(Merge Sort)
- 이미 정렬된 두 개의 파일을 한 개의 파일로 합병
> 기수 정렬(Radix Sort)
- Queue를 이용하여 자릿수 별로 정렬