강의정리

[자료구조] 배열과 구조체

i1hwan

• 19 min read

배열과 구조체

  • 배열(array)과 구조체(struct)는 여러 데이터를 효과적으로 관리하기 위한 자료구조이다.
  • 배열: 같은 데이터 타입의 요소들을 연속적인 메모리 공간에 저장한다.
    • ex) 성적 처리 프로그램에서 45명의 성적(정수형) 저장
  • 구조체: 다양한 데이터 타입의 요소들을 하나의 단위로 묶어 저장한다.
    • ex) 주소록 프로그램에서 친구 정보(이름-문자열, 전화번호-문자열, 주소-문자열 등) 저장

배열(Array)

배열의 개념 및 특징

  • 가장 기본적인 순차적인(sequential) 자료구조이다.
  • 같은 형(type)의 변수를 여러 개 만들어야 할 경우 유용하다.
    • 여러 개의 변수 선언: int A0, A1, A2, A3, ..., A5;
    • 하나의 배열 선언: int A[6];
  • 같은 타입의 값을 한꺼번에 여러 개 저장할 수 있는 연속된 메모리 공간이다.
  • <인덱스(index), 요소(element)> 쌍의 집합이다.
    • 인덱스를 알면 해당하는 요소 값에 직접 접근할 수 있는 구조이다.
    • 모든 요소는 동일한 자료형을 갖는다.
    • 하나의 이름(배열 이름)을 사용하고 인덱스를 변경하여 각 요소에 접근하므로 편리하다.
      • ex) C언어에서 A[2]는 배열 A의 세 번째 요소를 의미 (인덱스는 0부터 시작)
    • K번째 항목을 참조할 때, 해당 항목의 메모리 위치가 수식으로 즉시 계산되어 바로 접근 가능하다.
    • 항목 접근의 시간 복잡도는 O(1)으로 빠르다.
  • 배열을 사용하면 반복문(for, while 등)을 활용하여 여러 요소에 대한 작업을 효율적으로 처리할 수 있다.
  • 직접 접근(direct access) 방식을 사용한다.

1차원 배열

  • 배열 선언 형식
    • 자료형 배열이름[배열의_크기];
    • ex) int score[30]; // 정수 30개를 저장할 수 있는 배열 score 선언
  • 인덱스(Index)
    • 배열 요소의 위치를 나타내는 번호이다.
    • C언어에서는 0부터 시작한다. (0-based indexing)
    • A[6] 배열의 인덱스 범위는 0부터 5까지이다.
  • 메모리 저장 방식
    • 모든 요소가 메모리 상에 연속된 위치(공간)에 저장된다.
    • 따라서 첫 번째 요소(A[0])의 주소(base address)를 알면 다른 요소의 주소를 쉽게 계산할 수 있다.
    • 인덱스가 i인 원소 A[i]의 주소 계산:
      • A[i]의 주소 = Base address + i * sizeof(자료형)
      • 여기서 sizeof(자료형)은 배열 요소 하나의 크기(byte 단위)이다.
    • 배열 A(L:U) (시작 인덱스 L, 끝 인덱스 U)의 원소 개수: U - L + 1
    • sizeof(배열이름): 배열 전체의 크기 (bytes)
    • sizeof(배열이름[0]): 배열 요소 하나의 크기 (bytes)
    • 배열의 요소 개수: sizeof(배열이름) / sizeof(배열이름[0])
  • 선언과 동시에 초기화
    • 자료형 배열이름[크기] = { 값1, 값2, ... };
    • ex) int A[6] = { 1, 2, 3, 4, 5, 6 };
    • 초기화 시 배열 크기를 생략하면 컴파일러가 초기값의 개수만큼 자동으로 크기를 할당한다.
    • ex) int A[] = { 1, 2, 3, 4, 5, 6 } // 크기가 6인 배열로 자동 할당됨

배열 크기 확인: sizeof 연산자 활용

