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 ;