6. 자료구조 - 배열의 크기 조정하기

● arrays

 

우리는 배열에 대해 배웠었다. 아마 이것이 우리가 배운 첫 번째 자료구조일 것이다. 

배열로 인해 int를 2개 3개 혹은 100개 까지도 한번에 저장할 수 있었다.

많은 데이터를 캡슐화할 수 있었던 것이다.

 

그러나 배열은 생각한 것만큼 강력하진 않다.

 

예를 들어 크기가 3인 배열을 만들고

그 안에 3개의 값을 저장했는데,

4번째 값도 저장하려고 하는 상황을 가정해보자. 처음에는 이런 상황을 예상하지 못했던 것이다. 앞서 우린 배열의 크기는 미리 지정해야 한다고 배웠었다. 따라서, 3이나 3이 포함된 변수를 하드코딩해야 했다. 하지만, 4번째 값을 저장하려고 할 때 아마도 새로운 메모리 박스를 하나 더 가져와서 3옆에 두고 모든 숫자들을 한번에 저장하면 된다고 생각할 수도 있다.

 

하지만 안타깝게도 전에 배웠던 내용으로는 좋은 생각이 아니다. 

왜냐하면 컴퓨터의 나머지 메모리 관점에서는 1, 2, 3이 다른 byte에 둘러싸여 있기 때문이다. 프로그램의 다른 부분에서 쓰이는 데이터들로 둘러싸여 있는 것이다. 따라서 1, 2, 3 다음에 4를 넣을 공간이 바로 없고 그렇기에 기존 배열에 4번째 숫자를 넣을 수 없다고 생각할 수 있다.

 

그렇다면 다른 방법은 없을까??

 

다른 메모리로 이동시키는 방법이 있을 것이다. 위 그림을 보면 하단에 빈 공간이 보이는 곳으로 옮긴다고 생각할 수 있다.

그렇기 때문에 배열을 사용하더라도 메모리 안의 값을 새로운 메모리로 움직이게 되면 혹은 복사해오게 되면 새로운 값을 새로운 값을 추가할 수 있게 될 것이다.

 

이 과정은 일종의 눈속임이다. 기존 배열을 늘릴 수 없으니 새로운 배열로 이동하여 기존 배열의 크기를 늘린 것처럼 생각하게 된다. 따라서, 기존 배열을 하나하나 복사하는 것이다.

1, 2, 3을 새로운 배열로 옮긴다.

이렇게 하면 이전에 사용된 메모리를 버리거나, free를 실행하면 된다.

그리고 4를 추가한다. 

하지만, 이것이 꼭 최선의 방법은 아닐 것이다. 앞서 말한 방법을 사용하면 꽤 많은 단계를 거칠 것이다.

 

이 알고리즘이 얼마나 효율성을 지니는지 판단하기 위해 어떤 연산이나 얼마만큼의 실행시간이 추가적으로 숫자를 넣어주는데 필요한지 알아보자.

숫자를 insert 하는데에는 O(n) 일 것이다. 그 이유는 n 개가 있다고 하면 n 번의 과정을 통해 값들을 새로운 배열로 옮겨야 하기 때문이다. 엄밀히 따지면 3개가 있다고 할 때 왔다갔다하는 것을 고려하면 총 6번의 과정이 발생하지만(2n) 그냥 O(n) 이라고 생각하면 된다. 즉, 이미 만들어진 배열에 실제로 추가하는데는 O(n) 만큼의 실행시간이 걸린다.

 

정렬된 것을 탐색할 때는 O(lon n)이 걸린 것을 알 수 있다. 이것이 데이터를 정렬된 배열로 저장할 때의 장점이었다. 이진 탐색을 이용할 수 있기 때문이다. 하지만 움직이는 방법은 시간이 많이들고 이상적인 접근법은 아니다.

 

이를 코드로 살펴보자.

위 코드를 살펴보면

int list[3]; : 임의로 정수 3개를 만들기 위해 list 라는 정수형 배열을 만들고 크기를 3으로 한 것이다. 

 

list[0]; list[1]; list[2]; : 이 list 를 초기화하기 위해 인덱스마다 하드코딩 해준 것이다.

 

그 다음 for 문을 통해서 3개의 값을 관찰하기 위해 list를 출력한 것이다. 

배열 파트를 배웠을 때 구현한 것과 같은 것이다. 이 프로그램을 컴파일 한 뒤 실행하면 1, 2, 3이 출력된다.

 

이 코드에는 근본적인 문제가 있다. 직접 배열의 크기를 타이핑해서 하드코딩했기 때문에 4번째 숫자를 어떻게 넣을 수 있을까??

뭐 간단하게 list 배열의 크기를 4로 바꾸고 새로운 인덱스에 값을 넣어준 뒤 for 문의 조건식을 바꾸면 새롭게 compile 해야 할 것이다. 이는 동적이지 못하다. 그렇다면 어떻게 해야할까??

 