// 예시 코드
int iA[10];
printf("iA의 크기 = %d\n", sizeof(iA)); // 출력: 40 (int가 4바이트일 경우)
printf("iA[0]의 크기 = %d\n", sizeof(iA[0])); // 출력: 4

2차원 배열

  • 배열 선언 형식
    • 자료형 배열이름[행의_크기][열의_크기];
    • ex) int A[2][3]; // 2행 3열의 정수형 2차원 배열 선언
  • 요소 접근
    • 배열이름[행_인덱스][열_인덱스]
    • ex) A[0][1] // 0행 1열의 요소
  • 메모리 저장 방식
    • 논리적으로는 행과 열의 테이블 형태이지만, 실제 메모리에는 행 우선 순서(row-major order)로 연속적으로 저장된다.
    • 즉, 0행의 모든 요소가 저장된 후 1행의 모든 요소가 저장되는 방식이다.
    • A[2][3] 배열의 저장 순서: A[0][0], A[0][1], A[0][2], A[1][0], A[1][1], A[1][2]
  • 선언과 동시에 초기화
    • 자료형 배열이름[행크기][열크기] = { {0행 값들}, {1행 값들}, ... };
    • ex) int A[2][3] = { {1, 2, 3}, {4, 5, 6} };
    • 중괄호를 생략하고 나열할 수도 있다. (행 우선 순서로 채워짐)
    • ex) int A[2][3] = { 1, 2, 3, 4, 5, 6 };
  • 크기 생략 규칙
    • 초기화 시, 첫 번째 크기(행의 크기)만 생략 가능하다. 열의 크기는 반드시 지정해야 한다.
    • ex) int A[][3] = { {1, 2, 3}, {4, 5, 6} } // 컴파일러가 행 크기를 2로 자동 계산
  • 주소 계산
    • A[i][j]의 주소 (0-based index, 열의 개수가 COLS일 때):
    • Base address + (i * COLS + j) * sizeof(자료형)
  • 원소 개수
    • A(L1:U1, L2:U2) 배열의 원소 개수: (U1 - L1 + 1) * (U2 - L2 + 1)

다차원 배열

  • 3차원 이상의 배열도 선언 가능하다.
  • 3차원 배열 선언 형식: 자료형 배열이름[면의_크기][행의_크기][열의_크기];
    • ex) int i[2][3][4]; // 2면 3행 4열의 3차원 배열
  • 메모리 저장 방식: 가장 마지막 차원(열)부터 채워지고, 다음 차원(행), 그 다음 차원(면) 순서로 연속 저장된다.
  • 주소 계산 (A[k][i][j]): (면 크기 D, 행 크기 R, 열 크기 C 가정, 0-based)
    • Base address + (k * R * C + i * C + j) * sizeof(자료형)
    • 일반적으로는 Base address + (k * 면당요소수 + i * 행당요소수 + j) * 요소크기 로 생각할 수 있다.
  • 원소 개수 (A(L1:U1, L2:U2, L3:U3)): (U1 - L1 + 1) * (U2 - L2 + 1) * (U3 - L3 + 1)
  • 초기화: 2차원 배열과 유사하게 중첩된 중괄호를 사용하여 초기화한다.

문자열 (문자 배열)

  • 문자열(string): 특별한 1차원 문자(char) 배열로, 문자의 배열을 의미한다.
  • C언어에서 문자열 상수는 큰따옴표(" ")로 묶어 표현한다. ex) "Hello World"
  • 문자열의 끝에는 자동으로 널(NULL) 문자 \0가 추가되어 문자열의 종료를 표시한다.
    • 따라서 실제 문자열 길이보다 최소 1바이트 이상 큰 문자 배열이 필요하다.
    • ex) char s[12] = "game over"; // 실제 문자 9개 + \0 1개 = 총 10바이트 사용. 배열 크기는 12로 여유 있음.
  • 문자열 처리
    • 문자열의 복사나 비교를 위해 =나 ==, < 등의 연산자를 직접 사용할 수 없다.
    • <string.h> 헤더 파일에 정의된 문자열 처리 함수를 사용해야 한다.
      • strcpy(): 문자열 복사
      • strcmp(): 문자열 비교
      • strlen(): 문자열 길이 계산 (널 문자 제외)
  • 2차원 문자 배열: 여러 개의 문자열을 저장할 때 사용한다.
    • char c[3][20]; // 최대 19자(+널문자) 길이의 문자열 3개를 저장할 수 있는 배열
    • 초기화: char c[3][20] = { "Hong Gil Dong", "Computer Department", "Seoul Korea" };
    • 각 문자열 저장: strcpy(c[0], "Hong Gil Dong");

