[자료구조] 2주차

[자료구조] 2주차

- 영남대학교 K-MOOC 자료구조 수업 

- 더 깔끔한 정리: https://www.notion.so/2-797cbc9b1fb74b059d3de6897512aa9d?pvs=4

 

2-1. 배열과 구조체의 정의

1. 배열의 정의

• 동일한 타입의 데이터들을 묶는 구조
• 메모리의 연속된 위치에 차례대로 저장
• <인덱스, 데이터> 쌍의 집합
  • 1차원 배열: {<0, “김철수”>, <1, “홍길동”>}
  • 2차원 배열: {<(0,0), 10>, <(0,1), 20>}

2. C언어에서의 배열

• 1차원 배열
  • int a[5]
    • 인덱스는 0부터 시작
    • a[0], a[1], a[2], a[3], a[4]
• 2차원 배열
  • int B[2][2];
    • B[0][0], B[0][1], B[1][0], B[1][1]
• 배열과 포인터
  • C에서 이 둘을 동일한 개념으로 사용한다
  • int A[5], *pA = A;
    • A: 배열의 시작 주소 (==&A[0])를 말한다
    • A + 3: A[3]의 주소 (==&A[3])
    • (A + 3): A[3]의 내용 (==A[3])배열과 포인터
    • func() 에서 A[3]에 시작 주소가 복사 되게 된다. 시작 주소가 복사되더라도 원래 배열의 주소가 바뀌는 것은 아니기 때문에 A[3]가 존재하던 주소의 값이 5로 변경되게 된다. 배열과 포인터가 동일한 개념으로 사용된다는 것 주의!
• A[5]와 같이 프로그램에서 바로 배열의 크기를 수정할 수도 있고, 경우에 따라서 malloc 함수를 이용해서 동적으로 배열을 할당 받을 수도 있다.

• 위와 같이 이차원 배열도 공간을 할당 받을 수 있다.

 

 

3. 구조체

(1) 구조체 정의

• 하나 이상의 기본 자료형을 기반으로 사용자 정의 자료형을 만들 수 있는 문법 요소
• 다양한 자료 형을 포함 (배열과 다른 지점)
  • 배열: 동일한 자료형의 모음

struct humanBeing {
	char name[10];
	int age;
	double salary;
};
typedef struct humanBeing human_being

• 위와 같이 구조체를 사용자 정의형으로 만들어서 사용할 수 있다.

(2) 구조체 비교

• 구조체의 내용이 동일한지를 검사하는 방법
  • 구조체의 모든 속성들이 같은지를 하나씩 비교한다.

  if (person1 == person2) // C언어에서 지원되지 않는 문법이다.
  
  int humans_equal (human_being person1, human_being person2)
  {
  	if (strcmp (person1.name, person2.name))
  		return FALSE;
  	if (person1.age != person2.age)
  		return FALSE;
  	if (person1.salary != person2.salary)
  		return FALSE;
  	return TRUE;
  }
  // 위 방법처럼 각각의 요소에 대해 비교문을 써야 한다
  
  memcmp(&person1, &person2, sizeof(human_being))
  // 위와 같은 함수로 간편하게 비교할 수도 있다.
  

(3) 자기 참조 구조체

• 자기 자신을 가리키는 포인터를 속성으로 갖는 구조체

struct list {
	char data;
	struct list *link;
}

• 연결 리스트의 구현에 많이 사용됨

 

 

4. 배열의 주소 계산

• 다차원 배열을 저장하는 두 가지 방법
  • 행 우선 순서: 앞이 [0]인 것부터 먼저 저장하자
  • 열 우선 순서: 뒤가 [0]인 것부터 먼저 저장하자
  • 주로 많이 쓰는 것은 Row major order 를 사용한다. 그래서 오늘은 행 우선 순서에 대해 알아본다.

(1) 행 우선 순서의 주소 계산

• upper - 원소의 개수를 표현함
• 2차원 배열
  • 어차피 [i][0]부터 [i][upper1]까지 저장되고 나서야 i가 하나 올라가므로 a + i * upper1가 되는 것이다. A[i][j]는 당연히 앞의 식에 j 를 더하면 된다.
