코코야이야기

쉘 정렬 (Shell Sort) - 삽입 정렬을 간단하게 변형 - 멀리 떨어진 원소끼리 교환이 가능하게 하여 정렬 속도를 향상시킴 - h-정렬 화일 : 모든 h번째 원소를 정렬한 화일 - 증가 순서의 예 : …, 1093, 364, 121, 40, 13, 4, 1 특징 - 순열 h가 1, 4, 13, 40, … 일 때, 쉘 정렬의 비교 횟수는 N 3/2 을 넘지 않음 - 제자리 정렬 - 멀리 떨어진 원소끼리 교환할 때 동일한 원소가 어디로 갈지 알 수 없으므로 불안정적 수행 과정

칵테일 쉐이커 정렬 (Cocktail Shaker Sort) - Donald Knuth가 처음 제안 - 버블 정렬을 수정하여 매번 반복할 때마다 방향을 바꿔가며 원소의 위치를 결정하는 기법. - 한 번은 가장 큰 원소가 결정되고, 그 다음에는 가장 작은 원소가 결정되고, 또 그 다음에는 2번째로 큰 원소가 결정되고... 소스 코드 1. #include #include using namespace std; const int N = 10000; const int TRUE = 1; const int FALSE = 0; inline void swap(int a[], int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } void printList(int a[]) { i..

삽입정렬 (Insert Sort) - 카드 놀이를 할 때 손에 들고 있는 카드를 정렬하는 것과 유사함 - 오른쪽으로 움직이며 차례로 원소를 적절한 위치에 삽입하고 나머지 원소는 하나씩 오른쪽으로 이동시킴 특징 - 레코드를 계속 이동시켜야 하므로 레코드의 크기가 큰 경우에 불리 - 거의 정렬이 된 화일인 경우 유리 - 안정적인 제자리 정렬 - 더미(dummy) 키가 필요함 삽입과정 수행과정 성능 특성 - 시간 복잡도 O(N 2) - 거의 정렬된 화일의 경우 효율적임

버블정렬 (Bubble Sort) - 마치 거품이 물 위로 올라가는 것 같이 큰 값이 뒤로 가며, 결국 루프를 한번 반복할 때 마다 가장 큰 값을 가진 원소가 가장 뒤쪽으로 이동 특징 - 레코드를 계속 교환하므로 레코드의 크기가 큰 경우 좋지 않음 - 거의 정렬이 된 화일일 경우 좋음 - 안정적인 제자리 정렬 수행과정 성능 특성 - N 개의 원소 각각에 대해 N-1 번의 비교 - 전체 비교 횟수 N(N-1)/2 - 전체 시간 복잡도 O(N2)

선택정렬 (Selection Sort) - 배열에서 가장 작은 원소를 찾아 첫 번째 원소와 교환하고 두 번째 작은 원소를 찾아 두 번째 원소와 교환하고.. 이러한 방식으로 전체가 정렬될 때까지 계속함 특징 - 레코드가 실제로 교환되는 것은 많아야 한번 뿐이므로 작은 키와 매우 큰 레코드를 가지는 화일을 정렬하는데 적합 - 실행 시간은 입력 자료의 순서에 민감하지 않음 - 제자리 정렬 - 현재 값과 가장 작은 값을 교환할 때 현재 값이 어디로 갈지 알 수없으므로 불안정 수행과정 성능 특성 - n개의 원소 각각에 대해 n-1 번 비교 - 전체 비교 횟수 n(n-1)/2 - 전체 시간 복잡도 O(n^2) - 큰 레코드와 작은 키를 가지는 화일의 경우 효율적 소스 코드 #include #include #incl..

문제 A부터 Z까지 영문 대문자로 된 키를 입력으로 받은 다음, 키보드를 통해 입력된 문장을 비게네르 암호화 기법을 사용하여 암호화하는 프로그램을 작성하라. 스페이스는 문자 A보다 하나 앞에 있는 문자로 취급한다. 아래에 있는 첫 번째 예에서 A는 1, B는 2, C는 3 만큼 뒤에 있는 문자로 암호화한다. - 입출력 예 [입력] 3개의 키 입력 : ABC 평문 입력 : FIX YOU ZOO [출력] 암호문 출력 : GK A RVBCPQ [입력] 3개의 키 입력 : EJO 평문 입력 : FIX YOU ZOO [출력] 암호문 출력 : KSLEHCZJNTY 소스코드 #include #include using namespace std; void main() { char key[4]; cout

문제 생성된 허프만 코드로부터 원래의 문자열을 복원 [출력 예] 문자열 입력 : ABRACADABRA 허프만 코드 : 01011001110011110101100 복원된 문자열 : ABRACADABRA 허프만코드란? - 문자의 출현 빈도수에 따라 가변 길이를 배정. 트리구조를 사용하여 도출. 빈도수가 많은 문자는 적은 길이를 배정받는다. 소스코드 #include using namespace std; class Huffman { private: int *heap, *infomation; int n; public: Huffman(int size=100) { heap = new int[size]; infomation = new int[size]; n = 0; } ~Huffman() { delete heap; }..

파일 입출력관련 문제 제한시간 50분 --- 25분정도 걸림 문제 1. fstream 라이브러리를 사용하여 email.html 파일을 읽어서 그대로 화면에 출력하는 프로그램을 작성한다. 2. email.html 파일의 내용을 text[] 배열에 저장한다. 3. 직선적 스트링 탐색 알고리즘을 구현한 BruteForce 함수를 사용하여 "mailto:" 패턴이 나오는 위치를 탐색한다. 4. "mailto:" 패턴을 찾으면 "(쌍따옴표)가 나올 때까지 text[] 배열에 있는 문자를 화면에 출력한다. 화면에 출력하는 것이 성공하면 파일에 출력하는 것도 시도해 보라 [email.html 파일 내용] -------------------------------------------------- 홍길동 장길산 김영희 ..

문제 소스코드 #include using namespace std; void main() { int n; //n의 값은 20 이하 cout

문제 소스코드 #include #include using namespace std; int main() { string a; cout