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

0x00 정의와 성질

정의

 

성질

1. O(1)에 k번째 원소를 확인/변경 가능
2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음
3. Cache hit rate가 높음
4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

 

 

 

 

 

0x01 기능과 구현

어떤 배열에서

 

 

구현 - insert 함수

임의의 위치에 원소를 추가할 때(5번에 15를 넣는 상황)는 맨 오른쪽에서부터 하나씩 옮기는 방식을 써야했다

 

 

insert함수를 구현해 보면

void insert(int idx, int num, int arr[], int& len){
  for(int i = len; i > idx; i--)	//for문으로 순차적으로 값들을 오른쪽으로 이동시킴
    arr[i] = arr[i-1];
  arr[idx] = num;					//새롭게 추가할 값을 넣기
  len++;						//용량이 부족하니 추가
}

 

 

 

구현 - erase 함수

3번을 지우고 싶다!

임의의 위치에 원소를 지울때는 왼쪽부터 값들을 땡겨오면 될듯하다

 

erase함수를 구현해 보면

void erase(int idx, int arr[], int& len){
  len --;			//총 용량 줄이기
  for(int i=idx; i < len; i++)	//원소들을 한 칸씩 땡겨오기
    arr[i] = arr[i+1];
}

 

 

 

전체를 특정 값으로 초기화 시킬때 어떤 방법이 제일 효율적인가

1번은 정말 비추천(단점이 많음), 2번 (안전빵), 3번 algorithm헤더의  fill 함수를 이용하는 것이 가장 추천된다.

 

 

 

 

 

 

 

 

0x02 STL vector

vector는 배열과 거의 동일한 기능을 수행하는 자료구조로, 배열과 마찬가지로 원소가 메모리에 연속하게 저장되어 있기 때문에 O(1)에 인덱스를 가지고 각 원소로 접근할 수 있다. 그런데 vector는 배열과 달리 크기를 자유자재로 늘이거나 줄일 수 있다는 장점이 있다.

 

vector 사용 예시

 

.size()        :     vector의 크기

.begin()           :         맨 앞 인덱스

.push_back(n)         :        맨 끝에 n 원소 추가

.pop_back()             :        맨 끝 원소 삭제

.clear()                     :        전체 원소 삭제

 

 

 

 

vector에 있는 모든 원소를 순화하려고 할 때 방법 [ range-based for loop ]

 

04, 05번째 줄 처럼 int e : v1 이라고 하면 e에 v1의 원소들이 하나씩 들어가는 for문이 된다.

지금은 값을 바꾸지 않고 그냥 출력만 해서 별 상관이 없지만, 만약 int e : v1이라고 하면 복사된 값이 e에 들어가고 int& e : v1이라고 하면 원본이 e에 들어간다. 그렇기 때문에 int e : v1라고 쓴 for문 내에서 e를 바꿔도 v1에는 영향이 가지 않지만, int& e : v1이라고 쓴 for문 내에서는 e를 바꾸면 원본인 v1에서 실제 해당 원소의 값이 바뀌게 된다.

이 기능은 vector 뿐만 아니라 나중에 배울 list, map, set 등에서도 모두 사용할 수 있기 때문에 기억해두시면 좋은데 다만 이 기능은 C++11부터 추가된 기능이다. 만약 코딩테스트가 C++11을 지원하지 않는다고 하면 사용할 수 없다.

 

 

 

 

 

 

 

 

0x03 연습문제

BOJ 10808번:알파벳 개수

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

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> s;
    for(char a = 'a'; a <= 'z'; a++){
        int cnt = 0;
        for( auto c : s)
            if(a==c) cnt++;
        cout << cnt << ' ';
    }
}

 

 

 

 

0x01강의 연습문제

 

 

시간복잡도를 O(N) 으로 하기 위해 arr[] 말고도 for문안에 사용할(arr이 0이상 100이하라는 조건을 보고) 새로운 배열 occur을 크기 101로 만들어준다.

 

0으로 채워져있는 occur 배열을 길이 N만큼 반복해서 인덱스마다 값을 비교할것이다. 결국 arr[i]가 100이 되기 위해 필요한 수가 occur 인덱스가 되고 occur의 arr[i] 인덱스는 1로 바뀌어 가며 나중에 100이 되기 위해 필요한 수의 인덱스가 1인 경우 return 1을 해주게된다.