• 위의 식을 이용하여 배열에서 주소를 쉽게 구할 수 있다.

(2) 행 우선 순서의 저장 규칙

• 결국 풀어보면 i부터 upper n-1 까지 다 곱해서 더하는 것과 같다.

 

 

 

 

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

1. 순서 리스트

• 데이터들의 순서가 유지되는 집합

(1) 순서 리스트의 예

• 한 주의 요일들: 일, 월, 화, 수, 목, 금, 토
• 섞여진 카드들: A, 2, 3, 4, 5, …
• 미국의 2차 세계대전 참전 연도: 1941, 1942, 1943, 1944, 1945
• 스위스의 2차 세계대전 참전 연도: () 중립국이라 참전 X
  • 원소가 없는 집합도 순서리스트에 포함이 된다

(2) 순서 리스트의 연산

• 길이 계산 / 읽기 / 검색 / 대체 / 추가 / 삭제 등 가능
  • 추가는 한 칸씩 밀리게 되므로 시간이 걸리는 연산
  • 삭제는 한 칸씩 앞으로 이동하게 되므로 시간이 걸리는 연산
  • 순서리스트를 효율적으로 구현하는 것이 성능에 중요한 영향

 

 

2. 다항식 소개

• 주소 계산은 어렵지만 추가나 삭제에 강점을 보인다

(1) 순서 리스트를 구현하는 두 가지 방법

• 배열: i번째 데이터를 배열 인덱스 i에 저장
• 연결 리스트, 리스트로 연결됨

(2) 다항식의 정의

• Coef(p, e): e 지수에 해당되는 다항식의 계수를 가져와라
• Lead_Exp(p): 최고 차항을 가져와라
• Attach(p, a, e): a * x^e
  • e가 이 다항식에 포함이 되어 있다면 오류가 난다
• 오늘은 Add(p1, p2)에 대해서 자세히 알아본다

 

 

3. C 언어에서 다항식 구현

(1) 방법 1: 모든 지수의 계수들을 내림차순으로 저장

• 최고차항: 3
• x^3 = 2, x^2 = 1, x^1 = 0, -1 (2, 1, 0, -1)
• 만약 x^100 + 1 이라면 (문제점)
  • degree = 100
  • coef = 0부터 99까지 모두 다 0이고 100일 때 겨우 1
  • 항의 수가 굉장히 적은데 최고 차항이 굉장히 큰 경우 메모리 낭비가 심해진다.

(2) 방법 2: 지수와 계수를 모두 저장

• 계수가 0이 아닌 모든 항에 대해서 지수와 계수를 다 같이 저장하는 방식
• x^100 + 1은 항이 두 개
  • 첫 번째 항에 대해 계수는 1, 지수는 100
  • 두 번째 항에 대해 계수는 1, 지수는 0
  • {1, 100), (1, 0)} 으로 저장하는 방식
  • 최고차항이 차례대로 감소할 때는 이 방식이 필요하지만, 위 같은 식에서는 모든 계수를 표현하면 메모리 낭비가 되므로 이 방법이 유리하다.
  • 일단 편의상 이 표현 방식을 가정하도록 한다.
• 여러 개의 다항식이 하나의 일차원 배열에 저장된다고 가정
  • 하나의 배열에 넣어져서 메모리 낭비를 줄인다.
  • avail은 배열에서 빈 위치를 가리킨다.

 

 

4. 다항식의 합 구하기

(1) 먼저 최고차항의 지수를 비교한다

(2) 지수가 같은 경우 / 앞의 것이 더 큰 경우 / 뒤의 것이 더 큰 경우를 따져야 한다

(3) 최고 차항이 같으면 계수를 더한다

(4) 오른쪽이 더 크다면 큰 다항식의 항을 복사한다

b = Zero();
while (!IsZero(a) && !IsZero(b)) do {
	switch (COMPARE(Lead_Exp(a), Lead_Exp(b))) {
		case -1: 
			d = Attach (d, Coef(b, Lead_Exp(b)), Lead_Exp(b));
			b = Remove(b, Lead_Exp(b));
			break;
		case 0:
			sum = Coef(a, Lead_Exp(a)) + Coef(b, Lead_Exp(b));
			if (sum)
				Attach(d, sum, Lead_Exp(a));
			a = Remove(a, Lead_Exp(a));
			b = Remove(b, Lead_Exp(b));
			break;
		case 1:
			d = Attach(d, Coef(a, Lead_Exp(a)), Lead_Exp(a));
			a = Remove(a, Lead_Exp(a));
		}
}

