배열(vector)

바타칸·2023년 3월 16일
0

알고리즘 공부

목록 보기
4/4

복습을 겸해서 정리하는 모든 내용은 GOAT 바킹독에게서 시작됩니다. 감사합니다~

배열이란?

배열은 메모리 상에 원소를 연속하게 배치한 자료구조를 의미합니다.

배열의 성질

O(1)에 k번째 원소를 확인/변경 가능합니다.
메모리 상에 원소가 연속역으로 위치해 있기 때문에 k번째 원소는 k칸 오른쪽으로 가면 되므로 O(1)입니다.
추가적으로 알면 좋을 내용은 k번째 원소를 추가하거나 제거하는 것은 O(N)입니다.
추가할경우 해당 자리에서 오른쪽으로 원소들을 밀어야하므로 O(N-k)이고
제거할경우 해당 자리로 오른쪽 원소들을 당겨야하므로 O(N-k)이므로 O(N)입니다.

메모리 상에 연속한 구간을 잡아야하므로 할당에 제약이 걸립니다.
띄엄띄엄 배치할 수 있는 것이 아닌 한 번에 위치해야 하기 때문에 제한적일 수 밖에 없습니다.

Cache hit rate가 높습니다
저도 자세하게 아는 것은 아니지만 Cache에는 최근에 접근하거나 기억해야하는 자료가 들어가있고 우선적으로 Cache를 탐색하여 해당 자료가 있다면 메모리까지 가지 않고 Cache에서 바로 가져올 수 있어서 효율적입니다.
이 때, Cache에서 자료를 가져오는 것을 Cache Hit라고 하고 Cache hit rate가 높다는 뜻은 그만큼 빠른 작업이 가능하다는 뜻입니다.

Cache에 대해서 어려워하는 분들이 있을 것 같아서 예시를 하나 적어보겠습니다.

교수 : 여러분 123456789를 5432로 나눈 값이 몇일까요?
청중들은 계산기를 꺼냈고 누군가 답을 외쳤다.
교수가 똑같은 질문을 한 번 더 물어봤다.
청중들은 모두 바로 답을 외칠 수 있었다.

이해에 도움이 되셨을지 모르겠지만 이처럼 복잡하거나 시간이 오래 걸리는 작업을 한 번 수행한 이후에 동일한 결과 혹은 작업이 필요하다면 빠르고 쉽게 제공할 수 있게 만들어 주는게 Cache입니다.


vector

배열 얘기를 할 때 c++에서 빠질 수 없는게 있는데 바로 vector입니다.
장점으로 배열과 달리 미리 크기를 정해놓지 않아도 자유자재로 늘리고 줄일 수 있다는 것입니다.

#include <bits/stdc++.h>
using namespace std;

int main(void){
	vector<int> v1(4, 5); // {5,5,5,5}
    int s= v1.size(); //4
    v1.push_back(2);
    
    vector<int> v2(2); //{0,0}
    v2.insert(v2.begin() + 1, 2) // {0,2,0}
    
    vector<int> v3 = {1,2,3,4};
    v3.erase(v3.begin() + 2);
    
    vector<int> v4;
    v4 = v3;
    v4.pop_back();
    v4.clear();

}

STL vector의 사용 예시를 적어봤습니다.

코드를 보면 대부분 이해할 수 있으실거라고 생각하는데 개인적으로 중요하다고 생각하는 부분은 insert와 erease를 할 때 begin을 이용해서 주소로 접근한다는 점입니다.
저는 파이썬을 하다와서 그런지 얕게 공부해서 그런지 주소로 접근하고 계산하는게 매우 헷갈리고 어렵습니다.
그리고 v4 = v3에서 Deep copy가 발생합니다. v4를 바꿔도 v3에 영향을 주지 않는다는 뜻입니다.

그리고 특이한 점으로

for(auto c : s)

와 같은 표현이 가능한데 파이썬을 사용해보셨다면 꽤 자주 보셨을 것입니다.
이러한 표현이 가능하다는 점! 그리고 이걸 이용해서

string s;
for(auto c : s)

를 하면 문자열을 1개씩 c로 받을 수 있습니다. 저는 처음 보고 굉장히 유용할 것 같다고 생각했답니다.


이것으로 vector와 배열에 대한 간략한 정리를 마칩니다.
알고리즘을 하다가 깨닫거나 알게되는 점들은 업데이트를 하겠습니다!

profile
완전초보의 기록 겸 누군가에게 도움이 될 수 있는 날이 오기를

0개의 댓글