자료구조_배열[ C언어 ]

배열은 모든 언어에서 기본으로 제공되는 자료구조입니다.
배열은 동일한 타입의 데이터를 연속적으로 순서대로 나열시킵니다.

그럼 배열의 특징을 먼저 알아보겠습니다.

배열의 특징

1. 동일한 데이터 타입: 한가지의 데이터 타입만 사용할 수 있다.
2. 고정된 크기: 크기를 한번 정하면 변경하지 못한다.
3. 인덱스 접근: 배열에 값을 삽입하거나 가져올때는 인덱스로만 접근해야 한다.

그럼 배열을 한번 사용해 보겠습니다.

#include <stdio.h>

int main() {

	int int_array[5] = { };

	int_array[0] = 2;
	int_array[1] = 3;
	int_array[2] = 5;
	int_array[3] = 7;
	int_array[4] = 11;

	for (int i = 0; i < 5; i++) {
		printf("%d\n", int_array[i]);
	}

	return 0;
}

실행결과

2
3
5
7
11

배열을 생성할 때 int 형 데이터를 5 개 담을 수 있도록 선언을 함과 동시에 모든 인덱스의 값을 0 으로 초기화 시켰습니다.
그리고 0번 인덱스 부터 순서대로 2, 3, 5, 7, 11 을 인덱스를 지정해서 데이터를 담았습니다.

그리고 반복문을 사용해서 모든 0번 부터 4번 인덱스를 순서대로 값을 출력하였습니다.

이렇게 배열은 인덱스를 지정해서 값을 저장하고 읽을 수 있습니다.

---

데이터 (삽입, 삭제, 검색, 갱신)

데이터를 삽입 했으면 삽입한 데이터를 검색할줄 알아야 하고 삭제도 할 수 있어야 하죠 그리고 기존 데이터를 갱신(업데이트) 를 해야할 경우도 있겠죠 이 4가지 기능을 배열로 구현해 보겠습니다.

1. 삽입

위에서는 삽입을 할 때 인덱스를 직접 가르켜서 데이터를 넣었습니다.
하지만 이렇게 사용하면 문제가 발생할 수 있습니다.

{0, 0, 0, 0, 0} 이렇게 초기화 되어 있는 배열의 2번 인덱스에 3을 넣게되면
{0, 0, 3, 0, 0} 이렇게 들어가겠죠
그런데 이후에 5라는 데이터를 삽입해야 하는 경우 어느 인덱스가 비어있는지 모르고 2번 인덱스에 삽입을 하게되면
{0, 0, 5, 0, 0} 이렇게 삽입이 아닌 갱신을 하게 되버립니다.

이렇한 문제가 발생하지 않도록 하려면 인덱스의 순서대로 값을 넣어야 합니다.
그러면 자동으로 앞에서 부터 값을 넣을 수 있는 로직을 만들어 보겠습니다.

void clear(int* int_array, int size, int num) {// 초기화
    for (int i = 0; i < size; i++) {
        int_array[i] = num;
    }
}

int indexIntoCheck(int* int_array, int size) {//공간 확인
    for (int i = 0; i < size; i++) {
        if (int_array[i] == -1) {
            return i;
        }
    }
    return size;
}

void add(int* int_array, int size, int num) {// 삽입
    int setIndexPos = indexIntoCheck(int_array, size);
    if (setIndexPos != size) {
        int_array[setIndexPos] = num;
    }
    else {
        printf("배열에 공간이 없습니다.");
    }
}

---

#define arraySize 5


int main() {
    int int_array[arraySize] = { 0 };// 배열의 선언시 모든 요소를 0로 초기화

    clear(int_array, arraySize, -1);// 배열의 모든 요소를 -1로 초기화

    add(int_array, arraySize, 2);

    add(int_array, arraySize, 4);

    add(int_array, arraySize, 6);

    for (int i = 0; i < arraySize; i++) {
        printf("%d ", int_array[i]);
    }

    return 0;
}

실행결과

2 4 6 -1 -1

이렇게 하면 값을 빈 공간부터 차래대로 넣게 됩니다.
참고로 정수 배열은 빈 공간 자체가 없기 때문에 임의로 -1 을 빈 공간이라고 정의하였습니다.

1.1 삽입(중간 삽입)

데이터를 삽일할 때 특정 인덱스에 삽입하고 싶을때가 있습니다.
그러면 삽입할 인덱스의 뒷 부분은 1칸씩 뒤로 이동시키고 삽입을 해야 합니다.

...[추가코드]

void addIndex(int* int_array, int size, int num, int index) {//중간 삽입
    int arrayLen = indexIntoCheck(int_array, size);
    if (arrayLen != size) {// 공간이 있다면 실행
        for (int i = size - 1; i > index; i--) {
            int_array[i] = int_array[i - 1];
        }
        int_array[index] = num;
    }
    else {
        printf("배열에 공간이 없습니다.");
    }

}

 

---

 

#define arraySize 5


