동적 배열 ( dynamic array )

개요

---

간단한 정렬 문제를 생각해보자.

먼저 자연수N을 입력받는다. (1<=N<=1,000,000)

그 다음, N개의 정수를 입력받는다.

입력받은 N개의 정수를 오름차순으로 출력하시오.

배열을 활용해 문제를 해결하면 아래와 같이 된다.

//code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
 
using namespace::std;
 
int a[1000000];
 
int main(void){
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
        scanf("%d",&a[i]);
    sort(a,a+n);
    for(int i=0; i<n; i++)
        printf("%d\n",a[i]);
    return 0;
}

위와 같이 배열을 선언할 경우, 원소의 개수를 프로그램 실행 이전에 정해주게 된다.

따라서 입력에서 N으로 5가 들어오든, 1000000이 들어오든 똑같이 1000000개의 변수를 선언하는 꼴이 된다.

만약 N으로 5가 들어온다면 999995개의 int형 메모리는 낭비가 되는 것이다.

이럴 때 선형 자료구조 중 하나인 동적 배열을 활용하면, 이러한 메모리 낭비를 줄일 수 있다.

동적 배열의 크기는 저장하는 자료의 개수의 변화에 따라 변한다.

//code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#include<vector>
 
using namespace::std;
 
vector<int> a;
 
int main(void){
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        int in;
        scanf("%d",&in);
        a.push_back(in);
    }
    sort(a.begin(),a.end());
    for(int i=0; i<n; i++)
        printf("%d\n",a[i]);
    return 0;
}

C++ STL vector

---

C++ STL 에 있는 vector 를 활용하면 동적 배열을 사용할 수 있다.

//code by RiKang, weeklyps.com
#include<vector>
using namespace::std;
vector<변수형> 이름;

위처럼 전처리문을 넣어준 후, 'vector<변수형> 이름' 을 사용하면 해당 변수형을 저장하는 동적 배열이 생성된다.

vector<구조체> 를 선언하는 것도 가능하다.

배열과 같이, 벡터이름[숫자] 의 형식으로 사용할 수 있다.

1. push_back()

벡터에 새로운 자료를 넣는 연산이다. 이름에서 알 수 있듯이 자료를 넣는 위치는 맨 뒤이다.

예를 들어 a[0], a[1] 이 채워져 있는 상태에서 a.push_back(1) 이 이루어 진다면

a[2] = 1 이 된다.

//code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#include<vector>
 
using namespace::std;
 
vector<int> a;
 
int main(void){
    a.push_back(3); //a={3}
    a.push_back(2); //a={3,2}
    a.push_back(1); //a={3,2,1}
    return 0;
}

위와 같은 프로그램을 실행하면 a 에는 3,2,1 이 순서대로 저장된다.

따라서, a[0] = 3, a[1] = 2, a[2] = 1 이 된다.

2. size()

size() 는 현재 벡터에 저장되어 있는 자료의 개수를 unsigned int 형으로 반환해주는 함수이다.

따라서 size() 를 활용하면 아래와 같이 벡터에 있는 값들을 순서대로 사용할 수 있다.

//code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#include<vector>
 
using namespace::std;
 
vector<int> a;
 
int main(void){
    a.push_back(3);
    a.push_back(2);
    a.push_back(1);
    for(int i=0; i<a.size(); i++)
        printf("%d\n",a[i]);
    return 0;
}

위에서 a.size() 는 3을 반환한다.

3. pop_back()

맨 뒤에 있는 자료를 버리는 함수이다. 자연스럽게 size도 하나 줄어든다.

//code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#include<vector>
 
using namespace::std;
 
vector<int> a;
 
int main(void){
    a.push_back(3);
    a.push_back(2);
    a.pop_back(); // 맨 뒤에 있는 자료인 2를 버린다.
    a.push_back(1);
    for(int i=0; i<a.size(); i++)
        printf("%d\n",a[i]);
    return 0;
}

4. back()

맨 뒤에 있는 자료를 반환하는 함수이다.

//code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#include<vector>
 
using namespace::std;
 
vector<int> a;
 
