바킹독 알고리즘 0x03강 배열 요약본

1. 배열의 정의 

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

C++ 에서의 배열은, 한 번 배열의 길이를 선언하면 배열의 길이를 바꾸지 못하지만, 자료구조로써의 배열에서는 배열의 길이를 마음대로 늘리거나 줄일 수 있다.

2. 배열 === 책꽂이라고 생각하자. 책꽂이에 특정 책이 어디에 있는지는 책을 움직이지 않고도 확인 가능하고, 그 책을 다른 책으로 갈아끼우는 것도 1번이면 된다. 또 책을 책꽂이 끝에 추가하는 것도, 그 책만 가져다가 꽂으면 된다 마지막 책 제거도 마찬가지. 그러나 중간에 책을 끼워야 한다면, 책을 하나씩 옮겨야 된다. 책의 위치가 변하는 것이 평균적으로  n/2 이므로 시간 복잡도는 O(n)이 된다. 

3. 배열 문제를 풀 때는 fill 함수를 사용 하는 것을 추천. 코드도 짧고 실수할 여지도 별로 없다. 

사용법:

fill(초기화 시키고 싶은 부분의 시작 주소, 초기화시키고 싶은 부분의 끝 주소, 초기화할 값);

//배열일 경우
fill(arr, arr + 5, 10);
//벡터일 경우
fill(v.begin(), v.end(), 10);

4. STL vector 

배열과 비슷한 자료구조로, 크기를 자유자재로 늘이거나 줄일 수 있음! 그래프의 인접 리스트 저장 시에는 벡터를 많이 쓰게 된다. 

STL vector 의 경우 이미 insert 와 erase 메소드가 구현되어 있고 이들의 시간 복잡도는 O(n) 이다. 반면 push_back 이나 pop_back 처럼 뒤에 요소를 추가하는 경우 O(1), push_front, pop_front 의 경우 O(n)이다. 시간 복잡도를 헷갈리지 않도록 주의하자.

또, Vector 에서 = 는 깊은 복사를 의미한다. 다시 말해 참조하는 것이 아니라, 그 자체를 복사하므로, 복사한 값을 바꿔도 원본은 그대로 유지된다.

마지막으로, Vector 의 모든 원소를 순회하고자 한다면, (js 의 for each 같다.) range-based for loop 를 사용하자. (단, c++11 이후로 지원함.) for(int e: v1) 을 이용하면, e 에 v1 의 요소가 차례대로 들어가게 된다. 

for(int e : v1) // int& e : v1 이라 하면 원본값이 e 에 들어간다. 
	cout << e << ' '; 
//range-based for loop 는 vector 말고도 list, map, set 등에서 모두 사용되는 개념이다.