우리는 메모리를 동적으로 배정할 수 있는 함수를 배웠다. malloc 함수이다. malloc을 이용하면 정해진 숫자를 코드에 타이핑할 필요가 없다. 일정량의 메모리를 동적으로 할당할 수 있게 된다. 앞선 코드를 효과적으로 바꿔보자.

1. int *list = malloc(3 * sizeof(int)); if ( list == NULL ) { return 1; }

 

malloc 을 이용해 메로리를 할당받으면 그 메모리 덩어리의 주소를 반환해준다. 따라서, list라는 int에 대한 포인터를 선언할 수 있게 된다. 그리고 3 * sizeof(int) 를 통해 3개의 정수에 맞는 메모리를 받게된다. 따라서 list는 포인터 변수이고 메모리 덩어리에 해당하는 주소를 갖게 된다.

 

그리고 malloc을 사용할 때는 에러 검사를 해줘야한다. malloc은 메모리를 가끔 모두 쓸 수도 있기 때문이다. PC나 클라우드 계정에 메모리가 부족하다면 반환값을 보고 난 다음 가장 좋은 방법은 list == NULL 이면 1을 반환하는 것이다. 즉, 메모리를 할당할 때 마다 NULL이 반환되었는지 확인해보는 것이다.

 

2. list[0]; list[1]; list[2];

 

C 의 장점은 여기서 list가 메모리 덩어리라는 사실을 알게 되면 [] 를 그대로 사용할 수 있게 된다는 점이다.

따라서 인덱스를 지정한 부분은 바꾸지 않아도 된다. 

포인터 이름 옆에 []를 사용하면 컴퓨터는 자동으로 그 메모리 덩어리의 첫번째 바이트로 이동한다.

즉, list[0] 은 덩어리 중 제일 첫번째 덩어리의 첫 바이트로 가고,

list[1] 은 그 다음 덩어리의 첫번째 바이트로 가게된다.

list[2] 는 그 다음 덩어리의 첫번째 바이트로 가게된다.

이 3개 모두 malloc이 반환했던 범위 안에 있다.

 

정수는 4byte가 필요하고 포인터 연산이기 때문에 [0] 은 메모리 상에서 0번 byte가 오고,

[1] 은 1번 byte 가 나오는 것이 아닌 4byte 뒤의 4번 byte가 나온다.

[2] 는 2번 byte 가 나오는 것이 아닌 8byte 뒤의 8번 byte가 나오게 된다.

왜냐하면 4 + 4 + 4 총 12byte 를 할당받았기 때문이다.

그리고, [] 는 각 인덱스 마다 정확한 메모리 덩어리로 가서 정수 3개를 알맞게 넣을 수 있게 해준다. 

 

이 맥락에서 배열과 포인터는 어떤 의미에서는 동일하다.

포인터는 메모리의 주소이고 배열은 메모리 덩어리이다.

앞서 우린 메모리 덩어리를 배열이라는 이름으로 사용했지만 조금 더 일반적으로 배열은 [] 를 통해 나타낼 수 있는 메모리 덩어리인 것이다.

이제 우리는 원하는 만큼의 메모리를 할당할 수 있기 때문에 이 2가지 개념을 서로 바꿔서 사용할 수 있게 된 것이다.

물론 C 에서는 미묘한 점이 있지만 배열을 구현했을때와 같은 결과를 낼 수 있다. 단지 포인터와 malloc을 이용한다면 말이다.

 

이렇게 3개의 값을 넣은 코드가 완성되었다. 이제는 또 다른 정 수 값이 필요하다고 가정해보자. 배열의 크기를 바꾸고 싶은 것이다. 어떻게 하면될까??

 

3. int *tmp = malloc(4 * sizeof(int)); if ( tmp == NULL ) { return 1; }

 

우선 값을 옮길 임시 변수를 만들어서 4개의 정수를 넣을 메모리를 할당받도록 하자.

4개의 정수 크기만큼의 새로운 메모리 덩어리를 만든 것이다. 그리고 이것 또한 에러 검사를 위해 if 문을 써준다.

 

이렇게 하면 이제 크기가 3, 4인 두 개의 메모리 덩어리를 가지고 있게 된다.( list 와 tmp )

 

4. for (int i = 0; i < 3; i++) { tmp[i] = list[i]; }

 

그리고 list에 있는 값을 옮기기 위해 list 내의 각각의 값에 접근하여 새로운 메모리 덩어리에 넣어주면 된다. 이를 위해 for문을 사용한 것이다.

새로운 메모리 덩어리 또한 배열처럼 사용할 수 있기 때문에 [] 를 사용한다.

즉, list[i] 에 있는 것을 tmp[i] 에 저장한다는 의미이다. 따라서, list 배열에서 tmp 배열로 정수를 복사하게 된다.

 

5. tmp[3] = 4;

 

list에 있는 값을 옮기는 것에 그치지 않고 다음으로 새로운 정수 4도 저장하는 코드이다.(tmp 의 4번째 위치에)

 

이렇게 for 문과 tmp[3] = 4; 를 통해 모든 값들을 기존의 배열에서 새로운 배열로 옮기는 물리적인 개념을 구현하게 된 것이다.

 

