공부 일지/알고리즘

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

Roble 2023. 12. 20. 13:49

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헤더의&nbsp; 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을 해주게된다. 

 

 

 

 

 

 

 

 

저작자표시 (새창열림)