Algorithm (배열)
(본 글은 https://www.youtube.com/watch?v=mBeyFsHqzHg&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=4 참조)
[ 특징 ]
임의의 위치에 있는 원소를 확인 / 변경 => O(1)
원소를 끝에 추가 => O(1)
마지막 원소를 제거 => O(1)
임의의 위치에 원소를 추가 / 제거 => O(N)
(나머지 원소들을 미루고 / 당겨야 하기 때문)
[ 팁 ]
- 배열을 특정 값으로 초기화 시킬 때 -> fill함수 이용(algorithm 헤더)
: 3가지 방법이 있으나 fill이 가장 실수 여지가 적고 편하다!1) 1차원 배열
int a[21]; fill(a,a+21,0);
2) 2차원 배열
int b[21][31]; for(int i=0; i<21;i++) fill(b[i],b[i]+31,0);
[ vector ]
[ 개념 ]
STL에서 제공하는 배열과 비슷한 자료구조
원소가 메모리에 연속해서 저장된다.
배열과 다르게 가변적
새로운 원소 추가 시 메모리 재 할당 후 이전원소 복사한다
(2^n개 단위로 메모리 할당)
[ 생성 ]
vector<int> v; // 비어있는 벡터 생성 vector<int> v(5); // 0으로 초기화된 5개의 원소를 가지는 벡터 vector<int> v(5,2) // 2로 초기화된 5개의 원소를 가지는벡터 vector<int> v2(v1) // v1을 복사한 벡터 v2
[ 내장함수 ]
: 원래는 'vector' 헤더파일을 추가해야 한다!
- insert()
- O(N) : 원소를 밀고 저장하기 때문
v.insert(v.begin(),1) // 인덱스 0에 1 삽입 v.insert(v.begin()+2, 3) // 인덱스 2에 3 삽입 v.insert(v.end(), 5) // v.end()는 마지막 다음 부분을 가리킴 // 즉, 마지막 요소 다음부분에 5 삽입 v.insert(v.end()-1, 5) // 마지막 요소자리에 5 삽입 /* 반환 값은 삽입한 위치의 iterator */ vector<int>::iterator it = v.insert(v.begin()+1,2); // it는 삽입한 위치인 인덱스 1을 가리킨다.
- erase()
- O(N) : 원소를 삭제하고 당기기 때문
/* 두번째 매개변수 위치 전까지 삭제! */ v.erase(v.begin()+2) // 인덱스 2 삭제 v.erase(v.begin(), v.begin()+3) // 인덱스 0~2 삭제 v.erase(v.begin(), v.end()) // 처음~끝 모두 삭제
- push_back
- O(1)
v.push_back(1); // 가장 뒤에 1 삽입
- pop.back
- O(1)
v.pop_back(); // 가장 마지막 원소 삭제
- size : vector의 아이템 개수 반환
- capacity : vector의 크기 반환
- vector의 크기는 요소 개수를 포함할 수 있는 최소의
2의 제곱수의 크기를 갖는다
ex) 3 item -> 4
5 item -> 8
9 item -> 16
[ iterator ]
- v.begin() : vector의 첫번째 위치를 가리키는 iterator
- v.end() : vector의 마지막 요소 다음 위치를 가리키는 iterator
[ vector 순회 ]
1) vector 크기 이용
for(int i=0; i < v.size(); i++) cout << v.at(i); // v[i]도 가능
2) iterator 이용
for(auto i=v.begin(); i != v.end(); i++) cout << *i ;
3) range-based for loop (C++11)
: c++ 11 이상을 지원해야 한다.for(int e : v) cout << e ; /* 내부에서 값을 바꿔야 할 때! */ for(int& e : v) // 참조자로 접근하면 원본이 바뀐다. cout << e ;
Author And Source
이 문제에 관하여(Algorithm (배열)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/Algorithm-배열저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)