배열을 이용한 다항식의 표현

📌 배열을 이용한 다항식의 표현

💡 순서리스트 (Orderd List)

1. 데이터들의 순서가 유지되는 집합
   • 집합이란, 원소들의 모임, 순서를 중요시 하지 않음.
   1. 한 주의 요일들
   2. 섞여진 카드들
   3. 미국의 2차 세계 대전 참전 연도
   4. 스위스의 2차 세계 대전 참전 연도 (원소가 없는 집합도 순서리스트에 포함된다.)

💡 순서리스트의 연산

1. 순서리스트에 적용 가능한 연산들
   • 리스트 길이 연산
   • 리스트의 모든 데이터들을 왼쪽에서 오른쪽으로 읽기
   • 리스트로부터 i번째 데이터를 검색
   • 리스트로부터 i번째 데이터를 교체
   • 리스트의 i번째 위치에 새로운 데이터 추가 (i번째 이후에 있던 데이터는 한 칸씩 밀림)
   • 리스트의 i번째 위치에 있는 데이터를 삭제 (i번째 이후에 있던 데이터는 한 칸씩 당겨짐)

💡 다항식 소개

1. 순서리스트를 구현하는 방법
   • 배열 : i번째 데이터를 배열 i에 저장
   • 연결리스트

💡 C 언어에서 다항식 구현

1. 방법 1 : 모든 지수의 계수들을 내림차순으로 저장
   • 2x^3 + x^2 - 1 == [3, (2, 1, 0, -1)]
   • 만약 x^100 + 1 일 경우 [100, (1, 0, 0, ... , 1)]로, 메모리 낭비가 심해진다.

2. 방법 2 : 지수와 계수를 모두 저장하는 방법
   • x^100 + 1 == [(1, 100), (1, 0)]
   • 위와 같은 방법은 모든 항에 대해서 지수까지 표현해야하기 때문에 메모리 낭비가 심할 경우가 있다.
   • 각 다항식은 (start, end)의 쌍으로 표현한다.
   • 모든 다항식을 저장하기 위한 전역변수 terms 배열을 사용한다.