6. free(list);

 

기존 메모리 덩어리 사용이 끝났기 때문에 컴퓨터에 이 메모리를 돌려주기 위해 free 함수를 사용한다.

(   ) 안에는 free 하고 싶은 메모리 덩어리의 주소를 넣어준다.

하나의 주소만 넣어줘도 컴퓨터는 처음에 얼마만큼의 byte를 할당했는지 기억해낸다. 그리고 그냥 이 포인터가 가리키는 것이 무엇이든 모두 free 한다.

 

7. list = tmp;

 

그럼 이제 기존 list를 없애고 list = tmp 를 통해 업데이트 시키면서 이름을 바꿔준 것이다. 원래 포인터 이름인 list 를 그대로 쓰기 위함이다. 따라서, list 가 tmp와 같은 곳을 가리키도록 해준 것이다.

 

8. for (int i = 0; i < 4; i++) { printf("%i\n", list[i]); } 

 

위의 모든 과정이 잘 되었다면 이제는 제대로 값을 확인하기 위해 list를 모두 출력하는 코드이다.

 

9. free(list);

 

마지막으로 새로운 메모리 덩어리를 free 해줘야한다.( 크기가 4인 새로운 메모리 덩어리를 free 해주는 것 )

만약 해제해주지 않았다면 valgrind를 사용했을 때 메모리가 누수되고 있다고 경고가 나올 것이다.

 

이 프로그램을 컴파일한 뒤 실행하면 1 2 3 4 가 출력된다.

사실 이 프로그램은 좋지 않다. 그냥 4개의 정수를 저장하고 싶어진다면 이전 코드를 삭제하고 다시 짜면 되기 때문이다. 위 코드는 그저 시범을 위한 것이다. 만약 프로그램이 더 클 때 새로운 정수를 받아와서 메모리가 더 필요해지면 이런 방식으로 malloc을 사용하면 된다는 시범일 뿐이다.

 

이 과정을 간단하게 만들어주는 함수가 있다. malloc 대신 realloc 을 사용하는 것이다.

이 함수를 이용하면 tmp에 적용한 것처럼 malloc 을 이용하여 직접 메모리를 새로 할당하거나 for 문을 사용한 코드로 직접 값들을 옮기고 free를 할 필요가 없게 된다. realloc 을 이용한 코드를 살펴보자.

1. int *tmp = relloc(list, 4 * sizeof(int)); if ( tmp == NULL ) { return 1; }

 

realloc은 메모리를 새로 할당한다는 의미이다. list를 새로 할당하고, 정수 크기의 4배를 새로 할당하려고 한다는 의미이다. relloc 으로 반환된 것을 tmp에 임시로 저장한다.

 

2. for 문과 free(list) 삭제

 

for 문과 free(list) 를 삭제함으로써 전 코드보다 간단하게 만들어준다.

 

realloc 은 이미 할당받은 기존 메모리 덩어리를 새롭게 가져오고(list), 원래보다 크든 작든 새롭게 설정된 크기로 바꾸는 작업을 한다. realloc 이 기존 배열에서 새로운 배열로 데이터를 복사해주고 if 문을 통해 에러 검사를 한 뒤 새로운 값만 저장하기만 하면 된다.(tmp[3] = 4;)

 

list = tmp; 는 list 가 tmp와 같은 곳을 가리키도록 한 것이다.

 

이렇게 realloc 을 통해 기존에 길었던 코드를 간단하게 만들 수 있다.

 

 

※ 만약 list = malloc(4 * sizeof(int)); 와 같이 새로운 메모리 덩어리로 업데이트 하는 것은 어떻게 될까??

 

이렇게 하면 이전에 할당한 메모리 덩어리들이 빠르게 사라지게 된다. 기존의 메모리 덩어리는 컴퓨터 어딘가에 떠다니게 된다. 하지만 여기를 가리키는 포인터가 없는 것이다. 따라서, 이것은 임시 변수를 만들어서 기존의 메모리를 놓치지 않도록 해야하는 중요한 이유이다 !!

 

※ 위와 같이 tmp를 정수 포인터로 초기화하고 배열로 사용하는 것은 문제가 되지 않는다. 

 

배열은 메모리 덩어리이기 때문이다. C 에서는 [] 를 간단한 연산을 통해 메모리의 어떤 부분으로 이동하는데 사용할 수 있다. malloc, realloc 과 같은 함수들은 모두 메모리 덩어리를 다르게 말해 연속적인 메모리의 byte 들을 반환해준다. 그렇기 때문에 [] 를 사용할 수 있다. 배열은 본질적으로 메모리 덩어리이기 때문이다. malloc은 메모리 덩어리를 반환해주고 그러므로 이를 배열이라고 생각할 수 있다. 이런 관점에서 두 개념은 같은 것이다. 

그리고 배열은 자동으로 free를 해준다. 컴파일러를 통해 자동으로 이 과정이 진행되기에 따로 free를 해주지 않았던 것이다.

 

 

자료출처 : 부스트코스 - https://www.boostcourse.org/cs112/lecture/119037?isDesc=false