int main() {
    int int_array[arraySize] = { 0 };// 배열의 선언시 모든 요소를 0로 초기화

    clear(int_array, arraySize, -1);// 배열의 모든 요소를 -1로 초기화

    add(int_array, arraySize, 2);

    add(int_array, arraySize, 4);

    add(int_array, arraySize, 6);

    addIndex(int_array, arraySize, 10, 1);

    for (int i = 0; i < arraySize; i++) {
        printf("%d ", int_array[i]);
    }

    return 0;
}

실행결과

2 10 4 6 -1

1번 인덱스에 10 을 삽입하면 옆에 있던 4, 6 이 한칸씩 이동한것을 볼 수 있습니다.

2 삭제

마지막에 있는 요소를 삭제하게 되면 상관 없지만 중간에 있는 요소를 삭제하면 뒤에 있는 요소를 한간씩 당겨서 그 자리를 채워야 합니다.
이는 중간 삽입을 할 때의 반대로 동작하게 되는것입니다.

...[추가코드]

void deleteIndex(int* int_array, int size, int index) {
    int arrayLen = indexIntoCheck(int_array, size);
    for (int i = index; i < arrayLen - 1; i++) {
        int_array[i] = int_array[i + 1];
    }
    int_array[arrayLen - 1] = -1;
}

 

---

#define arraySize 5


int main() {
    int int_array[arraySize] = { 0 };// 배열의 선언시 모든 요소를 0로 초기화

    clear(int_array, arraySize, -1);// 배열의 모든 요소를 -1로 초기화

    add(int_array, arraySize, 2);

    add(int_array, arraySize, 4);

    add(int_array, arraySize, 6);

    addIndex(int_array, arraySize, 10, 1);

    deleteIndex(int_array, arraySize, 2);

    for (int i = 0; i < arraySize; i++) {
        printf("%d ", int_array[i]);
    }

    return 0;
}

2 10 6 -1 -1

이렇게 2번 인덱스에 있는 4 가 삭제되고 그 자리를 채우고 있습니다.

3 검색

검색은 특별한 로직이 필요하지 않습니다.
인덱스로 요소를 접근해서 찾기만 하면 되기 때문입니다.

4 갱신

갱신 또한신 또한 원하는 인덱스에 값만 넣으면 갱신되기 때문에 특별한 로직이 필요 없습니다.

정리

시간 복잡도

삽입	삭제	검색	갱신
O(n)	O(n)	O(1)	O(1)

이렇게 배열은 삽입과 삭제를 할 경우에는 배열 크기에 따라 시간이 오래걸리지만 검색과 생신은 인덱스로 바로 접근이 가능하기 때문에 배열이 아무리 크더라도 O(1) 으로 항상 빠르다는 장점이 있습니다.

즉 배열은 크기가 고정되어 있으면서 삽입, 삭제의 속도가 느리기 때문에 삽입, 삭제 작업이 별로 없고 검색이 많은 기능을 구현할 때 사용하는것이 좋습니다.

 

[추가]

 

동적할당

배열은 처음에 말씀드린대로 크기가 고정되어 있습니다. 하지만 동적할당을 사용하면 가변적으로 사용할 수가 있습니다.

 

간단하게 정적할당과 동적할당을 설명드리면

정적할당은 프로그램을 실행시키면 스택 메모리에 저장이 되면서 프로그램이 종료될 때 자동으로 소멸하게 됩니다.

동적할당은 프로그램이 실행되는 중간에 힙 메모리에 새로 할당을 할 수 있으며 메모리 사용이 끝나면 직접 해제를 해야 합니다.(프로그램이 종료되면 자동으로 해제됩니다.)

 

#include <stdio.h>
#include <stdlib.h>

#define arraySize 5

int main() {


    int* arr = (int*)malloc(arraySize * sizeof(int));

    if (arr == NULL) {
        printf("할당 공간이 부족합니다.\n");
        return 1;
    }
    else {
        printf("할당 되었습니다.\n");
    }

    // 값 입력
    for (int i = 0; i < arraySize; i++) {
        arr[i] = i;
    }

    // 값 출력
    for (int i = 0; i < arraySize; i++) {
        printf("%d, ", arr[i]);
    }
    printf("\n");

    // 확장
    int* temp = (int*)realloc(arr, arraySize * sizeof(int) * 2);

    if (temp == NULL) {
        printf("확장 공간이 부족합니다.\n");
        free(arr);
        return 1;
    }
    else {
        arr = temp;
        printf("확장 되었습니다.\n");
    }

    // 추가 값 입력
    for (int i = arraySize; i < (arraySize * 2); i++) {
        arr[i] = i;
    }

    // 전체 값 출력
    for (int i = 0; i < (arraySize * 2); i++) {
        printf("%d, ", arr[i]);
    }
    printf("\n");

    free(arr);
    return 0;
}

위 코드는 메모리를 처음에 동적으로 5사이즈 만큼 생성하고 추가로 *2 를 해서 10사이즈 의 배열을 동적으로 할당한 뒤 기존 배열에 넣는 방식을 사용합니다.