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

- 배열의 정의 -

배열을 선언한 뒤에 배열의 길이를 변경하는 게 불가능하지만, 자료구조로써의 배열에서는 길이를 마음대로 늘리거나 줄일 수 있다고 가정하자.

 

- 배열의 성질 -

1) 배열은 메모리 상에 원소를 연속하게 배치한 자료구조이기 때문에 k번째 원소의 위치를 바로 계산할 수 있다.

    k번만큼 이동하면 되기 때문에 시간복잡도 O(1)

2) 다른 자료구조들과 다르게 추가적으로 소모되는 메모리 양이 거의 없다.

3) 메모리 상에 데이터들이 붙어있기 때문에 Cache hit rate가 높다.

4) 메모리 상에 연속한 구간을 잡아야 하기 때문에 할당에 제약이 걸린다.

 

- 배열의 기능(시간복잡도) -

 

-배열을 특정 값으로 초기화시키는 방법-

1) cstring의 memset 함수는 memset(포인터(배열의 시작 주소), 초기화할 값, 초기화할 크기)로 사용할 수 있다.

하지만 0, -1이 아닌 다른 값으로 세팅하려고 하면 원하는 대로 작동하지 않는 문제가 있고, 또 2차원 이상의 배열을 넣을 때도 까다롭기 때문에 비추천!

 

2) for 반복문을 돌면서 값을 바꾸는 방식

 

3) argorithm 헤더의 fill 함수를 사용

fill(first, last, val)로 사용할 수 있고 [first, last) 범위에 val 값이 채워지게 된다. 실수할 여지가 적고 코드가 간단해서 추천!

 

- STL vector -

vector는 배열과 거의 동일한 기능을 수행하는 자료구조

배열과 마찬가지로 원소가 메모리에 연속하게 저장되어 있기 때문에 O(1)의 시간복잡도로 각 원소를 접근할 수 있다.

그런데 vector는 배열과 달리 크기를 자유자재로 조절할 수 있다는 장점이 있다.

임의의 위치에 원소를 추가하거나 제거하는 v.insert() v.erase()는 배열과 마찬가지로 시간복잡도 O(n)

가장 끝에 원소를 추가하거나 제거하는 v.push_back(),  v.pop_back()은 시간복잡도 O(1)이지만

가장 앞에 원소를 추가하거나 제거하는 v.push_front(), v.pop_front()는 O(n)이라는 것을 유의하자!

 

또 vector에서 =를 사용하면 deep copy가 발생한다.

16번째 줄에서 v4 = {1, 2, 4}가 되었고 이후 v4를 바꿔도 v3에는 영향을 주지 않는다.

 

vector에 있는 모든 원소를 순회하려고 할 때 range-based for loop 사용 가능

for(int e : v1)이면 e에 v1의 원소가 하나씩 복사되어 들어가는 for문이 된다.

for(int& e : v1)라고 작성하면 원본이 e에 들어가기 때문에 원본인 v1에 영향을 주는 데, 이 기능은 나중에 배울 list, map, set에서도 사용될 수 있으니 꼭 기억해두자!(다만 이 기능은 C++11부터 지원됨)

 

2번 방식처럼 기본적인 for문으로 원소를 순회할 수 있지만, 3번은 잘못된 방식이다.

기본적으로 vector의 size는 보통 unsigned int를 반환한다.

그렇기 때문에 3번같이 쓰면 v1이 빈 벡터일 때 v1.size - 1이 unsigned int 0에서 int 1을 빼는 식이 되고 이는 unsigned int로 자동 형변환 되기 때문에 -1이 아니라 4294967295라는 이상한 값이 들어가게 된다.(unsigned int overflow, 런타임 에러 발생)

 

 

🐶 바킹독의 실전 알고리즘 강의를 듣고 정리한 내용을 기록한 글입니다