배열의 연산 (복사)

  • 배열 자체를 한꺼번에 다른 배열에 복사하는 것은 불가능하다. (대입 연산자 = 사용 불가)
  • int A[5] = {10, 20, 30}; int B[5]; B = A //오류 발생!

배열을 복사하려면 반복문을 사용하여 각 요소를 개별적으로 복사해야 한다.

int A[5] = { 10, 20, 30 };
int B[5], i;
for (i = 0; i < 5; i++) {
    B[i] = A[i]; // 각 요소를 하나씩 복사
}

함수 매개변수로서의 배열 (Call by Reference/Address)

  • 함수에 변수를 전달하면 값에 의한 호출(call by value)이 발생한다.
    • 함수 내에서 매개변수 값을 변경해도 원본 변수에는 영향을 주지 않는다. (값이 복사되어 전달됨)
  • 함수에 배열을 전달하면 참조에 의한 호출(call by reference)과 유사하게 동작한다. (정확히는 주소에 의한 호출, call by address)
    • 배열의 이름은 배열의 첫 번째 요소의 메모리 주소를 나타낸다.
    • 함수에 배열 이름이 전달되면, 배열의 시작 주소가 전달되는 것이다. (주소가 복사됨)
    • 따라서 함수 내에서 전달받은 주소를 통해 배열 요소 값을 변경하면 원본 배열의 내용이 변경된다.
    • 함수 내에서는 전달받은 주소만으로는 배열의 끝을 알 수 없다. (배열 크기 정보가 전달되지 않음)
    • sizeof 연산자를 함수 내에서 매개변수 배열에 사용해도 전체 배열 크기를 알 수 없다. (포인터 변수의 크기만 반환됨)

주의사항: 함수에 배열을 전달할 때는 배열의 크기 정보도 함께 전달해야 한다.

void reset_array(int a[], int len) { // 배열과 크기를 함께 받음
    for (int i = 0; i < len; i++) {
        a[i] = 0; // 원본 배열의 내용이 변경됨
    }
}

int main() {
    int A[3] = {1, 2, 3};
    reset_array(A, 3); // 배열 이름(주소)과 크기 전달
    // A 배열의 내용은 {0, 0, 0}으로 변경됨
    return 0;
}

구조체(Structure)

구조체의 개념 및 필요성

  • 기존의 자료형들을 조합하여 새로운 사용자 정의 자료형을 만드는 방법이다.
  • 다양한 자료형의 데이터를 하나의 논리적 단위(모임)로 묶을 수 있다.
  • 배열과의 차이점:
    • 배열: 같은 자료형의 데이터 모임
    • 구조체: 서로 다른 자료형의 데이터 모임
  • 복잡한 데이터 형태(ex: 학생 정보 - 학번, 이름, 학점 등)를 정의하고 표현하는 데 유용하다.
  • 필드(Field), 레코드(Record), 파일(File) 개념
    • 필드: 구조체를 구성하는 각 항목(멤버 변수). ex) 학생 구조체의 학번, 이름, 학점 필드
    • 레코드: 관련된 필드들의 모임. 하나의 구조체 변수가 하나의 레코드를 나타냄. ex) 한 학생의 정보 레코드
    • 파일: 레코드들의 집합. ex) 전체 학생 정보 파일

