바킹독의 실전 알고리즘 : 배열

23 Jan 2026 • Self-study

정의와 성질

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

  1. O(1)에 k번째 원소 확인 가능
  2. 오버헤드 거의 없음
  3. hit rate 높음 -> CS 확실히 중요하네..
  4. 연속된 자료구조이기 때문에 할당에 제약이 있다 -> 메모리상에도 연속적

기능과 구현

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

void insert(int idx, int num, int arr[], int& len){
  for(int i=len;i>idx;i--) // i가 길이부터 시작이니까 
    arr[i]=arr[i-1]; //i-1이 맞는 위치(?) 맞는 배열의 인덱스, 1번째 원소 인덱스 번호는 0
  arr[idx]=num; //그리고 넣어준다. 
  len++; //len도 하나 늘어난다. 
}

void erase(int idx, int arr[], int& len){
  len--; //길이를 먼저 한 번 지워야 
  for(int i=idx+1;i<len;i++) //여기서 줄인 idx에 맞는 
      arr[i-1]=arr[i];
}

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();
}

STL vector

배열과 거의 동일한 기능을 수행하는 자료구조이다. 배열과 마찬가지로 메모리에 연속적으로 원소를 저장하기 때문에 O(1)의 시간복잡도로 접근 가능하다. 배열은 고정 자료구조인 반면, vector는 동적으로 크기를 조절할 수 있다는 장점이 있다.

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

int main(void){
  vector<int> v1(3,5); // {5,5,5} 크기 3으로 초기화값 5인 벡터 생성 
  cout<<v1.size()<<'\n';
  v1.push_back(7); //꼬리에 7 삽입 push 
  
  vector<int> v2(5); //{0,0,0,0,0}
  v2.insert(v2.begin()+1,3); //{0,3,0,0,0,0}

  vector<int> v3 ={1,2,3,4};
  v3.erase(v3.begin()+2); //{1,2,4}

insert, erase는 O(n) push_back, pop_back은 순회가 필요 없으므로 O(1)

vector<int> v1={1,2,3,4,5,6}; //list, map, set 등에서도 모두 사용 가능 
 
for(int e:v1) //int& e:v1이라고 쓰면 for문 내에서 e를 바꿨을 때, 원본 v1도 같이 바뀜
  cout<<e<<' ';

for(int i=0;i<v1.size();i++)
  cout<<v1[i]<<' ';

for(int i=0;i<=v1.size()-1;i++)
  cout<<v1[i]<<' ';

마지막 3번째 예시는 32비트 컴퓨터 기준 런타임에러가 생길 수 있다. vector.size()는 unsigned int 혹은 unsigned long long을 반환한다. 빈 vector일 때 v1.size()-1이 unsigned int 0에서 int 1을 빼는 식이 되고, 이렇게 되면 unsigned int로 자동 형변환이 된다. 때문에 0-1=-1이 아니라 4294967295가 된다(unsigned int의 자료형 범위)

연습 문제

문제 2

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

int func2(int arr[],int N){
  for(int i=0;i<len(arr);i++){
    int occur[101]={};
    for(int i=0;i<N;i++){
      if(occur[100-arr[i]]==1)
        return 1;
      occur[arr[i]]=1;
    }
    return 0;
  }
}
 coding