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