본문 바로가기

C언어30

[알고리즘] Assignment 5 - LCS 알고리즘, BFS 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘, Prim 알고리즘 1. LCS (Longest Common Subsequence, 최장 공통 부분 문자열) #include #define MAX(a,b) ((a)>(b)? (a):(b)) int LCS_table[10][10] = { 0, }; void LCS_length(int str1_len, int str2_len, char* str1, char* str2) { for (int i = 1; i < str1_len; i++) { for (int j = 1; j < str2_len; j++) { if (str1[i] == str2[j]) { LCS_table[i][j] = LCS_table[i - 1][j - 1] + 1; } else { LCS_table[i][j] = MAX(LCS_table[i - 1][j], LC.. 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.
[자료구조 프로그래밍 연습문제] 다항식 계수 배열, 다항식 곱하기, 구조체 1. 다항식 : 계수 배열 representation 교재 2.4.2절에 기술된 다항식 표현 방법 두 가지 중 앞부분에 먼저 기술된 계수 배열 표현의 C 구현으로 다항식 A(x) = a_n*x^n + a_(n-1)*x^(n-1) + ... + a_(1)*x^1 + a_(0)*x^0 을 표현하였다고 하자. 최고차항 a_(n)*x^n의 계수 a_(n)은 0이 아니고 나머지 항들의 계수는 0일 수도 있다고 가정한다. A(x)를 나타내는 변수 a를 교재에서 정의한 구조체 자형 polynomial로 선언하면 C 코드로 polynomial a; 이다. A. 구조체 자료형 polynomial에서 degree의 의미는 무엇인가? 차수, 즉 다항식에서 가장 큰 지수를 뜻한다. B. a.coef[i] = a_(n-i) 라.. 2022. 1. 11.
[자료구조 프로그래밍 연습문제] 재귀함수, 선택정렬, 배열 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.
[자료구조 프로그래밍 연습문제] 선택 정렬, 이진 탐색, 다항식 곱하기 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 프로그래밍 실습] 기말고사 문제 1. 다음 내용을 참고로 구조체 fraction을 정의하고, 2개의 분수를 표준입력으로 받아, 두 분수의 사칙 연산을 수행하는 프로그램을 작성하시오. (20점) 구조체 fraction 멤버 구성: 정수형의 분자(numerator)와 분모(denominator) 구조체 변수 선언은 포인터 형으로 한다. 연산식 입력 : 분수1 연산자 분수2 분수와 연산자 사이에는 임의의 공백이 있을 수 있다(뺄셈 연산 참고) 계산 결과후 약분(reduction of fraction)은 불필요(곱셈 연산 결과 참고) 연산은 무한 루프로 실행 2. 다음 파일(in.txt) 내용을 참고하여 구조체를 정의하고, 파일의 내용을 읽어 연결리스트를 구성하시오. 각 학생의 점수의 합을 구하여 아래와 같이 연결리스트를 출력하는 프로그램을 .. 2021. 1. 8.

티스토리툴바