[Algorithm]C++ 배열

개요

알고리즘 문제를 풀 때 배열에서의 주의사항, 팁들을 알아보자.

 

기본 배열

주의사항

• 배열은 순차적으로 메모리가 할당되므로 원소를 찾는데 O(1)의 시간이 걸린다.
• 배열 끝에 할당을 하거나 삭제하는 건 O(1)의 시간이 걸린다.
• 배열 중간에 할당을 하거나 삭제하는 건 O(1)의 시간이 걸린다.

초기화 방법

1. memset: 0, -1이 아니면 오류가 나고 2차원 배열에서도 사용 불가능 비추!!
2. fill: 실수할 여지도 없고 사용도 간편

int arr1[10] = {}; //{0, 0 ...}
int arr2[10][10];


//1. memset
memset(arr1, 0, sizeof arr1);

//2. fill
fill(arr1, arr1+10, 0);

for(int i=0; i < 10; i++)
	fill(arr2[i], arr2[i] + 10, 0);

 

Vector

C++의 STL중 하나로 배열과 같은 특성을 지녔지만 가변적으로 길이를 조절할 수 있다는 점이 포인트.

기본 사용법

vector<int> v1(3, 5); // {5, 5, 5}
cout << v1.size() << '\n';
v1.push_back(7);

vector<int> v2(2); // {0, 0}
v2.insert(v2.begin()+1, 3); // {0, 3, 0}

vector<int> v4;
v4 = v2; //깊은 복사
v4.clear(); // {}

range-based for loop

• c++ 11부터 사용가능
• list, map, set 등에서도 사용가능
• 마지막 경우를 조심하자

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

for(int e: v1) //복사된 값이 e에 들어감
	cout << e << ' ';
    
 for(int& e: v1) 
 	e = 4; //{4, 4, 4, 4, 4, 4}
    
 for(int i=0; i<v1.size(); i++)
 	cout << v1[i] << ' ';
  
  //잘못된 방법: v1.size()는 unsigned int이기 때문에 0일때 문제!!
  for(int i=0; i<=v1.size()-1; i++)
 	cout << v1[i] << ' ';

 

Reference

c++ reference 사이트

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

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