[자료구조] 배열(Array)

▶배열이 나타난 이유

---

옛날옛날... 선배님들은 변수를 이용해서 메모리에 값을 할당하고 CPU에게 계산을 시켰다.

하지만 문제가 생겼다.

메모리에 저장해야하는 값이 많아지면서 변수의 수도 많아지게 된것이다.

예를들어 이번 달 사용한 식비를 구하고싶으면 이번달 1일부터 마지막날까지의 식비를 다 더해줘야하므로 대충 30개의 변수가 필요하다.

 

선배님들은 어떻게 하면 변수를 많이 안쓰고 같은 종류의 데이터를 쉽고 효율적으로 메모리에 저장할 수 있을지를 고민했고, 그렇게 나오게 된 개념이 배열임.

내가 그림

 

▶배열의 정의와 성질

---

 

배열은 같은 종류의 데이터를 모아서 메모리에 순서대로 저장하는 기법이다.

배열은 요소(element)와 인덱스로 구성되어있다.

요소는 배열안에 담겨있는 하나하나의 요소를 말한다.

배열의 성질

1. k번째 원소를 O(1)에 확인하거나 변경가능
2. 추가적으로 소모되는 overhead가 거의 없음
3. 메모리상 데이터들이 불어있으니까 cache hit rate가 높음
4. 메모리 상에 연속한 구간을 잡아야해서 할당에 제약이 걸림.

+캐시적중률(Cache hit rate) 명령이나 자료를 찾기 위해 캐시 메모리에 접근했을 때 원하는 정보가 있을수도 있고 없을수도 있다. 만약 원하는 정보가 캐시 메모리에 있을 때 적중(Hit)되었다고 하고, 없다면 실패했다고 한다. 적중률 = 적중횟수/ 총 접근횟수 이고 컴퓨터의 성능을 나타내는 척도로 사용된다. (적중률이 0.95~0.99 일때 우수하다고 한다.)

 

임의의 원소를 확인하거나 변경 = O(1)

원소를 끝에 추가 = O(1)

마지막 원소를 제거 = O(1)

임의의 위치에 원소를 추가/제거 = O(N)

의 시간 복잡도를 가진다.

 

▶ 임의의 위치에 원소 추가/제거 구현

---

void insert(int idx, int num, int arr[], int& len);

void erase(int idx, int arr[], int& len);

int main(void){
	int arr[10]={10,50,40,30,70,20};
    int len = 6;
    insert(3,60,arr,len); //10 50 40 60 30 70 20
    erase(4,arr,len); // 10 50 40 60 70 20
}

insert함수와 erase함수를 구현해야 한다.

 

 

▷ insert 함수

---

• idx번째 위치에 num을 넣는 함수
• 원래 idx번째와 그 뒤에 있던 원소들은 자연스럽게 한칸씩 뒤로 이동함

void insert(int idx, int num, int arr[], int& len){
	for(int i=len; i > idx; i--)
    	arr[i] = arr[i-1];
    arr[idx] = num;
    len++;
}

 

코드를 확인해보면 오른쪽에서부터 자기 왼쪽의 값을 땡겨오는것을 알 수 있다.

if) 02번째 줄에 i≥idx로 작성했다면?

idx=0 일 때 arr[0]=arr[-1]이라는 명령이 수행되므로 런타임에러가 유발될 수 있음.

헷갈리는게 많지만 종이에 구상을 잘 해두고 구현하면 덜 꼬일거임.

 

▷ erase 함수

---

 

 

 

void erase(int idx, int arr[], int& len){
	len--;
    for(int i=idx; i<len; i++)
    	arr[i] = arr[i-1];
}

코드를 보면 insert함수와는 반대로 왼쪽부터 처리를 하는걸 볼 수 있다.

이러면 추가적으로 메모리를 쓰지 않고 구현 가능하다.

 

▶ STL vector

---

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	vector<int> v1(3, 5); //{5,5,5}
    cout << v1.size << '\n'; // 3
    v1.push_back(7); //{5,5,5,7}
    
    vector<int> v2(2); //{0,0}
    v2.insert(v2.begin()+1, 3); //{0,3,0}
    
    vector<int> v3 = {1,2,3,4}; //{1,2,3,4}
    v3.erase(v3.begin()+2); //{1,2,4}
    
    vector<int> v4; //{ }
    v4 = v3; //{1,2,4}
    cout << v4[0] << v4[1] << v4{2} << '\n'; //124
    v4.pop_back(); //{1,2}
    v4.clear(); //{ }
}

 

 

STL의 vector는 배열과 거의 동일한 기능을 하는 자료구조임.

배열과 마찬가지로 원소가 메모리에 연속하게 저장되어 있기 때문에

O(1)에, 인덱스를 이용해서 각 원소로 접근 가능하다.

vector는 배열과 달리 크기를 자유자재로 늘이거나 줄일 수 있다는 장점이 있음.

이후에 그래프의 인접리스트를 저장할 때 vector를 쓰는게 편함.

그 전까지는 굳이? 배열대신 vector를 써야하는 상황은 없음.

 

 

▶연습문제

---

BOJ 10808번: 알파벳 개수

 

 

▶  +전체를 특정 값으로 초기화 시킬 때 어떻게 하면 효율적일까?

---

 

int a[21];
int b[21][21];

//1. memset
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);

//2. for
for(int i = 0; i < 21; i++)
	a[i] = 0;
for(int i = 0; i < 21; i++)
	for(int j = 0; j < 21; j++)
    	b[i][j] = 0;
        
//3. fill
fill(a, a+21, 0);
for(int i = 0; i < 21; i++)
	fill(b[i], b[i]+21, 0);

1. memset 함수 활용
   • 제일 짧다.
   • memset함수는 실수할 여지가 굉장히 많다.
   • 그래서 비추한다.
2. for문으로 돌면서 하나씩 값 바꾸기
   • 코드가 좀 투박하다.
   • 그러나 실수할 여지가 없어서 무난하고 좋다.
3. algorithm 헤더의 fill 함수 이용
   • 코드도 잛고 실수할 여지도 별로 없음
   • 가장 추천함.

 

 

fill함수 구조는 C++ 포스팅 참고하시길 바랍니다!

https://learning-study.tistory.com/entry/Cfill-%ED%95%A8%EC%88%98%EC%97%90-%EB%8C%80%ED%95%B4-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90

[C++] fill 함수에 대해 알아보자