JArchive 프로그래밍 일기

목차

0x00 배열의 정의와 성질 

0x01 기능과 구현 

0x02 STL vector 

0x03 연습문제 

0x00 배열의 정의와 성질 

정의

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

성질 

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

2. 추가적으로 소모되는 메모리의 양(overhead)이 거의 없음 

3. Cache hit rate가 높음 

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

참고) Cache hit rate 가 높다는 의미 

캐시 적중률이 높다 == 캐시를 참조했더니 데이터가 존재하는 확률이 높다.

캐시의 지역성에 기반하여 캐시에 존재하는 데이터의 주변 데이터도 곧 사용할 가능성이 높은 데이터다. 

배열은 메모리상에 연속한 구간에 존재하기 때문에 Cache hit rate가 높다. 

0x01 기능과 구현

조회, 수정 O(1)

인덱스로 바로 접근할 수 있으니까 O(1) 시간이 걸린다. 

맨 끝에 추가, 마지막 원소를 제거 O(1)

따로 배열을 변경할 필요 없기 때문에 O(1)이 걸린다. 

임의의 위치에 원소 추가 O(N)

평균적으로 N/2 개를 밀어야 하기 때문이다. 

책꽂이에 꽂힌 책들을 생각해보자. 중간에 책을 하나 꽂으려면, 나머지 책들을 옆으로 밀어야 한다. 

임의의 위치에 원소 제거 O(N)

이 경우도 원소를 하나 제거하고, 평균적으로  N/2 개를 밀어야 하니까 O(N)의 시간이 필요하다. 

insert 함수와 erase 함수를 직접 구현해보자

github 링크에 들어가서 코드를 받고 직접 삽입/삭제를 구현해보자. 

존재하지 않는 인덱스를 참조하지 않도록 주의해야 한다. 

배열 초기화 팁 

1. memset  실수할 여지가 많다. 0이나 -1아닌 다른 값을 넣으면 오동작한다. 

2. for  투박하지만 실수할 여지가 없어서 무난하다. 

3. algorithm헤더의 fill함수 사용을 권한다. 

실수할 여지도 별로 없고, 코드가 짧아서 가장 추천하는 방식이다. 

    int a[21];
    int b[21][21];
    
    // 1. memset
    memset(a, 0, sizeof a);
    memset(b, 0, sizeof b);
    
    // 2. for
    for(int i = 0; i < 21; i++)
        a[i] = 0;
    for(int i = 0; i < 21; i++)
        for(int j = 0; j < 21; j++)
            b[i][j] = 0;
        
    // 3. fill
    fill(a, a+21, 0);
    for(int i = 0; i< 21; i++)
        fill(b[i], b[i]+21, 0);

0x02 STL vector 

배열과 거의 동일한 기능의 STL 
배열과 달리 크기를 자유자재로 늘이고 줄일수 있는 장점이 있다. 

공식 레퍼런스 사이트에서 확인하며 메서드 정확하게 익히도록 연습하기.
iterator는 따로 공부하는 것을 추천함

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

int main(){
    vector<int> v1(3, 5);  // {5,5,5}
    cout << v1.size() << '\n';   // 3
    v1.push_back(7);   // {5,5,5,7}
    
    vector<int> v2(2);    // {0,0}
    v2.insert(v2.begin()+1, 3);   // {0,3,0}
    
    vector<int> v3 = {1,2,3,4};
    v3.erase(v3.begin() + 2);  // {1,2,4}
    
    vector<int> v4;  // {}
    v4 = v3;   // {1,2,4}
    cout << v4[0] << v4[1] << v4[2] << '\n';  // 1 2 4
    v4.pop_back(); // {1,2}
    v4.clear();    // {}
}

시간 복잡도 유념할 점

앞에서 넣고 빼는 popfront(), pushfront() 는 O(N)의 시간이 걸리는 것을 유의하자. 

insert(), erase()는 시간복잡도가 O(N)

뒤 쪽에 넣고 빼는 popback(), pushback()은 O(1)

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

vector 순회하는 방법

vector<int> v1 = {1,2,3,4,5,6};

// 1. range-based for loop (since C++11)
for(int e: v1)
	cout << e << ' ';
    
// 2. not bad
for(int i = 0; i< v1.size(); i++)
	cout << v1[i] << ' ';
    
// 3. 주의! 
for(int i = 0; i <= v1.size()-1; i++)
	cout << v1[i] << ' ';

1. range-based for loop 범위 기반 반복문 (C++11 부터 지원된 기능임을 유의)

2. v1.size()를 인덱스의 끝으로 보는 것 

3. v1.size()는 기본적으로 unsized int를 반환함! 조심해야 함. 

만약, v1이 빈 벡터일 때, 
v1.size() -1 이 unsigned int 0에서 int1 을 빼는 식이 된다. 
그리고 unsiged int 와 int를 연산하면 unsigned int 로 자동 형변환이 된다.

unsigned int 0 - (int) 1은 -1이 아니라, 4294967295 가 되어버린다!! 
unsigned int  overflow가 발생하여 런타임 에러가 난다. 

0x03 배열 연습문제

 배열 문제집을 풀어보자. 

BOJ 10808번 알파벳 갯수 

다음시간에는 연결리스트를 배우고 연습문제를 풀어본다. 

공부 내용 출처 : 바킹독 알고리즘 0x03 배열