Selection Sort 선택 정렬 - 정렬되지 않은 영역에서 가장 큰 원소를 찾아 제자리에 위치시키는 것을 반복한다. * Comparison Sort Algorithms (비교 정렬 알고리즘) Selection Sort (선택 정렬) (URL) Bubble Sort (버블 정렬) (URL) Insertion Sort (삽입 정렬) (URL) Merge Sort (병합 정렬) (URL) Quick Sort (퀵 정렬) (URL) Heap Sort (힙 정렬) (URL) Mechanism (메커니즘) - 배열 \(\texttt{A[1 ... n]}\)*에서 가장 큰 원소를 찾아 배열의 끝자리에 있는 원소 \(\texttt{A[n]}\)과 자리를 맞 바꾼다.(오름차순 정렬의 경우) - 배열 내 가장 큰 원..
Queue 큐 구조 - 한 쪽 끝에서 삽입이 일어나고 그 반대쪽 끝에서 삭제가 일어나는 Ordered List(순서 리스트)이다. ※ Stack: LIFO (Last In First Out) ※ Queue: FIFO (First In First Out) - Queue는 Item 들을 도착한 순서대로 보관한다. - \(\texttt{Queue는 보관할 수 있는 Item 수에 한계가 있다. - Empty \(\texttt{Queue}\)를 생성할 수 있어야 한다. - \(\texttt{Queue}\)가 비어 있는지 검사할 수 있어야 한다. - \(\texttt{Queue}\)가가득차있는지검사할수있어야한다. - \(\texttt{Queue}\)의 Rear 부분(꼬리 부분)에 항목을 추가할 수 있어야 한다. -..
Structure Bag 가방 구조 - 중복된 원소를 허용하는 Container Class로 원소들간에 순서를 구분짓지 않는다. Bag에서 제공하는 연산의 종류 1. Push : 원소를 삽입하는 연산으로, 배열내에서 이용가능한 첫 번째 위치를 찾아내어 그 자리에 원소를 삽입(저장)한다. 배열이 꽉 찼을 경우, 배열의 크기를 두 배로 확장한다. 2. Pop : 원소를 제거하는 연산으로, 배열의 중앙에 위치한 원소를 찾아 제거하고, 뒤따른 원소들의 위치를 한 칸씩 조정한다.
Container Class 컨테이너 클래스 - 다수의 데이터 객체들을 수용 또는 저장하는 자료 구조를 표현하는 클래스이다. - 기본적으로, 데이터를 삽입하는 Push 연산, 데이터를 삭제하는 Pop 연산을 제공한다. - 컨테이너의 종류로는 Bag, Stack, Queue, Array 등이 있다.
Array 배열 - 연속적인 메모리 위치를 갖는 점이 특징인 Low-Level적 특성이 있는 자료구조이다. (구현 중심적) - 인덱스와 특정 값이 일대일로 Mapping(사상)되어 집합을 이루는 형태이다. - 대부분의 프로그래밍 언어에서는 추출, 저장, 생성 연산만을 제공하므로 추가적인 세부 연산을 위해서는 Operator Overloading이 필요한 자료구조이다. - 배열은 그 자체로 자료구조인 동시에, 다른 ADT(Abstract Data Type)구현에 이용 가능하다. * ADT {Abstract Data Tyep, 추상 데이터 타입) - Data Type(데이터 형)을 정의함에 있어서 해당 데이터 형에 적용 가능한 연산자와 제약조건과 같은 프로그래머 입장에서 최소한으로 알아야 할 내용만을 보여주..
분할정복 Divide and Conquer - 각 재귀 호출 레벨 위에서 세 가지 단계를 거치면서 재귀적으로 문제를 풀이함 1. 분할 - Divide - 현재의 문제와 동일하되 입력의 크기가 더 작은 다수의 부분 문제로 분할한다. 2. 정복 - Conquer - 부분 문제를 재귀적으로 풀어서 정복한다. - 부분 문제의 크기가 충분히 작으면 직접적인 방법으로 푼다. 3. 결합 - Combine - 부분 문제의 해를 결합해 원래 문제의 해가 되도록 만든다. * 부분 문제가 재귀적으로 풀어야 할 만큼 충분히 클 때, 재귀 대상(Recursive case) 라 한다. * 부분 문제가 충분히 작아져 더 이상 재귀 호출을 할 수 없을 때, "재귀가 바닥을 쳤다(Bottoms out)" 라 표현하거나, "베이스 케이..
Asymptotic Notation 점근적 표기법 - 변수의 크기가 충분히 큰 경우에 변수가 커짐에 따라 함수가 증가하는 비율을 표현하는 방법 * Asymptotic Analysis (점근적 분석) : 입력이 충분히 큰 경우에 대한 분석 ex) 점근적 표기법의 예시 ※ 표기법 상 유의사항 1. 점근적 표기법에서 " = "(Equal) 은 " ∈ "(lunate epsilon) 을 의미함 따라서 교환법칙이 성립하지 않음! ex) \(n^2 + 3 = \Theta(n^2) \nLeftrightarrow \Theta(n^2) = n^2 + 3\) 2. s.t. 는 such that 을 의미함 ex) \(A s.t. B \iff B\)를 만족하는 \(A\) Theta Notation - \(\Theta\) - ..
