[자료구조] 선형 리스트 - 2

지난 번에 선형 리스트가 무엇인지, 

선형 리스트에서의 삽입 / 삭제 방법과 특징에 대해 공부했다.

이전 포스트 바로가기

이번 포스팅에서는 다항식(polynomial) 을 선형 리스트(배열) 로 표현하는 방법에 대해 다루겠다.

선형 리스트로 다항식(polynomial) 표현

다항식(polynomial) 은 계수(coefficient) / 변수(variable) / 지수(exponent) 로 구성 된 항(term) 들의 합 이다.

항 들의 순서는 지수의 내림차순으로 정렬된다.

순서가 정해져 있으므로 선형 리스트를 활용하여 표현할 수 있다.

다음 다항식을 선형 리스트(배열) 로 표현 해 보겠다.

우선, 첫 번째 항의 지수를 통해 주어진 다항식의 최고차항을 알 수 있으며 이는 리스트의 크기가 된다. 

주어진 다항식의 지수가 3이지만 마지막 항의 상수까지 생각하여 리스트(배열) 의 최대 크기는 3 + 1로 총 4가 된다.

 

그 다음, 각 인덱스에 항(term) 의 계수를 저장하면 된다.

프로그래밍으로 구현 시 확인해야 할 로직은 

다항식은 내림차순이므로 0번 인덱스부터 최고차항의 계수를 저장해야 한다는 점과

각 항의 계수를 확인하여 값이 0인지 아닌지를 확인하는 로직이 필요하다. 

위 다항식을 보면   항의 계수가 존재하지 않으므로 해당 인덱스에는 0을 저장한다.

※ 만약 0으로 표기하지 않고 그 다음 계수를 저장한다면 역 변환 시 해당 계수가 몇 번째 항인지 확인 할 수 없으며, 그 다음 항 들도 꼬이게 된다. 

 

만약, 최고차항이 3인 다항식이 아닌 1000인 다항식이 주어졌다면

총 1001개의 공간을 가진 리스트를 만들면 된다.

하지만,

최고차항이 1000이지만 항의 갯수는 4개뿐인 다항식이 있다. (희소다항식)

즉, 1001개의 공간 중에 값이 유효한 공간은 4개이고 997개의 공간은 0으로 채워지는 비효율적인 배열이 된다.

이 경우에는 2차원 배열을 사용하면 공간을 효율적으로 활용할 수 있다.

행(row) 은 다항식의 지수를, 열(col) 은 각 항의 계수를 저장했다.

2차원 배열을 사용하여 최고차항이 1000인 희소다항식을 비효율적인 공간 없이 표현했다.

※ 다른 예제를 참고하다보면 지수를 열(col), 계수를 행(row) 에 저장하는 경우도 있는데 따로 정해져 있는 규칙은 없는 것 같다. 

   단, 무엇을 가리키는지 코멘트 명시 해 놓자..

* 잘못 된 내용은 댓글로 남겨주세요.

'Study memo' 카테고리의 다른 글

[자료구조] Queue  (1)	2018.06.01
[자료구조] 선형 리스트 - 2  (0)	2018.05.19
[자료구조] 선형 리스트 - 1  (0)	2018.05.12