구조체의 정의와 선언

  • 구조체는 사용하기 전에 반드시 정의되어야 한다.
    • struct Student { int id; char name[20]; double score; };
  • 구조체 선언(Declaration): 정의된 구조체 자료형을 사용하여 실제 변수를 만드는 과정.
    • struct 구조체_이름 변수명;
    • ex) struct Student s1;

typedef를 이용한 정의: 구조체 타입을 더 간결하게 사용할 수 있다.

typedef struct {
    자료형1 멤버변수1;
    자료형2 멤버변수2;
    ...
} 구조체_별칭; // typedef를 사용하면 struct 키워드 없이 별칭으로 선언 가능

// 사용 예시
typedef struct Student_t {
    int id;
    char name[20];
    double score;
} Student; // Student가 구조체 타입의 별칭이 됨

Student s2; // struct 키워드 없이 바로 선언 가능

구조체 정의(Definition): 새로운 자료형(틀)을 만드는 과정.

struct 구조체_이름 {
    자료형1 멤버변수1;
    자료형2 멤버변수2;
    ...
    자료형n 멤버변수n;
}; // 세미콜론(;) 필수
💡
정의와 선언의 차이
구조체 정의는 '틀'을 만드는 것이고, 구조체 선언은 그 '틀'로 실제 '객체(변수)'를 만든다. 쿠키로 비유해서 생각하면 편하다!

구조체 멤버 접근 및 초기화

    • 구조체변수명.멤버변수명
    • ex) s1.id = 2024001;
    • ex) s1.score = 95.5;
    • ex) strcpy(s1.name, "홍길동"); // 문자열 멤버는 strcpy 등 함수 사용
  • 선언과 동시에 초기화: 배열처럼 중괄호 {}를 사용하여 초기화할 수 있다.
    • 구조체_타입 변수명 = { 멤버1_초기값, 멤버2_초기값, ... };
    • 중괄호 안의 값들은 구조체 멤버 정의 순서대로 할당된다.
    • ex) Student a = { 202403156, "홍길동", 96.3 };

멤버 접근: 구조체 변수의 각 멤버(필드)에 접근할 때는 멤버 접근 연산자(.)를 사용한다.

구조체의 연산

  • 구조체 변수 간에는 기본적으로 대입 연산자(=)만 지원된다.
    • 한 구조체 변수의 내용을 다른 구조체 변수로 멤버별로 복사한다.
    • ex) Student s1 = { ... }; Student s2; s2 = s1 // s1의 모든 멤버 값이 s2로 복사됨
    • ex) if (s1 == s2) // 오류 발생!
    • 구조체 비교가 필요하다면, 어떤 멤버를 기준으로 비교할지 개발자가 직접 비교 함수를 구현해야 한다.

비교 연산자(==, !=, >, < 등)나 다른 산술 연산자는 기본적으로 지원되지 않는다.

// 예시: 학번(id)을 기준으로 비교하는 함수
int compareStudents(Student a, Student b) {
    if (a.id > b.id) return 1;
    else if (a.id < b.id) return -1;
    else return 0;
}

구조체를 포함하는 구조체 및 구조체 배열

  • 구조체 배열: 동일한 구조체 타입의 변수를 여러 개 저장하는 배열.
    • 구조체_타입 배열이름[크기];
    • ex) Friend list[45]; // Friend 구조체 45개를 저장할 수 있는 배열
    • 멤버 접근: 배열이름[인덱스].멤버변수명
    • ex) list[0].birthday.month = 7;
    • ex) strcpy(list[0].name, "Minyoung");

구조체를 포함하는 구조체 (중첩 구조체): 구조체의 멤버로 다른 구조체 변수를 가질 수 있다.

typedef struct {
    int month;
    int date;
} Birthday;

typedef struct {
    char name[20];
    Birthday birthday; // Birthday 구조체 변수를 멤버로 가짐
} Friend;

// 멤버 접근
Friend f1;
f1.birthday.month = 10;
f1.birthday.date = 25;

