1. 배열과 희소 다항식
희소 다항식은 차수가 큰 항이 있지만 항의 개수는 얼마 없는 다항식을 말한다. 다항식을 배열로 구현할 경우 각 항의 차수를 index에 대응시키는 방법이 있다. 하지만 이 방법은 희소 다항식에 어울리지 않는 방법이다. 만약 을 구현하려고 한다면 최고 차항의 차수가 99이므로 원소 100개 크기의 배열이 필요하게 되는데, 실제로 의미있는 원소는 2개 밖에 안된다. 다른 방법으로는 각 항의 정보를 갖고 있는 구조체의 배열 형태로 구현하는 것이 있다. 새로운 항을 추가할 때마다 원소 하나를 추가하면 되므로 불필요하게 낭비되는 메모리를 줄일 수 있다.
2. Term과 Polynomial
항의 정보는 Term구조체 형태로 저장된다. 계수와 지수 정보를 갖고 있다. Polynomial은 다항식을 표현하기 위한 클래스다. 주요 기능으로는 항 추가, 다항식 덧셈이 있다. m_terms 는 항의 배열을 가리키는 포인터고 초기 크기를 설정할 수 있다. 배열의 크기인 m_capacity 를 넘어가면 배열 크기는 2배로 증가한다. 다항식은 내림차순 정렬이 되도록 항을 추가할 때 삽입 정렬을 한다.
3. Polynomial 구현
4. 구현 테스트
출력 결과는 다음과 같다
Capacity: 8
numTerms: 6
10x^1000 + x^100 - 3x^5 + 5x^2 + 6x + 8
Capacity: 8
numTerms: 5
10x^32 + 13x^7 - 6x^3 - 8x + 6
Capacity: 16
numTerms: 9
10x^1000 + x^100 + 10x^32 + 13x^7 - 3x^5 - 6x^3 + 5x^2 - 2x + 14
PowerShell
복사