Chapter 3 구조체, 배열, 포인터
구조체
구조체란, 사용자가 원하는 자료형들을 모아 새롭게 데이터 타입을 만들 수 있다.
struct Person {
char name[10];
int age;
}
int main(){
struct Person p1;
retrun 0;
}
같은 자료형만 사용가능한 배열과 다르게 서로 다른 자료형들을 모아 사용할 수 있다.
그러나 이런 식의 구조체는 이후 선언 시, struct (구조체 이름)으로 길게 작성해야 한다.
짧게 P로만 작성할 수는 없을까? 우리의 손목 건강을 위해 typedef가 존재한다.
typedef struct {
char name[10];
int age;
} Person;
int main(){
Person p1;
retrun 0;
}
이렇게 typedef를 통해 선언하면 다시 이름을 지어주어 짧고, 가독성 좋게 작성 가능하다.
배열
배열이란, 같은 자료형을 순차적으로 나타낼 수 있는 자료형이다.
int a[10];
이때, a는 0부터 9까지의 인덱스 번호를 가진다. a[0] ~ a[9]
1차원 배열의 활용
배열은 문제해결에 있어 굉장히 유용하게 사용 가능하다.
아래는 배열을 이용한 다항식 연산과 행렬 계산이다.
다항식
배열을 이용해 다항식을 정의하는 경우, 두가지 형태로 나타낼 수 있다.
먼저 배열에 계수를 저장하고 차수는 배열의 인덱스 번호를 이용하는 코드이다.
#include <stdio.h>
struct POLY{
int max_degree = 2;
int coef[100] = { 0, };
};
int main(){
// 2x^2 + 3x + 1
struct POLY p1 = { 2, {1, 3, 2} };
retrun 0;
}
배열의 최대차수와 계수만 순서대로 적으면 다항식을 표현할 수 있다.
그러나 이런 식의 다항식은 좀 아쉬운 부분이 존재한다.
바로 $x^9 + 1$같은 경우, 8차부터 2차항까지 모두 계수가 $0$으로 값이 필요없지만, 배열의 인덱스 번호를 이용하기 위해 배열의 크기를 10으로 만들어야 한다는 점이다.
계수가 커지고, 중간의 계수가 없을수록 메모리적으로 낭비가 심한 방법이다.
이를 해결하는 방법은 차수와 계수를 모두 저장하는 방법이다.
#include <stdio.h>
struct TERM
{
int coef;
int degree;
};
struct ePOLY{
int valid_num;
struct TERM terms[100];
};
int main(){
// 2x^3 + 3x + 1
struct ePOLY p3 = { 3, { {2, 3}, {3, 1}, {1, 0} } };
retrun 0;
}
이 방법의 경우, 계수의 최대값과 각 항의 계수와 차수를 적어주면 사용가능하다.
고려해야 할 부분이 하나 더 생기지만 더이상 메모리를 낭비하지 않고, 차수만큼의 배열만 만들어주면 된다.
이제 배열을 이용해 다항식을 계산해 보자.
계수와 배열의 인데스를 이용한 다항식
#include <stdio.h>
// 차수와 배열을 이용한 다항식
struct POLY {
int max_degree;
int coef[100];
};
// 다항식 출력
void showPolynomoal(struct POLY _p) {
int first = 1;
for (int i = _p.max_degree; i >= 0; i--) {
if (_p.coef[i] != 0) {
if (!first) printf(" + ");
printf("%d*x^%d", _p.coef[i], i);
first = 0;
}
}
if (first) printf("0");
printf("\n");
}
// 다항식의 덧셈
struct POLY addPoly(struct POLY _p1, struct POLY _p2) {
int max = (_p1.max_degree > _p2.max_degree) ? _p1.max_degree : _p2.max_degree;
struct POLY temp = {0, };
temp.max_degree = max;
for (int i = 0; i <= max; i++) {
int coef1 = (i <= _p1.max_degree) ? _p1.coef[i] : 0;
int coef2 = (i <= _p2.max_degree) ? _p2.coef[i] : 0;
temp.coef[i] = coef1 + coef2;
}
return temp;
}
// 다항식 p1, p2를 입력받아 덧셈 실행
int main() {
struct POLY p1 = {0, };
struct POLY p2 = {0, };
printf("p1의 최대 차수: ");
scanf("%d", &p1.max_degree);
printf("p2의 최대 차수: ");
scanf("%d", &p2.max_degree);
for (int i = 0; i <= p1.max_degree; i++) {
printf("p1의 %d항의 계수: ", i);
scanf("%d", &p1.coef[i]);
}
for (int i = 0; i <= p2.max_degree; i++) {
printf("p2의 %d항의 계수: ", i);
scanf("%d", &p2.coef[i]);
}
struct POLY p3 = addPoly(p1, p2);
printf("\np1: ");
showPolynomoal(p1);
printf("p2: ");
showPolynomoal(p2);
printf("p1 + p2: ");
showPolynomoal(p3);
return 0;
}
차수와 계수를 저장하는 다항식
#include <stdio.h>
// 다항식 중 항 하나의 계수와 차수
struct TERM {
int coef;
int degree;
};
// 다항식 (유효한 항 개수 + TERM 배열)
struct ePOLY {
int valid_num;
struct TERM terms[100];
};
// 다항식 출력
void showEfficientPoly(struct ePOLY _p) {
for (int i = 0; i < _p.valid_num; i++) {
if (i > 0) {
printf(" + ");
}
if (_p.terms[i].degree == 0) {
printf("%d", _p.terms[i].coef);
} else {
printf("%d*x^%d", _p.terms[i].coef, _p.terms[i].degree);
}
}
printf("\n");
}
// 다항식의 덧셈
struct ePOLY addEfficientPoly(struct ePOLY _p1, struct ePOLY _p2) {
int count = 0, i = 0, j = 0;
struct ePOLY temp = { 0, };
while (i < _p1.valid_num && j < _p2.valid_num) {
if (_p1.terms[i].degree > _p2.terms[j].degree) {
temp.terms[count] = _p1.terms[i];
i++;
} else if (_p1.terms[i].degree < _p2.terms[j].degree) {
temp.terms[count] = _p2.terms[j];
j++;
} else {
temp.terms[count].degree = _p1.terms[i].degree;
temp.terms[count].coef = _p1.terms[i].coef + _p2.terms[j].coef;
i++, j++;
}
count++;
}
while (i < _p1.valid_num) {
temp.terms[count++] = _p1.terms[i++];
}
while (j < _p2.valid_num) {
temp.terms[count++] = _p2.terms[j++];
}
temp.valid_num = count;
return temp;
}
// 다항식 p1, p2를 입력받아 덧셈 실행
int main() {
struct ePOLY p1 = { 0, };
struct ePOLY p2 = { 0, };
printf("p1의 항의 개수: ");
scanf("%d", &p1.valid_num);
printf("p2의 항의 개수: ");
scanf("%d", &p2.valid_num);
for (int i = 0; i < p1.valid_num; i++) {
printf("p1의 %d번째 항의 계수와 차수: ", i + 1);
scanf("%d %d", &p1.terms[i].coef, &p1.terms[i].degree);
}
for (int i = 0; i < p2.valid_num; i++) {
printf("p2의 %d번째 항의 계수와 차수: ", i + 1);
scanf("%d %d", &p2.terms[i].coef, &p2.terms[i].degree);
}
struct ePOLY p3 = addEfficientPoly(p1, p2);
printf("\np1: ");
showEfficientPoly(p1);
printf("p2: ");
showEfficientPoly(p2);
printf("p1 + p2: ");
showEfficientPoly(p3);
return 0;
}
2차원 배열의 활용
2차원 배열은 우리가 흔히 생각하는 행렬을 수행하기 좋다.
아래는 2차원 배열을 이용한 행렬의 표현 방법이다.
행렬 코드 추가
그러나 이러한 방법은 희소행렬를 구하는 데에 있어 메모리를 낭비시킨다.
희소행렬(sparse matrix) : 대부분의 항들이 0인 배열
희소행렬의 항 중 유효한 부분만 가져와 행렬을 작성해 보자.
행렬 코드 추가
이제 2차원 배열을 이용한 행렬들로 여러가지 행렬의 연산을 수행할 수 있다.
아래는 행렬의 전치에 대해 코드이다.
전치 행렬 코드
포인터
포인터란, 데이터 타입의 일종으로 값을 담는 다른 자료형들과 다르게 주소를 담는 자료형이다.
*연산자
대입연산자(=)를 기준으로 오른쪽은 주소의 값을 가져온다.
대입연산자(=)를 기준으로 왼쪽은 그 주소에 값을 넣는다.
동적 할당
c에서 배열을 통해 데이터를 저장해야 하는 경우, 우리는 초기에 배열에 들어갈 최대치만큼 배열을 선언해주어야 한다.
그러나 최대가 100인 배열에 10만 넣는 경우, 메모리를 비효율적으로 쓴다는 생각이 든다.
이럴 때 사용할 수 있는게 바로 동적 할당이다.
동적 할당은 실행 시간 동안 사용할 메모리 공간을 할당받는 것을 의미한다.
프로그램이 실행하는 순간, 그 순간 필요한 메모리의 양만큼 할당받아 보다 효율적인 메모리 활용이 가능하다.
사용법은 다음 코드와 같다.
#include <stdio.h>
#include <stdlib.h> // malloc, free 동적 할당을 위해 필요한 헤더파일
int main(){
int n = 0;
scanf("%d", &n);
// num은 자료형의 크기 * 필요한 배열의 사이즈의 메모리를 할당
int *num = (int*)malloc(sizeof(int) * n);
// 동적 할당 해제, 반드시 필요, 생략 시 메모리 누수 가능성 존재.
free(num);
retrun 0;
}
<stdlib.h> 라는 헤더 파일을 추가하고, malloc 함수를 통해 동적 할당이 가능하다.
void* malloc(size_t size)
댓글남기기