2장 - 희소 행렬(Sparse Matrix)의 표현
행렬에 0이 많이 포함된 경우에 희소행렬이라고 한다. 배열에 희소행렬을 그대로 표현할 경우 공간낭비가 심하게 된다. 낭비되는 공간을 줄이기 위한 방법은 어떤게 있을까? 이차원 배열에 표현된 희소행렬을 (행,열,값)으로 묶어 표현하는 방법이 있다 1 0 0 0 0 5 0 0 0 이런 배열일 있다고 하자. 이 때 (행,열,값)으로 묶어 표현하면 [(0,0,1),(1,2,5)] 로 적을 수 있겠다. 근데 이 방법이 항상 효율적인건 아니다. n*n의 행렬이 있을 때, 0이 아닌 값이 k개 있다고 하자 2차원 배열로 행렬을 그대로 표현하면 n^2의 공간이 필요할 것이며 (행,열,값)으로 묶어 표현하면 3*k의 공간이 필요할 것이다. 이 방법이 효율적일 때는 k 다음시간에 계속..
2022. 9. 25.
2장 - 다항식의 덧셈 구현하기
C언어에서 다항식을 구현하는 방법 방법1: 모든 지수의 계수들을 내림차순으로 저장 #define MAX_DEGREE 101 typedef struct{ int degree; float coef[MAX_DEGREE]; }polynomial; 예시) 2x^3 + x^2 -1 [3, (2,1,0,-1)] [최고차항 지수, (계수들 순서대로)] 또다른 예시로 x^100 +1이라는 식이 있을 때, 이 방법으로 저장하기 위해선 [100,(1,0,0,0,0.....0,0,0,0,1)]을 저장해야하는데, 계수가 0인 항이 많은 경우 메모리 낭비가 심하다. 방법 2: 지수와 계수를 모두 저장 #define MAX_TERMS 100 typedef struct{ float coef; int expon; }polynomial..
2022. 9. 25.
시간복잡도 (big - O,big - Omega,big - Theta) 표기법
입력 크기 n에 따른 실행시간 증가율을 나타낼 수 있다. Big O 표기법 Omega 표기법 Theta 표기법 Big O: - 상한선을 표현하는 방법이므로, 이 알고리즘은 O(n)보다는 작을 것임 - n>k일 때 f(n) k일 때 f(n) >= C *g(n) 을 만족하는 k, C가 존재하면 f(n) = Ω(g(n))이다. - (Big O의 반대라고 보면 된다) big Theta: - f(n)=O(g(n)) 이고 f(n) = Ω(g(n))일 때, f(n)=Θ(g(n))이다. 예제 프로그램들의 근사 표현 이진탐색: T(n) = T(n/2)+1, T(1) = 1 ==> O(log2 n) 순열출력: T(0,n) = (n+1)*T(1,n), T(n,n) = n+1 ==> O(n^2 * n!) 문제풀이는 대충적었으..
2022. 9. 17.
선택정렬, 이진탐색, 순열
#include #include #define MAX_SIZE 101 #define SWAP(x,y,t) (t=x,x=y,y=t) void sort(int[], int); void main() { int i, n, list[MAX_SIZE]; printf("Enter the number of numbers to generate:"); scanf_s("%d", &n); if (nMAX_SIZE) { printf("ERROR"); } for (i = 0; i < n; i++) { //n개의 정수를 랜덤으로 생성 list[i] = rand() % 1000; printf("%d ", list[i]); } sort(list, n); printf("\n Sorted array:\n"); for (i = 0; i <..
2022. 9. 14.