int main(void){
    a.push_back(3);
    printf("%d\n",a.back()); // 3
    a.push_back(2);
    printf("%d\n",a.back()); // 2
    a.pop_back();
    printf("%d\n",a.back()); // 3
    a.push_back(1);
    printf("%d\n",a.back()); // 1
    return 0;
}

5. resize()

백터의 원소의 개수를 재조정하는 함수이다.

//code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int main() {
    vector<int> a;
    // 여기에서 a[3] 을 사용하면 에러가 난다. 아직 a[3] 이란 원소가 없기 때문.
    // printf("%d",a[3]);
    a.resize(5);
    for(int i=0; i<5; i++){
        a[i] = i*i;
        printf("%d\n",a[i]);
    }
    return 0;
}

push_back()의 시간복잡도

---

동적 배열은 일반 배열을 이용하여 구현한다.

그리고 동적 배열은 일반 배열과 같이 원소의 삽입, 변경, 접근을 평균 O(1) 에 할 수 있다.

접근이야 어차피 일반 배열과 동일한 방식 ( 이름[숫자] ) 이고,

변경도 이름[숫자] = 넣을 변수 을 하면 끝이기 때문에 O(1) 이라는 것이 놀라울 것 없다.

하지만 삽입의 경우엔 다르다.

아래와 같이 vector<int> a 와 int b가 메모리에 할당되어 있는 상태를 생각해 보자.

이 상태에서 a.push_back(5) 라는 함수가 실행되면 int b 때문에 5를 넣을 장소가 없다.

이렇게 더 이상 삽입을 할 수 없는 경우, 원래 있던 원소들도 메모리의 다른 곳으로 옮겨야 한다.

이렇게 메모리를 재할당 할 경우, 기존의 원소들을 다 옮겨야 하기 때문에  O(n) 이 필요하다.

따라서 최악의 경우, push_back() 을 할 때마다 재할당을 한다면 삽입의 시간복잡도는 O(n)이 될 것이다.

하지만 그렇다고 해서 무턱대고 처음부터 메모리를 크게 할당하면 동적 배열을 사용하는 이유가 반감된다.

이를 해결하기 위해 동적 배열에서 사용하는 전략의 예시는 재할당을 할 시, 기존의 크기의 2배로 할당하는 것이다.

위와 같이 4개의 자리가 부족해 재할당 한다면, 8개의 자리가 비어있는 곳을 찾아 할당한다.

그 다음 8개의 자리가 부족해 재할당 한다면, 16개의 자리가 비어있는 곳을 찾아 할당한다.

이런 전략의 시간복잡도 계산을 위해, 비어있던 vector에 N 번의 push_back() 이 이루어졌다고 해보자.

그러면 최악의 경우, 재할당에는  2*N + N + N/2 + N/4 + N/8 + ... + 1 이하의 연산이 필요하다.

(예시로, N=9 일 경우엔, 1 - > 2 - > 4 - > 8 - > 16 의 크기로 재할당 된다.)

그런데 1/2+1/4+1/8+... = 1 이기 때문에  2*N + N + N/2 + N/4 + N/8 + ... + 1 <= 4*N 이 된다.

따라서 N개의 push_back() 에 필요한 시간복잡도는 O(N) 이 되고, push_back() 한 번의 평균 시간 복잡도는 O(1)이 된다.

vector의 초기화

---

vector는 아래와 같이 다양한 방법으로 초기화할 수 있다.

//code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int main() {
    vector<int> a(5); // 원소의 개수를 5개로 초기화, a[0] ~ a[4] 를 쓸 수 있다.
    vector<int> b(5, 0); // 원소의 개수를 5개로 초기화 + 각 원소의 값을 0으로 초기화
    vector<int> c(5, 3); // 원소의 개수를 5개로 초기화 + 각 원소의 값을 3으로 초기화
    vector<int> d={1,2,3,4,5}; // 구 버전에선 작동하지 않는다. c++11 부터는 작동
    int arr[]={4,2,3,1};
    vector<int> e(arr,arr+4);  // e[0]=arr[0], e[1]=arr[1], ..., e[3]=arr[3]으로 초기화
    return 0;
}

초기화를 통해 미리 벡터의 크기를 늘려 놓고 사용할 경우,

메모리 재할당이 줄어들기 때문에 실행 속도가 빨라지는 경우가 있다.