[알고리즘] 배열의 응용: 다항식 덧셈 프로그램 분석1

배열로 다항식의 덧셈을 구현할 때 2가지의 선택지가 있다.

1. 모든 차수에 대한 계수 값을 배열로 저장

2. 하나의 다항식을 하나의 배열로 표현

 

이번 포스팅에는 첫번째 방식으로 구현한 코드를 분석해볼 것이다.

 

모든 차수에 대한 계수 값을 저장하는 방식의 장단점

• 장점
  1. 같은 차수의 계수를 쉽게 찾을 수 있으므로 알고리즘이 간단하다.
  2. 다항식의 각종 연산이 간단해진다
• 단점
  1. 대부분의 항의 계수가 0이라면 메모리 낭비가 심하다.

 

 

코드 분석

#include <stdio.h>
#define MAX(a,b) (((a)>(b)) ? (a) : (b))
#define MAX_DEGREE 101

typedef struct {
	int degree; //차수
	float coef[MAX_DEGREE]; //계수
}polynomial;

polynomial poly_add(polynomial A, polynomial B) {
	polynomial C; // 덧셈 결과를 기록할 다항식 C 생성
	int Apos = 0, int Bpos = 0; int Cpos = 0; // A, B, C의 현재 position
	int degree_a = A.degree; // degree_a에 최고차항 저장
	int degree_b = B.degree; // degree_b에 최고차항 저장
	C.degree = MAX(A.degree, B.degree); // C.degree에 두 다항식 중 더 높은 최고 차항 저장

	while (Apos <= A.degree && Bpos <= B.degree) { // 다항식의 position이 최고차항까지 진행
		if (degree_a > degree_b) { // 계산할 차항이 A가 더 높을 때
			C.coef[Cpos++] = A.coef[Apos++]; // A항의 계수만 C에 저장
			degree_a--; // 해당 차항은 계산이 끝났으니 한 차수 내려준다.
		}
		else if (degree_a == degree_b) { // A와 B가 차항이 같을 경우
			C.coef[Cpos++] = A.coef[Apos++] + B.coef[Bpos++]; // A와 B의 계수를 더해서 C에 저장
			degree_a--; degree_b; // 각 A항 B항 모두 계산이 끝났으니 한 차수 내린다.
		}
		else { // 계산할 차항이 B가 더 큰 경우
			C.coef[Cpos++] = B.coef[Bpos++]; // B의 계수를 그대로 옮겨준다.
			degree_b--; // 계산이 끝난 차항 한 차수 내려주기
		}
	}
	return C;
}

 

이제 코드를 조금씩 뜯어서 해석해보자

 

기본 세팅

#include <stdio.h>
#define MAX(a,b) (((a)>(b)) ? (a) : (b))
#define MAX_DEGREE 101

typedef struct {
	int degree; //차수
	float coef[MAX_DEGREE]; //계수
}polynomial;

두 변수 중 큰 값을 리턴하는 MAX를 define해준다. 

MAX_DEGREE는 계산할 수 있는 최고 차수를 나타낸다.

 

최대 차수와 , 차수에 해당하는 계수를 저장해야 하니 배열도 같이 선언해준다.

 

계산에 필요한 변수 정리

