본문 바로가기

전체 글163

[알고리즘] 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.
[알고리즘] Assignment 2 Submit a word, hwp or pdf file to the e-class that contains (1) your answers for the following exercises, and (2) your codes written in the C programming language and their results for programming exercises (screenshots okay). 1. (programming) Write a program that takes a number n and displays the largest k satisfying the following equations: 2^k 2022. 1. 28.
[알고리즘] Assignment 1 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.
[자료구조 프로그래밍 연습문제] 연결 리스트 (linked list) invert 함수, 원형 연결 리스트 (circular linked list) linked list A. 교재 4.5절에 설명된 Program 4.16: Inverting a singly linked list의 함수 invert를 고려하자. 리스트 p가 있을 때 q = invert(p); 를 호출하면 처럼 리스트의 링크가 방향이 바뀐다. 교재의 invert를 수행하면서 그 동작과정을 확인하기 위한 프로그램을 아래와 같이 작성하고 invert의 실행 과정을 확인 및 설명하시오. main 함수에서 노드 2개로 구성된 리스트 L2를 생성한 후, 생성한 리스트를 출력한다 (각 노드의 주소, 데이터 필드 값, link 필드 값을 출력한다.) 생성한 리스트에 대해 invert 함수를 호출한다. invert에서 while loop이 매회 수행된 직후마다 다음 회를 수행하기 전에 변수 trail.. 2022. 1. 12.
[자료구조 프로그래밍 연습문제] 다항식 덧셈, 희소행렬 덧셈 1. polynomial addition 두 다항식 A(x)와 B(x)를 더하여 다항식 D(x)를 구한다고 하자. 만약 다항식을 항 배열로 표현하되 교재의 Figure 2.3과 같이 여러 다항식들을 하나의 통합된 배열에 저장할 경우 이를 C로 구현한 것이 교재의 Program 2.6과 Program 2.7이다. 다항식을 계수 배열로 표현할 경우 계수가 0인 것도 모두 저장하므로 다항식 더하기 프로그램은 매우 간단히 작성될 수 있다. 다항식 A(x), B(x), D(x)를 각각 교재 2.4.2절에 기술된 계수 배열 표현 방법으로 저장할 경우 다항식 더하기를 수행하는 C 프로그램을 작성하시오. 다항식 표현 방법 : 교재 2.4.2절에 기술된 내용 및 관련 C 코드를 일체의 수정 없이 그대로 사용한다. mai.. 2022. 1. 12.
[자료구조 프로그래밍 연습문제] maze 미로 경로 찾기 1. maze 교재 Program 3.12의 함수 path를 아래 요건대로 수정한 후 이를 호출하여 경로찾기를 수행하고 경로 를 출력하는 maze 프로그램을 작성하시오. mark[][] 배열을 사용하지 않는다. maze[][] 배열의 상하좌우 가장자리 element들을 사용하지 않는다. 즉, n by m maze의 경우 교재의 프로그램에서는 maze[][] 배열을 maze[n+2][m+2] 로 선언하고 상하좌우 가장자리 element들의 값을1로 설정하여 사용하는데 본 수정에서는 maze[][] 배열을 maze[n][m]로 선언하여 maze를 표현한다. stack에 저장 시 위치좌표만 저장하고 방향정보는 저장하지 않는다. 즉, 교재에서는 (row, col, dir)을 push하는데 (row, col) 만.. 2022. 1. 11.
[자료구조 프로그래밍 연습문제] 희소행렬 전치 1. sparse matrix transpose 교재에서는 그림 2.4(b)의 6×6 matrix를 그림 2.5(a)의 a 배열로 표현하였다. A. 그림 2.5(a)의 a 배열의 값은 정확한가? 정확하다. B. 그림 2.5(b)의 b 배열은 그림 2.4(b)의 6×6 matrix를 transpose 한 결과이다. 그림 2.5(b)의 b 배열의 값은 정확한가? 정확하다. C. 교재 2.5.3절의 마지막 부분에는 2.5(a)의 a 배열에 대해 프로그램 2.9 fastTranspose()의 3번째 for loop 수행 직후 시점의 rowTerms 배열과 startingPos 배열의 값을 보이고 있다. 이들 값은 정확한가? 정확하다. D. 프로그램 2.9 fastTranspose()로 그림 2.5의 a 배열로부.. 2022. 1. 11.

티스토리툴바