학점교류로 듣는 숙명여대 자료구조
day 2. 2021.12.23. 목
Polynomial ADT
a sum of terms, ax^e(x:variable, a:coeffieicnet, e:exponent)
array of terms (coefficient, exponent)
지수의 내림차순으로 정렬되어있다.
지수가 같은 항은 하나만 있다.
operations of polynomial ADT
method를 구현한다. -> 구현해보기
IsEmpty()
Coef(poly, expon)
Lead_Exp(poly) # 최고 차항
Attach(poly, expon)
Remove(Poly, expon)
SingleMultiply(poly, coef, expon) # 새로운 항을 곱하는 것이다.
Add(poly1, poly2)
Multiply(poly1, poly2)
ex)
A(x) = 2x^100 + 1
B(x) = x^4 + 10*x^3 + 3x^2 + 1
A = [(2,100), (1,0)]
B = [(1,4), (10,3), (3,2), (1,0)]
D = []
홀 재밌다.
# polynomial ADT
A = [(2,100), (1,0)]
B = [(1,4), (10,3), (3,2), (1,0)]
D = []
def padd(a, b, d):
while a and b:
coef1, exp1 = a[0]
coef2, exp2 = b[0]
if exp1 > exp2:
d.append(a.pop(0)) # 가장 앞 원소를 꺼낸다 # a.pop 은 가장 뒷 원소
elif exp1 < exp2:
d.append(b.pop(0))
else:
d.append(((coef1+coef2), exp1))
a.pop(0)
b.pop(0)
for coef, exp in a:
d.append((coef, exp))
for coef, exp in b:
d.append((coef, exp))
a = [(5,12), (-6, 8), (13,3)]
b = [(10,15), (4,8), (9,0)]
d = []
print("a=",a)
print("b=", b)
padd(a,b,d)
print("d=", d)
Sparse Matrix
희소 행렬 : 행렬의 원소가 대부분 0인 행렬
Matrix(m row, n cols)
2d array : matrix[m][n]
space complexity = S(m,n) = m*n
희소 행렬 A[m,n]
most of matrix elements are zeors
find efficient method to store a sparse matrix
0이 아닌 것만 위치, 값을 저장해두자~
solution
- store non-zero elements only
- array of 3-tuples (row, col, value) => array of struct
store matrix info at a[0]
the number of rows
the number of columns
the total number of non-zero values
a[0].row : number of matrix rows
a[0].col : number of matrix columns
a[0].value : number of non-zeros
From at a[1],
non-zero elements are stored in left-right and top-bottom order
tuple array
그대로 저장하지 않으니
괜찮아짐
메모리 복잡성이 낮은 쪽이 무엇인지 잘 계산해보아야 함~!
class SparseMatrix:
def __init__(self):
self.matrix = [[15,0,0,22,0,15],
[0,11,3,0,0,0],
[0,0,0,-6,0,0],
[0,0,0,0,0,0],
[91,0,0,0,0,0],
[0,0,28,0,0,0]]
self.sparse_list = []
def toTuple(self):
row = count = 0
for rows in self.matrix:
col = 0
for value in rows:
if value != 0:
count += 1
self.sparse_list.append((row, col, value))
col += 1
row += 1
height = len(self.matrix)
width = len(self.matrix[0])
self.sparse_list.insert(0,(height,width,count))
s = SparseMatrix()
s.toTuple()
print(s.sparse_list)
숙제 : 연습문제
space complexity
S(m,n) 3*(t+1) < m*n
t = number of non-zeros
until 8 non-zeros,
(8+1) * 3 < m*n