==========================================================================================================================
* 자료추상 - 연산의 대상이 되는 자료를 추상화
1) 기본적추상 : 컴퓨터안에 저장된 자료값을 추상화
2) 구조적추상 : 연관된 자료값들의 집합을 추상화
3) 단위추상 : 단위 프로그램 전체에 대한 추상
* ADT(Abstract Data Type : 추상 자료형)
=> 프로그램의 제어보다 자료에 관심을 두고 자료구조 및 그와 관련된 연산들로 구성된 모듈을 작성하여 정수나 실수형과 같은
하나의 자료형으로 취급할 수 있는것
1) 조건 : 자료형과 연산에 대한 정의가 한 곳에서 가능(캡슐화와 정보은폐)
2) 구현방법 : 자료와 그와 관련된 연산들의 특징을 기술 - 이미 존재하는 자료형으로 기술된 내용 구현 - 내용과 구현결과 비교
* 매개변수 전달방법
1) Call by Value : 메인프로그램에서 서브 프로그램을 호출하여 실행할때 변수값을 넘겨주는 것
2) Call by Name : 메인프로그램에서 서브 프로그램을 호출하여 실행할때 변수 자체를 넘겨주는 것
3) Call by Reference : 실 매개변수의 주소를 서브 프로그램에 전달하는 방법
* 알고리즘 : 주어진 문제를 해결하기 위한 수행과정을 논리적으로 표현한것
=> 한 입력에 대해 그 이상의 출력을 생성하고 종료해야한다.
=> 알고리즘 조건 : 입력(외부로부터 자료입력받을 수 있음), 출력(최소 한가지 이상 출력이 있어야함), 명확성(모든 명령은 명확해야),
유한성(반드시 종료되야), 효율성(실행가능해야)
=> 분석대상 : 작업량, 점유공간, 단순성, 정확성, 최적성
==========================================================================================================================
* 선형구조 : 자료를 연속된 저장공간에 순서대로 기억시킬 수 있는 구조
1) 배열(Array) : 크기와 성격이 동일한 기억장소가 메모리에 연속적으로 할당되어 데이터를 기억하는 자료구조
=> 종류 : (1) 1차원배열 : 메모리에 같은 크기의 기억장소가 연속으로 할당되며 첨자가 하나
(2) 2차원배열 : 행과 열을 의미하는 첨자가 2개이고 구분은 행과 열로 하지만 실제 메모리에서는 1차원배열로 기억
=> 행고정 열변환(행은 고정이고 열이 변화하는 순서에 따라 기억 : COBOL, C, PASCAL, PL/I )
=> 열고정 행변환(열은 고정이고 행이 변화하는 순서에 따라 기억 : FORTRAN )
=> 희소행렬 : 많은 원소들이 0 이고 극 소수만 0이 아니여서 기억장소의 낭비가 심함 = > Linked List로 해야..
2) 리스트(LIST) : 자료가 연속적으로 저장되어 있으며 이들 사이에 논리적인 관계를 가지고 있는 자료집합체
2-1) 선형리스트(Linear List) : 데이터들이 기억장소에 연속적으로 저장되어 있는 자료구조를 말함
=> 기억장소의 낭비가 적으나(장점), 삽입,삭제시 데이터 이동회수가 많다(단점).
2-2) 연결리스트(Linked List) : 하나의 노드는 자료부분과 링크부분으로 구성
=> 노드를 연속적으로 저장하지 않아도 되나(장점), 링크부분을 위한 기억장소가 필요(단점)
=> 단순연결리스트 : ㅁ->ㅁ->ㅁ->ㅁ , 마지막 노드는 null로 표현
=> 원형연결리스트 : ㅁ->ㅁ->ㅁ->ㅁ-> 이렇게 마지막 노드가 처음 노드 포인터를 같도록 구성
^-------------
: 어느 노드에서나 다른 노드 접근이 가능하고 임의의 노드 검색시 현재 노드부터 검색가능하나
무한루프에 빠질수 있어 Head Node를 둔다.
=> 이중연결리스트 : ㅁ -> ㅁ -> ㅁ ->ㅁ , 노드가 한개의 데이터부분과 두개의 링크부분으로 구성
<- <- <-
: 양뱡향 검색으로 속도가 빠르나 두개의 링크를 저장한 기억공간이 필요하다.
=> 이중원형연결리스트 : 이중연결과 원형연결의 합체, 최고 좋음(융통성), 복잡성
3) 스택(Stack) : 한 원형리스트의 한쪽 끝 노드에서 모든 삽입, 삭제 작업이 수행되는 선형리스트의 한 형태(LIFO, FILO)
=> 인터럽트 호출, 재귀적호출, 서브프로그램 호출시 복귀주소 저장등에 사용
4) 큐(Queue) : FIFO, 작업스케쥴링, 프린터스풀에 이용 (이동큐, 환형큐)
5) 데크(Deque) : 큐의 양쪽 끝에서 입력과 출력이 가능한 선형리스트, 스택과 큐를 복합한 운영방식
=> 입력제한데크 : 한쪽으로만 입력이 가능(SCROLL)
=> 출력제한데크 : 한쪽으로만 출력이 가능(SHELF)
==========================================================================================================================
* 비선형구조
1) 트리(Tree) : 정점과 연결선으로 형성된 그래프의 특수한 경우(사이클을 형성하지 않고 근노드 갖음)
=> 터미널노드(자식노드가 없음), 차수(가지수), 트리의 차수(차수가 가장큰거), 계층(몇계층)
=> 종류 : (1) 순서트리 : 순서가 중요함 고정된 위치
(2) 비순서트리 : 순서가 중요하지 않음
(3) 닮은 트리 : 구조는 같으나 내용이 다름
(4) 대등한 트리 : 트리구조, 내용이 같은 트리
(5) 이진트리 - 정이진트리, 전이진트리, 사향이진트리
=> 저장법 : 연속 배열 저장법, Linked List 저장법, 일반트리를 이진트리로 변환하는 방법
=> 운행 : (1) Level Order : 동일한 레벨의 노드들을 좌에서 우로 검사
=> 하향식(Top-Down : 루트노드로부터 좌 -> 우)
=> 상향식(Bottom-Top : 마지막레벨에서 좌 -> 우)
(2) Preorder : 루트노드 - 좌 - 우
(3) Postorder : 좌 - 우 - 루트노드
(4) Inorder : 좌 - 루트노드 - 우
(5) Familyorder : 루트노드를 검사후 자노드를 Lever Order하향식으로 검사후 마지막 검사한 노드의 자노드를 검사
2) 그래프(Graph) : 정점의 집합과 정점사이의 관계를 나타내는 연결선의 집합으로 구성
=> 종류 : 방향그래프, 무방향그래프, 완전그래프, 부그래프
=> 그래프 운행 : (1) DFS (Depth First Search) : preorder운행법으로 탐색하며 스택구조를 이용
=> 임의의 시작점 방문 -> 연결된 정점중 방문 안한곳 방문 -> 끝나면 이전 방문한 정점으로 돌아가 다른 곳 방문
(2) BFS (Breadth First Search) : 큐 구조이용
=> 시작정점 방문 -> 시작정점에 연결된 정점을 차례로 방문 -> 다음 거리가 2인 정점 방문 -> 다음 거리 3인...
==========================================================================================================================
* 정렬(Sort) : 기억공간 내의 레코드나 자료를 임의의 기준에 의해 오름차순 또는 내림차순의 순서로 나열하는 것
=> 종류 : (1) 내부정렬 : 정렬하고자 한느 파일을 주기억 장치에 두고 정렬하는 방법으로 속도가 빠름
-> 삽입법 (삽입정렬, 셀정렬)
-> 교환법 (버블정렬, 퀵정렬, 선택정렬)
-> 선택법 (힙정렬)
-> 합병법 (2-way merge sort, n-way merge sort)
-> 분배법 (기수정렬)
(2) 외부정렬 : 정렬하려는 파일의 크기가 너무커서 보조기억장치에 두고 정렬하는 방법으로 속도가 느림
: run생성한후 합병(내부정렬, 대체선택, 자연선택)
-> 균형합병정렬, 계단식합병정렬, 교대합병정렬, 다단계합병정렬
==========================================================================================================================
* 검색(Search) : 자료들 중 주어진 조건에 맞는 레코드를 찾는것
1) 기억장소에 의 해 내부검색과 외부검색으로 나뉨
2) 검색방법에 의해
(1) 선형검색-순차검색 : 모든 레코드를 대상으로 처음부터 탐색, 오래걸린다.
(2) 제어검색 : 자료가 정렬되어 있어야하는 조건이 있으며, 검색키와 레코드를 비교하여 검색
=> 이진검색, 피보나치검색, 보간검색
(3) 트리검색 : 이진트리를 구성하여 실행
(4) 블럭검색 : 파일을 여러개의 블록으로 나눈다음 블록의 최대값을 구하여 인덱스로...
(5) 해싱(hashing) : 주어진 킷값을 찾을 때 해싱함수로 산출된 주소에 바로접근
=> Bucket의 Slot이 충분하다면 OverFlow가 없을수 있다.
=> 서로 다른 Key가 같은 Home Address를 가리키고 있다면 충돌현상이라고 하며
이 때의 Key들의 집합을 Synonym이라 한다.
