[바킹독의 실전 알고리즘] 0x03강 - 배열

1. 배열의 정의 및 성질

배열이란?

메모리 상에 원소를 연속하게 배치한 자료구조

 

원래 C++에서는 배열을 선언한 이후 배열의 길이를 변경하는 게 불가능하다고 하지만, 자료구조에서 배열을 이해할 때는 배열의 길이는 유동적이라고 생각하자!

 

배열의 성질 - 코테에는 영향이 없지만 그래도 알아두자!

 

• O(1)에 k번째 원소를 확인/변경이 가능함
  • 배열은 메모리 상에 연속적으로 값을 저장하기 때문에 k번째 원소의 위치를 바로 계산할 수 있음. 따라서 시간복잡도는 O(1)

 

• 추가적으로 소모되는 메모리 양, 즉 오버헤드가 거의 없음
  • 오버헤드: 프로그램 실행 중 추가적으로 사용해야 하는 시간, 메모리, 자원을 의미

 

• Cache Hit Rate가 높음
  • 메모리 상에 데이터 값들이 서로 붙어있으니깐 hit rate이 높음
  • 컴구.. 나중에 개념 공부 다시 해야지.. 캐시 어려워!

 

• 메모리 상에 연속한 구간을 잡아야 하기에 할당에 제약이 있음

 

2. 기능과 구현

 

배열에서 구현하는 기능은 총 4가지

 

1) 임의의 위치에 있는 원소를 확인/변경

2) 새로운 원소를 끝에 추가

3) 마지막 원소를 제거

4) 임의의 위치에 원소를 추가 or 제거

 

1), 2), 3)의 경우 모두 시간복잡도가 O(1)이지만, 4)에서 새로운 원소를 기존 배열 중간에 넣으려면 그 자리 이후에 있던 원소들을 다 뒤로 밀어야 하는 과정이 필요하기 때문에 평균적으로 N/2개를 밀어야 함.(당연하게도 N은 배열의 총 길이임) 따라서 4)의 시간복잡도는 O(N)이 됨!

 

//배열에서 insert 함수와 erase 함수 구현해보기

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

void insert(int idx, int num, int arr[], int& len){
	for(int i = len; i > idx; i--) // >= idx 이면 idx가 0일때 런타임에러 발생
		arr[i] = arr[i-1];
	arr[idx] = num;
	len++;
}

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

 

배열의 초기화 방법

 

memset은 비추. 오동작할 가능성이 높음😑

for문을 돌면서 하나하나 초기화해주는 방식은 투박하지만 가장 확실한 방법!

algorithm 헤더의 fill 함수를 이용한다면 best! 실수할 여지도 없고 무엇보다 코드가 깔끔해서 추천함

 

📌 fill 함수

#include <algorithm> //꼭 추가시켜주기!

for(int i = 0; i < 5; i++) {
	arr[i] = 10;
}

fill(arr, arr + 5, 10); //위 코드랑 똑같은 기능을 함. 0번째부터 4번째까지
fill(초기화 시키고 싶은 부분의 시작 주소, 초기화시키고 싶은 부분의 끝 주소, 초기화할 값);

//벡터 배열일때
fill(v.begin(), v.end(), 10);

 

3. STL vector

vector는 배열과 거의 동일한 기능을 수행하는 자료구조로, 배열과 마찬가지로 원소가 메모리에 연속적으로 저장되어 있기에 각 원소로 접근하고자 한다면 시간복잡도는 O(1)이 됨.

다만 vector의 경우 배열과 다르게 크기를 자유자재로 늘이거나 줄일 수 있는 장점이 있음!

 

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}; 시간복잡도 O(N)

  vector<int> v3 = {1,2,3,4}; // {1,2,3,4}
  v3.erase(v3.begin()+2); // {1,2,4}; 시간복잡도 O(N)

  vector<int> v4; // {}
  v4 = v3; // {1,2,4} vector에서 '='을 사용할 경우 deep copy가 발생함.
  //이 후 v4를 바꿔도 v3에는 영향을 주지 X
  cout << v4[0] << v4[1] << v4[2] << '\n';
  v4.pop_back(); // {1,2} 
  v4.clear(); // {}
}

//push_back(), pop_back()은 제일 끝에 원소를 추가하거나 빼는 것으로 시간복잡도는 O(1)

*Deep copy(깊은 복사) vs Shallow copy(얕은 복사)

Deep copy는 실제 데이터 값을 메모리 영역으로 복사하는 것으로, 복사를 한 객체에서 값들을 아무리 수정해도 원본 객체의 값은 변하지 않는 게 특징임.

하지만 Shallow copy의 경우 객체의 참조값을 복사를 하는 것이기 때문에 복사한 객체에서 값을 수정하게 된다면 원본 객체의 데이터 값도 같이 수정되어 버리게 됨!

 

vector의 원소를 순회하는 방법

 

1) range-based for loop

*C++11부터 추가된 기능임에 주의하자! 

2) for문

vector<int> v1 = {1,2,3,4,5,6};

//1.range-based for loop
for(int e: v1) //e에 v1의 원소들이 하나씩 들어가는 for문. 참고로 int&e:v1으로 쓰면 원본 값이 e에 들어가 수정 시 실제 값 변경됨!
	cout << e << ' ';
    
//2.for문
for(int i=0; i<v1.size(); i++)
	cout << v1[i] << ' ';
    
//이거 하지 맙시다요 WRONG WRONG WRONG!
//vector의 size 메소드를 unsigned int/long long을 반환하는데, 만약 v1이 빈 벡터이면 "unsigned int(0) - 1 = 요상한 값"이 됨. 오버플로우 발생함!
for(int i=0; i <= v1.size()-1;i++) 
	cout << v1[i] << ' ';

 

📌vector에 대해 참고할만한 사이트

https://cplusplus.com/reference/vector/vector/