[실전 알고리즘] 배열

지금까지 프로그래밍 언어의 관점에서 배열을 다뤘었기 때문에 자료구조로써의 배열을 익힐 필요가 있어 공부하였다.

 

1. 정의와 성질

배열의 정의

배열이란 메모리 상에 원소를 연속하게 배치한 자료구조를 말한다.

C++에서는 이미 선언된 배열의 길이를 변경하는게 불가능하지만, 자료구조로써의 배열에서는 길이를 마음대로 늘리거나 줄일 수 있다고 생각하겠다.

 

배열의 성질

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

- 시작 주소에서 k칸 만큼 오른쪽으로 가면 되기 때문

 

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

- 다른 자료구조와는 다르게 추가적으로 소모되는 메모리 양이 거의 없슴

 

3. Cache hit rate가 높음

- 메모리 상에 데이터들이 붙어있으니까 Cache hit rate가 높다.

 

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

- 메모리 상에 연속한 구간을 잡아야 하니 할당에서 다소 제약이 있다.

---

2. 기능과 구현

O(1)

- 임의의 위치에 있는 원소를 확인하고 변경하는 연산

- 원소를 끝에 추가하는 연산

- 마지막 원소를 제거하는 것

 

O(N)

- 임의의 위치에 원소를 추가하는 과정

   (위치가 끝에 가까울수록 시간은 줄어들고, 앞에 가까울수록 시간은 늘어나지만 평균 N/2이니 O(N)이라고 해도 상관없다.)

 

- 임의의 위치에 있는 원소를 제거

   (임의의 위치에 있는 원소를 제거하면 그 이후에 있던 모든 원소들을 한 칸씩 땡겨와야 한다.)

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

// 구현해보기
void insert(int idx, int num, int arr[], int& len){
	for(int i=len; i>idx; i--){
    	arr[i] = arr[i-1];
        // arr[i+1] = arr[i] 방식은 Out of Range 예외가 발생할 수 있기에 사용 X
    }
    arr[idx] = num;
    len++;
}

// 구현해보기
void erase(int idx, int arr[], int& len){
  	int i;
    for(i=idx+1; i<len; i++){
    	arr[i-1] = arr[i]
    }
    arr[i] = 0;
    len--;
}

void printArr(int arr[], int& len){
  for(int i = 0; i < len; i++) cout << arr[i] << ' ';
  cout << "\n\n";
}

void insert_test(){
  cout << "***** insert_test *****\n";
  int arr[10] = {10, 20, 30};
  int len = 3;
  insert(3, 40, arr, len); // 10 20 30 40
  printArr(arr, len);
  insert(1, 50, arr, len); // 10 50 20 30 40
  printArr(arr, len);
  insert(0, 15, arr, len); // 15 10 50 20 30 40
  printArr(arr, len);
}

void erase_test(){
  cout << "***** erase_test *****\n";
  int arr[10] = {10, 50, 40, 30, 70, 20};
  int len = 6;
  erase(4, arr, len); // 10 50 40 30 20
  printArr(arr, len);
  erase(1, arr, len); // 10 40 30 20
  printArr(arr, len);
  erase(3, arr, len); // 10 40 30
  printArr(arr, len);
}

int main(void) {
  insert_test();
  erase_test();
}

---

배열 전체를 특정 값으로 초기화시킬 때에는 세 가지 방식이 있다.

첫 번째로 제일 코드가 짧은 방법으로 cstring 헤더에 있는 memset 함수를 사용하는 방식이다.

하지만 이 함수는 실수할 여지가 굉장히 많기 때문에 비추천한다.

 

두 번째로는 그냥 for문을 돌면서 값을 하나하나 다 바꾸는 방식이고, 코드가 조금 투박하지만 실수할 여지가 없기에

무난하고 좋은 방법이다.

 

마지막으로 algorithm 헤더의 fill 함수를 이용하는 것이고, fill 함수는 실수할 여지도 별로 없고,

코드도 짧기에 가장 추천 드린다.

#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

int main(){
	vector<int> v(8);
    
    // 1번째 위치부터 4번째 위치까지 1로 할당
    fill(v.begin(), v.begin()+4, 1)
    
    return 0;
}

 

 

 

출처 - BarkingDog