imported>Unknown at 05:24, 7 February 2021

2021-02-07T05:24:00Z

New page

=== 목적 ===
다항식의 곱셈을 이용하는 프로그램을 작성한다.
=== 자료구조 ===
하나의 항은 coefficient 와 exponent 로 구성된다. 하나의 항(단항식)을 표현하는 자료구조는 다음처럼 구조체를 사용한다. (여기서는 지수와 밑모두 integer를 사용한다)

struct Node {
int coef; // 밑
int exp; // 지수
};

다항식을 표현하는자료구조는 크게 두가지로 생각해 볼 수 있다. linked list 와 array 이다. 배열은 모두들 잘 알겠고 linked list 는 동적으로 storage를 할당받아 각 노드를 포인터로 연결한 자료구조를 말한다..(라고 우선 설명만 해둬야지 정확한 정의는 내리지 못하겠다..-_-). 물론 동적으로 할당받지 않고도 linked list 를 구현할수 있지만 그럴꺼면 배열로 하는게 낫지 그 노가다를 뭐하러 하나...-_-

* 배열을 사용한 방법
Node expr_1[SIZE]; // 이와 같은 식으로 표현한다.
Node expr_2[SIZE];

* linked list 를 사용한 방법
// 위의 정의한 구조체에 포인터 변수 두개가 더 필요하다.
struct Node {
int coef;
int exp;
Node *prev;
Node *next;
};

Node *n1 = new Node;
Node *n2 = new Node;
n1->next = n2;
n1->prev = NULL;
n2->next = NULL;
n2->prev = n1;

이 방법을 사용할때 발생할수 있는 문제점은 memory leakage (메모리 누수)이다. Java같은 경우는 쓰레기 수집기가 있지만 c 는 코더(-_-)가 일일이 사용되지 않는 자원을 회수해줘야 한다. 그렇지 않으면 그 자원을 다시 사용할 수 없게 된다.

=== specification ===
다음과 같은 prototype 을 갖는 함수를 구현해야 한다. (이름은 달리해도 상관없다..)
Node* mul(Node *n1, Node *n2); // 두 다항식의 곱을 표현하는 새로운 다항식을 리턴한다.
Node* add(Node *n1, Node *n2); // 두 다항식의 합을 표현하는 새로운 다항식을 리턴한다.
Node* add(Node *n1, Node *n2); // 두 다항식의 차를 표현하는 새로운 다항식을 리턴한다.
/* 문제점 : 다음과 같은 경우는 어떻게 처리해야 할까?
n1 = mul(n1, n2); // n1 이 중복 사용되었다..
*/
Node* input(); // 사용자에게 값을 입력받아 새로운 다항식을 생성하여 리턴한다.
void delete(Node *node) // 다항식을 삭제한다.
void sort(Node *node) // 다항식을 내림차순으로 정리한다.

=== input data ===
다음과 같은 자료의 합, 차, 곱을 리턴하는 프로그램을 작성하시오
식1 : 2x^5 + 3x^2 - 2x + 10
식2 : 2x^4 + x^3 - 5x^2 +3

=== 잡담 ===
* 다항식을 표현하는 클래스를 만들어서 operator overloading 을 사용해도 되겠지만 이는 위에 말한 내용을 이미 구현한 후 이걸 클래스로 포장하는거기때문에 지금수준에서는 무리라고 생각됨... - 임인택
* 이거 작년에 했다가 한명("영창이")만 겨우 풀었어요 저도 이거 하다 포기했고 1학년에게 넘 어려운 문제가 아닐런지...-재동
----
see Also [[데블스캠프2002]]
----
[[문제분류]]

Polynomial - Revision history

imported>Unknown at 05:24, 7 February 2021