본문 바로가기

정렬12

[알고리즘] Assignment 3 - 정렬 알고리즘 (bubble sort, insertion sort, merge sort, quick sort, radix sort, bucket sort) 1. Code #include #include #define SIZE 1000 #define DIGIT 4 int origin[SIZE], result[SIZE], result_2[SIZE]; void bubble_sort() { int i, j, temp; for (i = SIZE - 1; i > 0; i--) { for (j = 0; j origin[j + 1]) { temp = origin[j]; origin[j] = origin[j + 1]; origin[j + 1] = temp; } } } } void insertion_sort() { int i, j, temp; for (i = 1; i < SIZE; i++) { temp = origin[i];.. 2022. 1. 28.
[자료구조 프로그래밍 연습문제] 이진탐색트리 (binary search tree), 힙 (heap), min cost spanning tree, 전위표기식 (postfix), 연결 리스트 (linked list) 1. binary search tree와 heap binary search tree는 노드에 key 값만 저장하는 것이 아니라 key값과 관련된 정보(associated item)를 같이 저장한다. 후자를 단순히 value라고 하자. 이 (key, value) 쌍을 보통 dictionary pair라고 부른다 (교재 ADT 5.3 Dictionary 참조). 은 binary search tree의 예로 각 노드에 키 값만 나타낸 것이다. 는 각 노드에 (key, value) 쌍을 나타낸 것이다. (앞의 한자리 수는 key, 뒤의 두자리 수가 value) complete binary tree로 표현되는 heap도 노드에 (key, value) 쌍을 저장할 수 있다. (교재 5.6.3절에는 heap의 노드에.. 2022. 1. 28.
[자료구조 프로그래밍 연습문제] 힙 정렬 (heap sort) heap sort A. 배열 a[1]에서 a[11]에 11개의 999보다 큰 네자리 이상의 양의 정수가 저장되어 있다고 하자. 교재 Program 7.13: Heap sort의 함수 heapSort를 호출하여 이들을 오름순으로 정렬하는 과정을 확인하고자 한다. 이를 위해 Program 7.13에서 함수 adjust가 호출될 때마다 그 호출 직후 시점의 배열 a[1] 부터 a[11] 까지의 값을 출력하시오. 또한 정렬 진행 과정 설명을 위해 자신이 확인하고 싶은 기타 변수 값이 있으면 출력하시오. 출력된 값을 보고 배열을 complete binary tree로 그림을 그려서 해당 adjust의 수행 결과와 정렬 진행 과정에 대해 설명하시오. (complete binary tree 그림은 육필로 그려도 되고.. 2022. 1. 28.
[자료구조 프로그래밍 연습문제] 재귀함수, 선택정렬, 배열 1. recursion 교재 Figure 1.3의 C 코드에서 수업시간에 언급된 오류를 차고 정확한 코드로 수정하시오. 수정하지 않을 경우 실행 결과에 어떤 오류가 발생하는지 간단한 예를 들어 설명하시오. float rsum(float list[], int n) { if (n) return rsum(list, n-1) + list[n-1]; return 0; } 0 대신 list[0]의 값을 반환하면, list배열의 값들의 전체 합에 첫번째 요소 값이 한 번 더 더하여져서 값이 달라진다. 예를 들어, list == [1, 2, 3, 4, 5] 인 경우, rsum의 결과 값은 1 + 1 + 2 + 3 + 4+ 5, 16으로 첫번째 요소인 1만큼의 오차가 발생한다. 2. recursive implementa.. 2022. 1. 10.
[C++] C++ 11/14/17/... New STL (ENG) Unordered Map std::unordered_map std::unordered_multimap // std::map #include #include #include int main() { std::map scores; scores["Nana"] = 60; scores["Mocha"] = 70; scores["Coco"] = 100; for (auto it = scores.begin(); it != scores.end(); ++it) { std::cout first 2022. 1. 2.
[C++] Standard Template Library Container: Map (ENG) Creating Map A map stores pairs of key and value. Keys cannot be duplicated. C++ maps are automatically sorted. It is based on the binary search tree (ascending order). #include int main() { std::map simpleScoreMap; simpleScoreMap.insert(std::pair("Mocha", 100)); simpleScoreMap.insert(std::pair("Coco", 50)); simpleScoreMap["Mocha"] = 0; std::cout 2022. 1. 2.
[자료구조 프로그래밍 연습문제] 선택 정렬, 이진 탐색, 다항식 곱하기 1. selection sort A. 교재 1장 Program 1.4: Selection sort의 함수 sort()는 오름순(non-decreasing order) 정렬과 내림순(non-increasing order) 정렬 중 어느쪽을 수행하는가? 교재의 함수 sort()를 교재의 정렬 순서와 반대 순서로 정렬하도록 수정한 C 코드를 제시하시오. 오름순(non decreasing order) 정렬을 수행한다. void sort(int list[], int n) { int i, j, max, temp; for (i = 0; i list[max]) max = j; SWAP(list[i],.. 2021. 4. 3.
[C 프로그래밍 실습] 동적 메모리와 전처리 2 (Lab 14) Program 1 : 전처리 함수, 매크로 Program 2 : 전처리 함수, 매크로 Program 3 : 전처리 함수, 매크로, 삼항 연산자 Program 4 : 버블 정렬 Program 5 : 선택 정렬 Program 6 : 삽입 정렬 Program 1 다음을 참고로 매크로 PRINTM(exp)를 정의하여 다음 결과가 나오도록 프로그램을 작성하시오. Dev C++ 의 경우 전처리 연산자(#, #@, ##)는 printf() 인자로 사용할 경우 오류 발생하나, 아래 문제를 해결하기 위한 매크로 정의에는 문제 없음 매크로 PRINTM (exp)는 “Expression: exp = 연산 결과값” 으로 출력 int a = 2; PRINTM(3 * 4 + 3 / a); #include #define PRINT.. 2021. 1. 8.
[C 프로그래밍 실습] 동적 메모리와 전처리 1 (Lab 13) Program 1 : 구조체, 동적 메모리 할당 Program 2 : 이차원 배열, 동적 메모리 할당 Program 3 : 파일 입력, 구조체, 동적 메모리 할당, 연결리스트 Program 4 : 동적 메모리 할당, 연결리스트, 출력 Program 5 : 배열, 연결리스트, 삽입, 삭제, 정렬 Program 1 다음 결과를 참고로 구조체 point와 circle을 정의하고 구조체 circle을 저장할 공간을 동적으로 할당하여 다음 자료를 저장하고 출력하는 프로그램을 작성하시오. 구조체 point : 실수 멤버 x, y 이차원 평면의 좌표로 구성 구조체 circle : 원의 중심 좌표인 point와 반지름인 실수 radius멤버로 구성 원 중심좌표(x,y) 와 반지름을 실수로 차례로 입력 #include .. 2021. 1. 8.

티스토리툴바