함수 매개변수로서의 구조체

    • 함수에 구조체 변수를 전달하면 기본적으로 이 방식으로 동작한다.
    • 구조체 변수의 모든 멤버 값이 복사되어 함수 내의 새로운 매개변수 구조체 변수에 저장된다.
    • 따라서 함수 내에서 매개변수 구조체의 멤버 값을 변경해도 원본 구조체 변수에는 영향을 주지 않는다.
    • 단점: 구조체의 크기가 클 경우, 함수 호출 시마다 모든 멤버를 복사하는 데 드는 비용(시간 및 메모리)이 커질 수 있다 (오버헤드 발생).
    • 구조체 변수의 주소를 함수에 전달하는 방식이다. 함수는 이 주소를 포인터 변수로 받는다.
    • 구조체 자체를 복사하는 것이 아니라 주소만 전달하므로, Call by Value 방식보다 효율적이다 (특히 큰 구조체의 경우).
    • 전달된 주소를 통해 함수 내에서 원본 구조체의 멤버 값을 직접 읽거나 수정할 수 있다.
    • 구조체 포인터를 통해 멤버에 접근할 때는 화살표 연산자(->)를 사용한다. (포인터변수명->멤버변수명)

참조에 의한 호출 (Call by Reference, 포인터 활용)

void reset_complex_by_reference(Complex *c_ptr) { // Complex 구조체 포인터를 받음
    c_ptr->real = 0.0; // 포인터를 통해 원본 구조체의 멤버 변경
    c_ptr->imag = 0.0; // 포인터를 통해 원본 구조체의 멤버 변경
}

int main() {
    Complex a = {1.0, 2.0};
    reset_complex_by_reference(&a); // 구조체 a의 주소(&a)를 전달
    // 함수 호출 후 a.real과 a.imag는 0.0으로 변경됨 (원본 수정됨)
    return 0;
}

값에 의한 호출 (Call by Value, 기본 방식)

void print_complex_by_value(Complex c) { // Complex 구조체 변수 c를 값으로 받음
    // c는 원본의 복사본이므로, 여기서 c를 변경해도 원본은 바뀌지 않음
    printf("%4.1f + %4.1fi\n", c.real, c.imag);
}
💡
함수에서 구조체 내용을 읽기만 할 때는 Call by Value가 간단하지만, 원본을 수정해야 하거나 구조체가 커서 효율성이 중요할 때는 Call by Reference (포인터 사용) 방식이 더 유용하다.

4. 배열과 구조체의 응용

행렬 표현 (2차원 배열 활용)

  • 수학의 행렬(matrix)은 2차원 배열을 사용하여 자연스럽게 표현할 수 있다.
  • int M[3][3]; // 3x3 정수 행렬 M 선언
  • 행렬 연산: 2차원 배열의 인덱스를 이용하여 덧셈, 곱셈, 전치(transpose) 등의 연산을 구현할 수 있다.
  • 전치 행렬(Transpose Matrix): 원본 행렬의 행과 열을 맞바꾼 행렬. M[i][j] 와 M[j][i] 를 교환하여 구할 수 있다.
    • 장점: 행렬 연산을 비교적 간단하게 구현할 수 있다.
    • 단점: 행렬 요소 대부분이 0인 희소 행렬(sparse matrix)의 경우, 0 값을 저장하기 위해 불필요한 메모리 공간을 많이 사용하게 된다(공간 낭비).

희소 행렬 표현

  • 희소 행렬(Sparse Matrix): 행렬의 요소 대부분(ex: 70% 이상)이 0인 행렬.
  • 효율적인 표현 방법: 0이 아닌 요소들만 저장하여 메모리 공간을 절약한다.
    • 방법: 0이 아닌 각 요소의 <행(row), 열(col), 값(value)> 정보를 저장한다.
    • 장점: 희소 행렬의 경우 메모리 공간을 크게 절약할 수 있다.
    • 단점: 행렬 연산(덧셈, 곱셈, 전치 등) 구현이 2차원 배열을 사용할 때보다 복잡해진다.
  • 희소 행렬 전치 연산: 각 항(Term)의 row와 col 값을 서로 교환하면 된다. 값(value)은 변경하지 않는다.

