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.
