가변배열이 필요한 이유?
아래 예문이 가능한가?
🔖예문
int main()
{
int a = 100;
int arr[a] = {};
}변수 a는 다른 코드에 의해 변경될 수 있는 값이다.
main함수가 컴파일 할 때 스택 메모리를 얼마나 할당할 건지 알려줘야 하는데, a의 값이 변하면 메모리의 공간도 변할 수 있기 때문에 위의 수식으로는 컴파일을 할 수가 없다. 크기를 확정할 수 없다.
즉, 프로그램 도중에 필요한 만큼 할당할 수 있는 배열(가변배열)을 만들고 싶다면 지역변수로는 불가능하다. 동적할당된 힙 영역에 있는 메모리만 가능하다.
🔍참고
객체(Instance)
int a;위 예문에서 int는 자료형, a는 객체에 해당한다. int라는 자료형을 실제로 만들어 낸 것이다. 내가 의도한 자료형의 실질적인 데이터를 말한다.
자료형이 도장이라면 객체는 도장으로 찍어낸 것이다.
구조체 자료형 생성
가변배열이라는 동작을 할 수 있는 자료형을 만들어서 객체를 생성하면 그게 가변배열이 된다.
구조체를 사용하여 가변배열에 사용할 자료형을 만들어보자.
🔖예문
// 먼저 Arr.h 와 Arr.cpp 파일을 생성해준다.
// Arr.h
// 구조체를 사용하여 가변배열 동작을 할 수 있는 자료형을 만든다.
typedef struct _tagArr
{
int* pInt; // 주소를 받는다.
int iCount; // 배열에 몇 개가 들어가는지 세기위해 초기 Count를 정해준다.
int iMaxCount; // 최대 Count가 몇 개 인지 정해준다.
}tArr; // 가변배열 자료형초기화
이 자료형을 가지고 main 함수에서 호출하여 초기화를 해주자.
🔖예문
int main()
{
tArr s;
s.pInt = (int*)malloc(40)
s.iCount = 0;
s.iMaxCount = 10;
}하지만 초기화는 반복해서 사용할 것이기 때문에 함수로 만들어준다.
🔖예문
// Arr.h
...
// 배열 초기화 함수
void InitArr(tArr* _pArr);
/=============================================/
// Arr.cpp
// 헤더에서 선언한 함수를 구현한다.
#include "Arr.h"
#include <iostream>
void InitArr(tArr* _pArr, int _iCount)
{
_pArr->pInt = (int*)malloc(sizeof(int) * 2); // int형 변수 두개를 담을 힙 메모리 공간을 할당
_pArr->iCount = 0; //
_pArr->iMaxCount = 2;
}해제
가변배열을 사용하고 나서 프로그램을 종료할 때 자동으로 힙 메모리 영역을 해제해주지 않기 때문에 해제하는 함수도 만들어준다.
🔖예문
// Arr.h
...
// 배열 메모리 해제 함수
void ReleaseArr(tArr* _pArr);
/=============================================/
// Arr.cpp
// 헤더에서 선언한 함수를 구현한다.
#include "Arr.h"
#include <iostream>
...
void ReleaseArr(tArr* _pArr)
{
free(_pArr->pInt); // 해제해주는 함수
_pArr->iCount = 0;
_pArr->iMaxCount = 0; // 최대 배열 갯수도 0으로 대입해서 해제해준다.
}main 함수에서 호출하면 이런 형태가 될 것이다.
🔖예문
int main()
{
tArr s;
InitArr(&s);
ReleaseArr(&s);
}데이터 추가
여기까지 만들었으면 이제 가변배열을 실제로 데이터를 추가하는 함수를 만들어보자.
🔖예문
// Arr.h
...
void PushBack(tArr* _pArr, int _iData); // _iData는 배열에 들어갈 데이터
/=============================================/
// Arr.cpp
// 헤더에서 선언한 함수를 구현한다.
...
void PushBack(tArr* _pArr, int _iData)
{
// 힙 영역에 할당한 공간이 다 참
if (_pArr->iMaxCount <= _pArr->iCount)
{
Reallocate(_pArr); // 재할당 함수
}
// 공간이 남아있다면 데이터 추가
_pArr->pInt[_pArr->iCount++] = _iData; // 데이터를 추가한 후 iCount를 1 증가시킨다.
}재할당 함수
재할당 함수를 생성해준다.
만들기 전에 생각해봐야할 것은 재할당 함수는 Arr.cpp 파일 안에 PushBack 함수 안에서만 동작하면 된다.
Arr.h에 만들면 힙 메모리 공간이 아직 남아있는데도 Arr.h 가 포함되있는 곳에서라면 언제든지 재할당할 수 있기 때문에 이걸 막기 위해서 Arr.cpp 파일 안에서 선언 및 구현까지 한다.
가변배열에 사용한 malloc 함수는 입력한 크기만큼 힙 메모리 영역을 할당해서 그 주소값을 넘겨줄 뿐이다. 즉, 사용자가 원하는 곳의 주소를 할당받지는 못한다.
따라서 재할당을 하기 위해선 더 큰 크기의 메모리 영역을 새로 할당하고, 기존 메모리 영역에 있는 데이터를 복사한 후에 해제해줘야 한다.
🔖예문
// Arr.cpp
...
void Reallocate(tArr* _pArr)
{
// 1. 더 큰 새로운 힙 메모리 영역을 할당해준다. 여기선 2배씩 늘려주는 것으로 한다.
int* pNew = (int*)malloc(_pArr->iMaxCount * 2 * sizeof(int)); // 바로 pInt주소에 넣어버리면 기존 영역의 주소값은 누구도 가르키고 있지 않게 되기 때문에 지역변수로 받아놓는다.
// 2. 기존 힙 메모리 영역에 있던 값을 새 영역에 복사한다.
for (int i = 0; i < _pArr->iCount; ++i)
{
pNew[i] = _pArr->pInt[i];
}
// 3. 기존 영역을 해제한다.
free(_pArr->pInt);
// 4. 배열이 새로 할당된 메모리 영역을 가리키게 한다.
_pArr->pInt = pNew;
// 5. iMaxCount 변경점 적용
_pArr->iMaxCount *= 2;
}🔍참고
일반 배열에서도 초과 접근하는 것을 주의해야 하는 것처럼, 만약 위 처럼 하지 않고 포인터를 써서 기존 힙 메모리 영역을 넘어가는 순간 다른 데이터를 덮어씌워버리는 문제가 발생할 수 있다.
컴파일 단계에서도 오류라고 잡아주지 않고 굉장히 나중에 문제가 발생할 수 있기 때문에 주의해야 한다. 이것을 힙손상(Heap Corruption)이라고 한다.
코드 정리
마지막으로 정리해보자면,
🔖예문
// Arr.h
typedef struct _tArr
{
int* pInt;
int iCount;
int iMaxCount;
}tArr;
// 가변배열 초기화 함수
void InitArr(tArr* _pArr);
// 가변배열 데이터 추가 함수
void PushBack(tArr* _pArr, int _iData);
// 가변배열 해제 함수
void ReleaseArr(tArr* _pArr);
/=============================================/
// Arr.cpp
#include "Arr.h"
#include <iostream>
// 가변배열 초기화 함수 구현
void InitArr(tArr* _pArr, int _iCount)
{
_pArr->pInt = (int*)malloc(sizeof(int) * 2); // int형 변수 두개를 담을 힙 메모리 공간을 할당
_pArr->iCount = 0; //
_pArr->iMaxCount = 2;
}
// 가변배열 데이터 추가 함수 구현
void PushBack(tArr* _pArr, int _iData)
{
// 힙 영역에 할당한 공간이 다 참
if (_pArr->iMaxCount <= _pArr->iCount)
{
Reallocate(_pArr); // 재할당 함수
}
// 공간이 남아있다면 데이터 추가
_pArr->pInt[_pArr->iCount++] = _iData; // 데이터를 추가한 후 iCount를 1 증가시킨다.
}
// 가변배열 재할당 함수 선언 및 구현
void Reallocate(tArr* _pArr)
{
// 1. 더 큰 새로운 힙 메모리 영역을 할당해준다. 여기선 2배씩 늘려주는 것으로 한다.
int* pNew = (int*)malloc(_pArr->iMaxCount * 2 * sizeof(int)); // 바로 pInt주소에 넣어버리면 기존 영역의 주소값은 누구도 가르키고 있지 않게 되기 때문에 지역변수로 받아놓는다.
// 2. 기존 힙 메모리 영역에 있던 값을 새 영역에 복사한다.
for (int i = 0; i < _pArr->iCount; ++i)
{
pNew[i] = _pArr->pInt[i];
}
// 3. 기존 영역을 해제한다.
free(_pArr->pInt);
// 4. 배열이 새로 할당된 메모리 영역을 가리키게 한다.
_pArr->pInt = pNew;
// 5. iMaxCount 변경점 적용
_pArr->iMaxCount *= 2;
}
// 가변배열 해제 함수 구현
void ReleaseArr(tArr* _pArr)
{
free(_pArr->pInt); // 해제해주는 함수
_pArr->iCount = 0;
_pArr->iMaxCount = 0; // 최대 배열 갯수도 0으로 대입해서 해제해준다.
}
/=============================================/
// main.cpp
#include <iostream>
#include "stdio.h"
#include "Arr.h"
int main()
{
tArr s1;
InitArr(&s1); // 초기화 함수
for (int i = 0; i < 10; i++) // 반복문을 사용해서 가변배열에 데이터를 추가해준다.
{
PushBack(&s1, i);
}
ReleaseArr(&s1); // 힙 메모리 해제
}버블정렬
배열에 있는 데이터를 순서대로 정렬시키는 방식
가변배열에 입력한 데이터를 버블정렬을 사용해서 정렬시켜보자
🔖예문
// Arr.h
...
void Sort(tArr* _pArr); // 헤더에 Sort라는 함수를 선언
/=============================================/
// Arr.cpp
...
void Sort(tArr* _pArr)
{
// 1. 데이터가 1개 이하이면 정렬하지 않음
if (_pArr->iCount <= 1)
return;
// 3. 모든 수가 정렬될 때까지 반복
while(true)
{
// 2. 두 수를 비교해서 큰 수가 뒤로 가도록 한다.
bool bFinish = true;
for (int i = 0; i < _pArr->iCount - 1; i++)
{
if (_pArr->pInt[i] >= _pArr->pInt[i + 1])
{
int temp = _pArr->pInt[i]; // 임시로 다른곳에 저장해놓음
_pArr->pInt[i] = _pArr->pInt[i + 1];
_pArr->pInt[i + 1] = temp;
bFinish = false; // 정렬이 안되있으면 false
}
}
// 모두 정렬 되었으면 종료
if(bFinish)
break;
}
}정렬되지 않은 무작위의 수를 얻기 위해서 Rand함수를 사용한다.
🔍참고
Rand함수는 마치 책에다가 무작위 숫자를 페이지를 적어놓고 뽑는것과 마찬가지이다.
결국 거기 적혀있는 숫자만 나오기 때문에 완전한 난수라고 하기 어렵다.
그래서 완벽하진 않지만 어느정도 보완을 하기 위해srand함수를 사용하는데, 이것은 씨드값을 통해서 그 페이지를 변경시켜주는 함수이다. 그렇지만 씨드값이 고정되어 있다면 페이지 수가 정해지는 건 마찬가지이기 때문에 씨드값에 시간값을 넣어준다.srand(time(nullptr))여기서 time은 지금 이 순간의 날짜, 시, 분, 초 까지 정해지기 때문에 절대 겹칠 수가 없다.
최근에 가장 난수에 가깝다는 함수가 나왔지만 나중에 알아보자.
🔖예문
int main()
{
srand(time(nullptr)); // 시간을 씨드값해서 랜덤 페이지를 변경해줌
tArr s = {};
InitArr(&s);
for (int i = 0; i < 10; i++)
{
int iRand = rand() & 100 + 1; // 1 ~ 100 까지의 숫자를 10개를 뽑고싶다
PushBack(&s, iRand);
}
// 정렬 전 출력
printf("정렬 전\n");
for (int i = 0; i < s.iCount; i++)
{
printf("%d\n", s.pInt[i]);
}
Sort(&s); // 버블정렬하는 함수를 호출
// 정렬 후 출력
printf("\n정렬 후\n");
for (int i = 0; i < s.iCount; i++)
{
printf("%d\n", s.pInt[i]);
}
ReleaseArr(&s);
return 0;
}실행결과
정렬 전
11
14
75
40
42
22
79
88
23
99
정렬 후
11
14
22
23
40
42
75
79
88
99함수 포인터
가변배열에 있는 데이터를 정리하는데 있어서 내가 원하는 방식으로 정렬할 수 있으면 더 좋지 않을까?
