# 자료구조 (1)

## 1\. 배열

### 1-1. 배열이란?

배열은 **같은 타입의 데이터를 연속된 메모리 공간에 나란히 저장하는 자료구조** 다.

변수 하나에는 값 하나만 저장할 수 있다. 학생 100명의 점수를 저장해야 한다면 `int score1, score2, score3, ... score100;` 이렇게 변수를 100개 만들어야 할까? 비현실적이다. 배열을 쓰면 `int score[100];` 한 줄로 해결된다.

JavaScript의 배열과 비슷한 개념이지만, 결정적인 차이가 있다. JavaScript 배열은 서로 다른 타입을 섞어 넣을 수 있고 크기도 자유롭게 변한다. C 배열은 **하나의 타입만** 저장할 수 있고, **크기가 고정** 되어 있다.

### 1-2. 배열의 이해와 사용

#### 배열의 선언 구조

```c
자료형 배열이름[크기];
```

```c
int scores[5];        // int 5개를 담는 배열
double temps[7];      // double 7개를 담는 배열
char name[20];        // char 20개를 담는 배열 (문자열용)
```

`int scores[5]` 를 선언하면 메모리에 `int` 크기(4바이트) × 5 = 20바이트의 연속된 공간이 확보된다. 각 요소는 `scores[0]`부터 `scores[4]`까지 인덱스로 접근한다. 인덱스는 **0부터 시작** 한다.

```c
scores[0] = 90;
scores[1] = 85;
scores[2] = 78;
printf("%d\n", scores[1]);  // 85
```

#### 배열의 속성

배열 이름은 **배열 첫 번째 요소의 주소** 를 가리킨다. 즉 `scores`와 `&scores[0]`은 같은 값이다.

```c
int scores[5] = {90, 85, 78, 92, 88};
printf("%p\n", scores);       // 배열 시작 주소
printf("%p\n", &scores[0]);   // 같은 주소
```

배열의 전체 크기는 `sizeof` 연산자로 구할 수 있다. 요소 개수는 전체 크기를 요소 하나의 크기로 나누면 된다.

```c
int arr[5];
printf("전체 크기: %lu\n", sizeof(arr));        // 20 (4 × 5)
printf("요소 개수: %lu\n", sizeof(arr) / sizeof(arr[0]));  // 5
```

다만 배열을 함수에 매개변수로 넘기면 **포인터로 변환** 되기 때문에, 함수 안에서 `sizeof`로 배열 크기를 구할 수 없다. 그래서 배열을 함수에 넘길 때는 크기도 함께 전달하는 것이 일반적이다.

```c
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
}
```

#### 배열의 크기는 왜 상수여야 하는가?

> **컴파일타임과 런타임**
> 
> 이 개념을 이해하려면 먼저 **컴파일타임(compile time)** 과 **런타임(runtime)** 의 차이를 알아야 한다.
> 
> **컴파일타임** 은 소스 코드가 기계어로 번역되는 시점이다. 컴파일러가 코드를 읽고, 문법을 검사하고, 실행 파일을 만드는 과정이 여기에 해당한다. **런타임** 은 그 실행 파일이 실제로 실행되는 시점이다. 사용자 입력을 받거나, 파일을 읽거나, 계산 결과가 나오는 것은 전부 런타임에 일어난다.
> 
> 쉽게 말해 컴파일타임은 "코드를 번역하는 시점", 런타임은 "프로그램이 돌아가는 시점"이다.

C에서 일반 배열(정적 배열)은 **스택 메모리** 에 할당된다. 스택은 함수가 호출될 때 필요한 공간을 미리 계산해서 확보하는 구조다. 이 계산은 **컴파일타임** 에 이루어진다.

```c
int arr[5];  // 컴파일러가 "20바이트 필요하겠구나" 판단 가능
```

컴파일러는 `5`라는 숫자를 보고 4 × 5 = 20바이트를 확보하면 된다는 걸 바로 알 수 있다. 그런데 크기가 변수라면 어떻게 될까?

```c
int n;
scanf("%d", &n);
int arr[n];  // n은 런타임에야 알 수 있음
```

`n`의 값은 사용자가 입력해야 알 수 있다. 컴파일 시점에서는 배열에 얼마만큼의 메모리를 잡아야 할지 결정할 수 없다. 그래서 C89/C90 표준에서는 배열 크기를 반드시 **상수** 로 지정해야 한다.

```c
int arr[5];            // OK — 상수
const int SIZE = 5;
int arr2[SIZE];        // 컴파일러에 따라 다름 (C에서 const는 진정한 상수가 아님)
#define MAX 100
int arr3[MAX];         // OK — 매크로 상수는 전처리 단계에서 치환됨
```