2차원 배열 대신, 구조체 배열을 사용하여 표현할 수 있다.

typedef struct {
    int row;
    int col;
    int value;
} Term; // 0이 아닌 항(Term)을 위한 구조체

Term sparseMatrix[NUMBER_OF_NONZERO_TERMS]; // 0이 아닌 항의 개수만큼 배열 선언

다항식 표현 (배열/구조체 활용)

  • 다항식(Polynomial): $p(x) = a_n * x^n + a_{n-1} * x^{n-1} + ... + a_1 * x + a_0$ 형태의 식.
  • 표현 방법 1: 계수 배열 사용 (밀집 표현)
    • 다항식의 모든 항의 계수를 1차원 배열에 저장한다. 배열의 인덱스는 해당 항의 차수(지수)를 나타낸다.
    • 최고차항(degree) 정보도 함께 저장해야 한다.
    • 계수 저장 방식:
      • 방법 A: coef[0]에 최고차항 계수, coef[degree]에 0차항 계수 저장 (슬라이드 예시와 다름)
      • 방법 B: coef[0]에 0차항 계수, coef[degree]에 최고차항 계수 저장 (슬라이드 예시 방식) - 덧셈/곱셈 구현 시 인덱스 접근이 편리
    • 장점: 다항식 연산(덧셈, 곱셈 등) 구현이 비교적 간단하다.
    • 단점: 희소 다항식(0인 항이 많은 경우)의 경우, 0인 계수를 저장하기 위해 메모리 공간을 낭비한다.

구조체 활용:

#define MAX_DEGREE 1000 // 최대 차수 정의
typedef struct {
    int degree; // 다항식의 최고 차수
    float coef[MAX_DEGREE + 1]; // 계수 저장을 위한 배열 (0차항부터 최고차항까지)
} Polynomial;

희소 다항식 표현 (구조체 활용)

  • 희소 다항식(Sparse Polynomial): 0이 아닌 항의 개수가 전체 차수에 비해 매우 적은 다항식.
    • ex) $p(x) = 10x^{1000} + 6$
  • 효율적인 표현 방법: 0이 아닌 항들만 저장한다.
    • 각 항의 <계수(coefficient), 지수(exponent)> 정보를 저장한다.
    • 장점: 희소 다항식의 경우 메모리를 매우 효율적으로 사용한다.
    • 단점: 다항식 연산 구현이 밀집 표현 방식보다 복잡해진다. (지수를 비교하며 연산 수행)
  • 희소 다항식 덧셈 연산: 두 다항식의 항들을 지수(expon) 기준으로 비교하며 연산을 수행한다.
    • 지수가 같으면 계수를 더한다. (더한 결과가 0이면 저장하지 않음)
    • 지수가 다르면 지수가 더 큰 항을 결과 다항식에 추가한다.
    • 한쪽 다항식의 모든 항이 처리되면 남은 다른 쪽 다항식의 항들을 모두 결과에 추가한다.

구조체 활용:

typedef struct {
    float coeff; // 계수
    int expon;   // 지수
} Term; // 0이 아닌 항을 위한 구조체

#define MAX_TERMS 100 // 최대 항 개수 정의
typedef struct {
    int nTerms; // 0이 아닌 항의 개수
    Term term[MAX_TERMS]; // 0이 아닌 항들을 저장하는 구조체 배열
} SparsePoly;

레퍼런스

“이 글은 『쉽게 배우는 C 자료구조』(최영규 및 천인국, 2024)의 내용을 토대로 재구성된 자료입니다.”​

💻 이 글은 자료구조 시리즈의 일부입니다.

← 이전글: 자료구조와 알고리즘 | 다음글: 스택 →

다른 글 더 읽어보기