polynomial poly_add(polynomial A, polynomial B) {
	polynomial C; // 덧셈 결과를 기록할 다항식 C 생성
	int Apos = 0, int Bpos = 0; int Cpos = 0; // A, B, C의 현재 position
	int degree_a = A.degree; // degree_a에 최고차항 저장
	int degree_b = B.degree; // degree_b에 최고차항 저장
	C.degree = MAX(A.degree, B.degree); // C.degree에 두 다항식 중 더 높은 최고 차항 저장

Apos, Bpos, Cpos는 position을 뜻한다. 즉 계산할 현재 위치라는 것이다. 

최고차수인 A.degree를 degree_a로 복사한 이유는 원본 값 A.degree를 유지하기 위해서이다. while문 조건 안에서 각 다항식의 position과 비교해야 하기 때문에 원본 값을 유지시킨 것이고,  계산이 끝난 항의 지수를 하나씩 내려주기 위해 degree_a로 복사한 것이다.

 

C.degree의 최고 차수는 다항식 A와 B중 최고차수가 높은 것이다. 그러므로 define한 MAX함수를 이용해 최고차수가 높은 것을 저장한다.

 

 

다항식 계산

while (Apos <= A.degree && Bpos <= B.degree) { // 다항식의 position이 최고차항까지 진행
		if (degree_a > degree_b) { // 계산할 차항이 A가 더 높을 때
			C.coef[Cpos++] = A.coef[Apos++]; // A항의 계수만 C에 저장
			degree_a--; // 해당 차항은 계산이 끝났으니 한 차수 내려준다.
		}
		else if (degree_a == degree_b) { // A와 B가 차항이 같을 경우
			C.coef[Cpos++] = A.coef[Apos++] + B.coef[Bpos++]; // A와 B의 계수를 더해서 C에 저장
			degree_a--; degree_b; // 각 A항 B항 모두 계산이 끝났으니 한 차수 내린다.
		}
		else { // 계산할 차항이 B가 더 큰 경우
			C.coef[Cpos++] = B.coef[Bpos++]; // B의 계수를 그대로 옮겨준다.
			degree_b--; // 계산이 끝난 차항 한 차수 내려주기
		}
	}

while문 조건을 먼저 보자.

>>   Apos <= A.degree && Bpos <= B.degree

A.degree와 B.degree는 각 다항식의 최고차수이다. 

Apos와 Bpos는 계산을 실행할 현재 위치를 나타낸다. 

위 사진을 다항식 A라고 한다면, while문을 처음 돌 때 Apos는 0, A.degree는 5이다.

그럼 while문이 한 번 실행되고 Apos가 1 증가했다면, Apos는 1, A.degree는 5이다.

그렇게 다항식 A의 계산이 모두 끝난 후 Apos는 6이 될 것이고 A.degree는 여전히 5이다. 그럼 다항식 A의 계산이 끝난 것이고 while문 안의 조건에 벗어났기 때문에 while문에서 벗어나게 된다.

 

인덱스 수와 최고차수가 반대로 되어있어 조금 헷갈릴 수 있지만 천천히 읽어보면 이해가 될 것이다!

 

다음 if문을 살펴보자

 

if문의 조건은 degree_a와 degree_b 중 어느것이 큰지, 작은지, 같은지 비교하는 것이다.

전체적으로 보자면, 우리는 계수가 0인 차항도 모두 배열에 저장시켜놓았다. 

만약 A가 B보다 최고차수가 크다면, degree_a > degree_b의 조건을 만족시킨다.  계산이 끝난 degree_a는 줄어들 것이고 계산이 실행되지 않은 degree_b는 유지될 것이다. 그렇게 A와 B의 차수가 같은 순간이 온다.

그 후에는 degree_a == degree_b 조건만 충족될 것이고 동시에 다항식의 계산이 끝날 것이다.

 

이제 세부적으로 들어가보자.

편의를 위해서 degree_a가 더 클경우는 if문, 같은 경우는 else if문, degree_b가 더 클경우는 else문이라고 하겠다.

다항식 A의 최고차수 5, B의 최고차수가 4라고 가정해보자. 현재 최고 차수가 들어있는 degree_a와 degree_b를 비교할 것이고 그 결과, if문이 실행될 것이다. 그렇게 되면 계산할 필요 없이 그대로 덧셈 연산 결과 다항식인 C.coef[Cpos]로 복사해주면 된다.  현재 Cpos는 0이기 때문에 배열에 가장 첫번째로 들어갈 것이다.

Cpos++와 Apos++를 해준 이유는 계산이 끝났으니 position을 다음 항으로 넘겨주는 것이다. 

계산이 끝났다면 이제 A의 ^5 부분은 계산이 끝났으니 ^4 부분을 계산해줄 차례이다. 그렇기 때문에 degree_a를 감소시켜주는 것이다.

 

이제 degree_a와 degree_b가 일치한다. 이제는 else if문만 실행될 것이다. 왜냐?? 계수가 0인 부분도 모두 배열에 저장 시켜놓았기 때문이다.

 

 

else if문이 실행되면서 이제는 A와 B의 계수를 더해서 C에 저장해야 한다. 그 후 계산이 끝났다면 degree_a와 degree_b를 감소시켜준다.

 

그렇게 위에 설명한 while 안의 조건문에서 벗어나게 되면 다항식 덧셈 연산이 끝난 것이다. 그 후 계산이 끝난 C를 return 시켜주면 끝!

 

---

 

다음 포스팅은 하나의 다항식을 배열로 표시하는 방식에 대한 코드 분석입니다. 아래 링크를 찾고하세요!

 

https://chlduswns99.tistory.com/17

[알고리즘] 배열의 응용: 다항식 덧셈 프로그램 분석2