[알고리즘/C++] 배열

출처 : BaaaaaaaarkingDog | '강좌/실전 알고리즘' 카테고리의 글 목록 (encrypted.gg)

- 배열이란 : 연속된 메모리 주소 상에 데이터를 할당하는 자료 구조
- 배열의 시간 복잡도
  - 데이터의 조회 및 수정 : O(1)
  - 맨 끝 원소의 추가/제거 : O(1)
  - 임의 원소의 추가/제거 : O(n) - 해당 위치부터 배열 끝까지 1개씩 데이터 위치를 조정해주어야 하므로

- 배열의 특징
  - 원소의 조회 및 확인에 O(1)의 시간 복잡도 요구
  - overhead는 낮고, cache hit는 높다
  - 주소가 연속 할당되어야 하므로 다른 구조 대비 할당에 제약이 다소 있는 편

- 배열 임의 위치에 추가 및 제거

#include <iostream>
using namespace std;

void insert(int idx, int data, int arr[], int &len){
	// idx : 추가할 위치
    // data : 추가할 데이터
    // arr[] : 원본 배열
    // len : 배열 길이, reference로 호출하였으므로 수정시 원본 값도 수정된다.
	
	for(int i=len;i > idx;i--){
    	arr[i] = arr[i - 1];
    }
    arr[idx] = data;
    len++;
}
void delete(int idx, int arr[], int &len){
	// insert에서 data만 빠진 상태
    // 제거할 위치 뒤의 모든 데이터를 1칸씩 앞으로 옮긴다.
    for(int i = idx ; i < --len ; i++){
    	arr[i] = arr[i+1];
    }
}

- 배열의 초기화
  1. for문 순회
  2. <algorithm> 헤더 - fill함수

int a[21];
int b[21][21];

fill(a, a + 21, 0); //시작위치, 끝위치, 채울 값

for(int i = 0 ; i < 21 ; i++)
	fill(b[i], b[i] + 21, 0); // 2차원 배열 초기화

- <vector> 헤더
  - 배열과 동일한 기능
  - 크기 조정이 자유로움

#include <iostream>
#include <vector>
using namespace std;

int main(void){
	vector<int> v1(3, 5);
    // vector 선언 : vector<자료형>
    // 초기값 선언 : 배열이름(길이, 초기값);
    
    int size = v1.size(); // 벡터 길이
    int begin = v1.begin(); // 벡터 맨 앞 위치
    v1.push_back(1); // 벡터 맨 뒤에 데이터 추가
    v1.insert(begin, 3); // 임의 위치에 데이터 추가
    v1.erase(begin); //임의 위치의 데이터 제거
    
    int pop = v1.pop_back(); // 맨 뒤 데이터 제거 및 반환
    v1.clear(); // 벡터 초기화
    
    // insert, erase 시 O(n) 시간복잡도
    // push/pop_back은 O(1) - 맨 뒤 데이터이므로
    // 벡터 간 대입 시 deep copy - 한쪽이 바뀌어도 다른쪽은 유지
    
    //벡터 순회 - C++11 기준
    for(int v : v1) cout << v << ' ';
    // v1의 원소가 순서대로 v에 복사되어 들어감
    // 만약 int &v로 설정시 원본값이 들어감
    
    //for문으로 벡터 순회
    for(int i = 0 ; i < v1.size() ; i++) cout << v1[i] << ' ';
}