C99부터는 **가변 길이 배열(VLA, Variable Length Array)** 이 도입되어 `int arr[n]` 같은 문법이 허용되기도 한다. 하지만 Visual Studio에서는 VLA를 지원하지 않으므로, 수업 환경에서는 배열 크기를 항상 상수로 지정해야 한다.

크기가 런타임에 결정되어야 하는 경우에는 `malloc`을 사용한 **동적 메모리 할당** 으로 해결한다. 이건 이후에 포인터와 함께 다루게 된다.

#### 배열의 초기화

배열을 선언하면서 동시에 값을 넣을 수 있다.

```c
int arr[5] = {10, 20, 30, 40, 50};
```

요소 수보다 적게 초기화하면 나머지는 **자동으로 0** 이 된다.

```c
int arr[5] = {10, 20};  // {10, 20, 0, 0, 0}
int arr2[5] = {0};       // 전부 0으로 초기화
```

크기를 생략하면 초기화한 요소 수에 맞춰 자동으로 크기가 결정된다.

```c
int arr[] = {10, 20, 30};  // 크기 3짜리 배열
```

초기화하지 않은 지역 배열에는 **쓰레기값** 이 들어있다. 전역이나 `static` 배열은 자동으로 0으로 초기화된다.

```c
int globalArr[5];  // 전역 — 전부 0

void foo(void) {
    int localArr[5];         // 지역 — 쓰레기값
    static int staticArr[5]; // 정적 — 전부 0
}
```

### 1-3. 배열과 문자열

C에는 JavaScript의 `string` 같은 문자열 타입이 없다. 대신 `char` **배열** 로 문자열을 표현한다.

#### 문자열 변수

C에서 문자열은 **널 문자(**`\0`**)로 끝나는** `char` **배열** 이다. 널 문자는 문자열의 끝을 알려주는 표식이다. 모든 문자열 처리 함수(`printf`의 `%s`, `strlen`, `strcpy` 등)는 이 `\0`을 기준으로 문자열의 끝을 판단한다.

```c
char name[6] = {'H', 'e', 'l', 'l', 'o', '\0'};
printf("%s\n", name);  // Hello
```

매번 이렇게 쓰면 불편하니까, 문자열 리터럴로 간단하게 초기화할 수 있다. 이 경우 `\0`이 자동으로 붙는다.

```c
char name[6] = "Hello";  // 자동으로 끝에 '\0' 추가
```

`"Hello"`는 문자 5개지만 `\0`까지 포함하면 6바이트가 필요하다. 배열 크기를 5로 잡으면 `\0`이 들어갈 자리가 없어서 문자열 함수들이 **오작동** 한다. 배열 크기는 항상 **문자 수 + 1** 이상으로 잡아야 한다.

```c
char name[] = "Hello";  // 크기를 생략하면 자동으로 6 (5 + 널 문자)
```

문자 하나(`'A'`)와 문자열 하나(`"A"`)는 다르다. `'A'`는 `char` 타입으로 1바이트이고, `"A"`는 `'A'` + `'\0'`으로 구성된 2바이트짜리 `char` 배열이다.

문자열을 입력받을 때는 `scanf`에서 `%s`를 사용한다. 이때 배열 이름 자체가 주소이므로 `&`를 붙이지 않는다.

```c
char name[20];
printf("이름을 입력하세요: ");
scanf("%s", name);  // & 없이 배열 이름만
printf("안녕하세요, %s\n", name);
```

다만 `scanf`의 `%s`는 공백을 만나면 입력을 멈춘다. "Hong Gil Dong"을 입력하면 "Hong"만 저장된다. 공백을 포함한 문자열을 입력받으려면 `fgets`를 사용한다.

```c
char line[100];
fgets(line, sizeof(line), stdin);
```

문자열 관련 주요 함수들은 `<string.h>`에 들어있다. `strlen`은 문자열 길이를 반환하고, `strcpy`는 문자열을 복사하고, `strcmp`는 두 문자열을 비교한다. C에서는 `=` 연산자로 문자열을 대입하거나 `==`로 비교할 수 없으므로, 반드시 이 함수들을 사용해야 한다.

```c
#include <string.h>

char src[] = "Hello";
char dest[20];

strcpy(dest, src);              // 복사
printf("%lu\n", strlen(dest));  // 5 (널 문자 제외한 길이)

if (strcmp(src, dest) == 0) {
    printf("같은 문자열\n");
}
```

* * *

## 마무리

배열은 C언어에서 데이터를 묶어서 관리하는 가장 기본적인 방법이다. 핵심은 세 가지다 — 크기가 고정이라는 것, 인덱스가 0부터 시작한다는 것, 그리고 배열 이름이 첫 번째 요소의 주소라는 것. 특히 문자열이 `\0`으로 끝나는 `char` 배열이라는 점은 C 프로그래밍에서 끊임없이 등장하는 개념이니 확실히 이해해두는 것이 좋다.