실전 알고리즘 0x03 배열

배열

[ 정의와 성질 ]

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

- O(1)에서 k번째 원소를 확인/변경 가능

- 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음

- Cache hit rate가 높음

- 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

 

[ 기능과 구현 ]

- O(1) = 위치 확인/변경, 끝에 추가/제거

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

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

- 배열을 초기화하는 방법

 

1. memset

- 오동작할 가능성이 커서 비추천한다.

 

2. for문으로 하나하나 바꾸기 

- 실수할 여지가 없기 때문에 무난하다.

 

3. fill 함수 (algorithm 헤더)

- 코드도 짧고 실수할 여지가 없어서 가장 추천한다.

fill(a, a+21, 0);
for(int i = 0; i < 21; i++)
	fill(b[i], b[i]+21, 0);

 

[ STL vector ]

- 배열과 달리 크기를 자유자재로 늘이거나 줄일 수 있다.

- 그래프의 인접 리스트를 저장할 때 vector를 쓰는것이 편하다.

- 사용법 : http://www.cplusplus.com/reference/vector/vector/

- STL의 iterator 따로 공부

- v.push_back(n) : 마지막에 n추가

- v.insert ( v.begin()+1, 3 ) : 1번 인덱스에 3 추가 ( 기존의 1번 인덱스는 2번 인덱스로 이동한다, O(N) ) 

- v.erase ( v.begin()+2) : 2번 인덱스의 숫자 제거 ( 이후의 인덱스는 1칸씩 앞으로 이동한다, O(N) )

- v.pop_back() : 맨 뒤 숫자 제거

- v.clear() : 모든 원소 제거

 

- vector에서 =를 사용하면 deep copy가 발생한다. ( 하나가 바뀌어도 다른 하나에 영향을 주지 않는다, 배열과 다름 )

 

- vector에 접근하는 방법

 

1. range-based for loop ( since C++11 )

for (int e : v1)
	cout << e << ' '; // v1의 원소가 e에 1개씩 들어간다

-  위의 코드에서는 e값이 바뀌어도 v1값은 바뀌지 않지만 int& e : v1을 이용하면 e값이 바뀌면 v1값도 바뀐다.

( list, map, set에서 모두 사용한다 )

 

2. not bad

for (int i = 0; i < v1.size(); i++ )
	cout << v1[i] << ' ';

3. WRONG

for (int i = 0; i <= v1.size()-1; i++ )
	cout << v1[i] << ' ';

- vector의 size메소드는 unsigned int 혹은 unsigned long long를 반환한다.

- 위 코드는 0-1 이 되면 unsigned int overflow가 발생한다. ( 런타임에러 발생 )

 

 

[ 연습문제 ]

- 배열은 데이터를 자주 바꾸지 않고 쌓아두고 싶을 때 활용한다.

- BOJ 10808번 https://www.acmicpc.net/problem/10808

- 아스키 코드 ( 'a'=97, 'z'=122 )