[ 자료구조 ] 2. 배열 C/C++

쵸오오오오오오오오잉 입니다

배열

대용량 자료의 처리

• 다수의 자료가 있을 경우 단순 변수로만 처리하기엔 어려움이 있음
• 이러한 한꺼번에 많은 자료가 필요할 경우 배열이나 구조체 혹은 데이터클래스(객체)를 사용

배열 (Array)

• 같은 종류의 데이터가 메모리 상에 연속적으로 저장된 데이터
• 연속적으로 값을 저장하기 때문에 원하는 위치(Index)의 값을 즉각적으로 접근 가능(시간복잡도 O(1))
• 배열에서 연속된 값을 보통 배열의 요소(Element)라고 부름
• 배열은 위치(Index)와 요소(Elment)의 집합
  

  

배열 선언

#include <iostream>

using namespace std;

int main(){
    int arr[4] = {1,2,3,4};
    for(int i=0; i<sizeof(arr)/sizeof(int); i++){
        cout<< arr[i] << endl;
    }
    return 0;
}

• 기본적인 배열 선언 및 출력코드
• 배열의 인덱스 번호는 0부터 시작
• sizeof 연산자를 통해 자료형의 크기 구함
  • 변수 arr 은 int 가 4개인 배열이니까 16 크기를 가짐

2차원 배열

• int [3][2]와 같은 형태의 2차원 배열 선언 가능
• 열과 행으로 원하는 인덱스에 접근가능 ex) arr [1][0]
• 형태는 2차원이지만 저장할 때 메모리 구조는 1차원 배열처럼 연속적으로 저장됨
  

  

배열은 첫 번째 요소를 가리키는 참조변수(포인터)이다

• 배열은 연속적인 메모리 구조를 가지기 때문에 첫 번째 요소의 참조변수와 사이즈만 알아도 모든 요소에 접근이 가능
• C/C++ 에선 포인터 연산을 통해 다음 요소에 접근 가능

#include <iostream>

using namespace std;

int main(){
    int arr[4] = {1,2,3,4};
    cout << "arr size:" <<  sizeof(arr) << endl;
    cout << "& arr size:" <<  sizeof(&arr) << endl;
    cout << "& arr :"  << &arr << endl;
    cout << "* arr :" << *arr << endl;
    cout << "*(arr+1) : " << *(arr+1) << endl;
    cout << "&(*(arr+1)) : " << &(*(arr+1)) << endl;
    return 0;
}

출력 결과

arr size:16
& arr size:8
& arr :0x16fbb6cd0
* arr :1
*(arr+1) : 2
&(*(arr+1)) : 0x16fbb6cd4

• &arr 은 배열의 첫 번째 요소를 가르키는 주소 값
  • 해당 값은 주소값 즉 포인트변수기 때문에 8바이트 (32비트 컴퓨터라면 4바이트라고 나옴)
• * 포인터를 통해 배열애서 원하는 위치의 요소에 접근 가능
• *arr 은 첫번째 요소, *(arr+1) 은 두 번째 요소에 값을 접근할 수 있음
• &(*(arr+1)) 을 접근할 시 두 번째 요소의 주소값을 가져오게 됨
  • 실제로 첫 번째 요소의 주소값은.. 6cd0이었는데 두 번째 요소는.. 6cd4로 배열의 타입만큼 연속적으로 이루어진 메모리 구조라는 것을 알 수 있음

배열에 삽입과 삭제 연산 구현해 보기

• 기본적으로 배열은 삽입 삭제 연산이 지원되지 않음
• 이를 구현하려면 직접 구현해야 됨
• 삽입 삭제 연산 모두 시간복잡도가 O(n)으로 삽입 삭제하려는 값을 업데이트하고 그 뒤의 값들은 하나하나 이동시켜야 됨

배열 선언

int arr[1000]={0,};
int length = sizeof(arr)/sizeof(arr[0]);
int cur = 0;

• 배열 초기화 및 현재 배열의 사이즈를 가리키는 cur 변수 선언

삽입 연산

void insert_array(int value, int index) {
    if (cur == 1000) {
        cout << "더이상 추가할 수 없습니다." << endl;
        return;
    }
    if (index < 0 || index > cur) {
        cout << "유효하지 않은 인덱스입니다." << endl;
        return;
    }
    for(int i = cur; i > index; i--) {
        arr[i] = arr[i - 1];
    }
    arr[index] = value;
    cur++;
}

1. 인덱스 유효성 검사
2. 배열의 현재 사이즈 cur에서 시작하여 삽입하려는 index 위치까지 반복문을 통해 한 칸식 뒤로 이동
3. 삽입하려는 위치 index에 value 값 대입
4. 값이 추가됐으므로 배열의 사이즈 추가 (cur++)

삭제 연산

void delete_array(int index) {
    if (cur == 0) {
        cout << "삭제할 수 없습니다." << endl;
        return;
    }
    if (index < 0 || index >= cur) {
        cout << "유효하지 않은 인덱스입니다." << endl;
        return;
    }
    for(int i = index; i < cur - 1; i++) {
        arr[i] = arr[i + 1];
    }
    cur--;
}

1. 인덱스 유효성 검사
2. 삭제하려는 위치 index에서 시작하여 배열의 현재사이즈 cur까지 반복문을 통해 한 칸씩 앞으로 당김
3. 값이 삭제됐으므로 배열의 사이즈 감소 (cur--)

전체코드

#include <iostream>

using namespace std;
int arr[1000]={0,};
int length = sizeof(arr)/sizeof(arr[0]);
int cur = 0;

void print_arr(){
    for(int i=0; i<cur; i++){
        cout << arr[i] << "\t";
    }
    cout << endl;
}
void insert_array(int value, int index) {
    if (cur == 1000) {
        cout << "더이상 추가할 수 없습니다." << endl;
        return;
    }
    if (index < 0 || index > cur) {
        cout << "유효하지 않은 인덱스입니다." << endl;
        return;
    }
    for(int i = cur; i > index; i--) {
        arr[i] = arr[i - 1];
    }
    arr[index] = value;
    cur++;
}

void delete_array(int index) {
    if (cur == 0) {
        cout << "삭제할 수 없습니다." << endl;
        return;
    }
    if (index < 0 || index >= cur) {
        cout << "유효하지 않은 인덱스입니다." << endl;
        return;
    }
    for(int i = index; i < cur - 1; i++) {
        arr[i] = arr[i + 1];
    }
    cur--;
}
int main(){
    insert_array(1,0);
    insert_array(2,0);
    insert_array(3,0);
    insert_array(10,2);
    insert_array(999,cur);
    delete_array(0);
    delete_array(cur);
    print_arr();
    return 0;
}

• 이러한 방식은 실제 ArrayList와 유사하게 동작함
• 현재 배열의 크기가 꽉 찰경우 더 이상 추가를 못하지만 배열의 크기를 늘리고 기존값을 복사하는 방식으로 구현 가능
• 삭제나 삽입 연산 시 해당 위치 이후의 모든 원소들을 이동시켜야 하므로 시간복잡도 O(n)
• 배열은 연속적인 메모리 주소로 할당되기 때문에 원하는 위치에 바로 접근 가능해서 시간복잡도 O(1)