• 수도 코드
  • A에 다항식이 남아있고 b에도 남아있을 때까지 반복
  • 두 개를 비교해서 만약 b가 더 크다면 b에 현재 최고차항의 지수와 그 항의 계수를 d에 추가
  • a가 더 크다면 a 최고차항 계수와 그 다음 최고 차항의 지수를 갖는 새로운 항을 d에 추가
  • 두 개의 최고차항의 지수가 동일하다면 계수를 더해봐야 한다
  • 즉, 더해서 0보다 크다면 합이 계수가 되고, 지수는 최고차항이 되는 항이 새로 추가가 되고, 이후는 a,b를 모두 다 보았기 때문에 a도 다음 항, b도 다음 항 넘어가면 된다.

void padd(int starta, int finisha, int startb, int finishb, int *starrd, int *finishd)
{
	float coefficient;
	*startd = avail  //avail은 terms[]에서 비어있는 공간의 색인
	while (starta <= finisha && startb <= finishb)
		switch (COMPARE(terms[starta].expon, terms[startb].expon))
		{
			case -1:  // a.expon < b.expon
				attach(terms[startb].coef, terms[startb].expon);
				startb++;
				break;
			case 0:   // equal exponents
				coefficient = terms[starta].coef + terms[startb].coef;
				if (coefficient) attach(coefficient, terms[starta].expon);
				starta++; startb++;   // starta와 startb를 모두 증가
				break;
			case 1:   // a.expon > b.expon
				attach(terms[starta].coef, terms[starta].expon);
				starta++;   //starta만 증가
		}
	// a의 나머지 항을 d에 모두 추가. 항이 없을 경우?
	for ( ; starta <= finisha; starta++ )
		attach(terms[starta].coef, terms[starta].expon);
	// b의 나머지 항들을 d에 모두 추가
	for ( ; startb <= finishb; startb++ )
		attach(terms[startb].coef, temrs[startb].expon);
	*finishd = avail-1;
}	

• 위 코드는 C 언어로 작성한 코드다.
  • 시간 복잡도: 반복문이 얼마나 돌 것인가
  • 최악의 경우 a와 b가 한 번씩 검사됨
  • 즉, O(a의 항의 수 + b의 항의 수) 만큼의 시간복잡도를 갖는다.

void attach(float coeffcient, int exponent)
{
	// 다항식에 새로운 항을 추가하는 함수
	if (avail >= MAX_TERMS) {
		fprintf(stderr, "Too many terms in the polynomial \\n.");
		exit(1);
	}
	terms[avail].coef = coefficient;
	terms[avail++].expon == exponent; // avail은 여기에서 증가됨

• attach 함수의 구현
  • 새로운 항에 계수와 지수가 주어지면 현재 avail이 가리키는 곳에 coeffcient, exponent를 복사
  • 그 다음 avail을 한 칸 증가시키는 함수

• 예시 문제

a = 3x^14 + 2x^8 + 1
b = 8x^14 - 3x^10 + 10x^6

1. a, b 순서로 계수와 지수를 나누어 배열에 저장
2. 계수가 14로 같아서 3과 8을 더하고 결과를 startd에 저장, starta와 startb는 한 칸씩 증가
3. starta와 startb를 비교, 계수 10이 더 커서 startb를 뒤에 저장, startb를 한 칸 증가
4. starta가 8로 더 커서 뒤에 저장, starta를 한 칸 증가
5. statb가 6으로 더 커서 뒤에 저장, startb를 한 칸 증가
6. startb가 finishb와 같아져서 starta 값(상수항)을 뒤에 추가
7. 결과

d = 11x^14 - 3x^10 + 2x^8 + 10x^6 + 1

 

 

요약 정리

• 순서 리스트의 개념을 설명
• 다항식을 표현하는 방법을 설명
• C 언어에서 다항식의 합을 구현하는 알고리즘