1. 과제 풀이
1번 과제를 하면서...
- 도전과제에 있어서 sorting 알고리즘을 구현해야 하였기에, 무슨 알고리즘을 구현할까 하다가 Quick Sort 알고리즘을 구현하였다. (빠른 sorting 알고리즘 중 하나니까... 나중에 merge sort도 꼭 구현해 볼 것이다.)
- Quick Sort를 알아보자
- N개의 값이 있을 때 이 값들을 특정값(pivot) 이상, 미만으로 분류하는 아이디어로 시작한다. -> O(N)
- 이 아이디어를 가지고 pivot 왼쪽에는 pivot보다 작은 값, 오른쪽에는 큰 값을 두는 작업을 재귀적으로 실행하는 방식이다.
- 코드로 보면, Partition 이라는 함수와 QuickSort라는 재귀함수가 존재한다.
- Partition 함수는 pivot을 하나 잡고, 그에 따라 pivot 왼쪽에는 작은 값, 오른쪽에는 큰 값이 오도록 만들어주는 함수이다.(swap 이용)
- QuickSort는 정렬하고자 하는 나눠서 Partition을 수행하도록 하는 재귀함수이다.
- Partition 함수 동작 예시 (pivot이 5이고, i가 -1 j가 0일 때의 동작 예시이다.)
- 6 1 4 8 3 9 2 5 의 숫자 배열이 있고, pivot은 맨 오른쪽 값인 5로 한다.
- 화살표를 두개를 가지고 시작하는데, 두 화살표 각각의 목적은
- 파란 화살표는 pivot보다 큰 값을 가리키는 화살표이고,
- 빨간 화살표는 pivot보다 작은 값을 가리키는 화살표이다.
- 만약 각각의 화살표가 해당하는 값을 가리키고 있다면, 두 값을 swap 해줘야 한다.
- 한 스텝을 그림으로 그리면 다음과 같다.
- 이후 함수의 반환값이 pivot의 index이며, 이를 통해 배열을 나눠 Partition함수의 동작을 반복한다.
- 코드와 실행 결과
- Quick Sort의 시간 복잡도
- 평균적으로 O(lgN)회 분할을 수행하게 된다. 평균적으로 O(NlgN)의 시간복잡도 이다.
- 그러나 만약 pivot을 잘못 잡은 경우 O(N) 까지 느려질 수가 있으며, 그 결과는 O(N^2) 이 될 수도 있다.
- pivot을 잘 선택하는 것이 곧 quick sort의 성능을 결정한다.
- 가장 왼쪽이나 오른쪽 값, 혹은 가운데 값 등을 사용하지만, 이러한 방법을 택할 때 분할의 시간복잡도가 O(N)이 될 수 있다.
- 이를 해결하기 위해서 많이 쓰는 방식은
- 중간값 선택
- 가장 왼쪽, 가장 오른쪽, 가운데 값 중에서 중앙값을 선택하는 방식
- 데이터값에 따른 중간값 선택
- 데이터가 3개 이하면 피벗은 반드시 마지막 값
- 데이터가 4개 이상이면 중간값 선택
- 피벗이 선택되면, 구간의 맨 끝 원소와 교환
- 퀵 소트 코드
#include <iostream>
using namespace std;
void Print(int board[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << board[i] << " ";
}
cout << "\n\n";
}
int Partition(int board[], int low, int high)
{
int pivot = board[high];
int i = low - 1;
for (int j = low; j < high; ++j)
{
if (board[j] < pivot)
{
i += 1;
swap(board[i], board[j]);
}
}
swap(board[i + 1], board[high]);
Print(board, 8);
return i + 1;
}
void QuickSort(int board[], int low, int high)
{
if (low < high)
{
int pos = Partition(board, low, high);
QuickSort(board, low, pos - 1);
QuickSort(board, pos + 1, high);
}
}
int main()
{
int num;
int board[8] = { 6,1,4,8,3,9,2,5 };
QuickSort(board, 0, 7);
}
2번 과제를 하면서...
- 평가 기준을 유심히 봤던 것 같다. 신경을 썼던 키워드를 정리해 보면, 아래와 같고 각각에 해당하는 내용을 작성할 것이다.
- 필수 과제의 경우
- 도전과제의 경우
- "동적 할당된 객체를 메모리에서 올바르게 해제하는지"
- "메모리 누수 발생 금지"
- "배열의 제한된 크기 고려"
평가 기준표
- 생성자와 소멸자의 호출 순서
- 클래스는 객체가 생성될 때, 생성자가 호출되고 해당 객체의 수명이 다하면 소멸자가 호출되게 된다.
- 만약 어떤 클래스가(자식) 다른 클래스(부모)를 상속했다고 하면
- 자식 클래스를 기반으로 한 객체를 생성한 경우
- 생성자는 부모 생성자부터 호출되며,
- 소멸자는 자식 소멸자부터 호출된다.
- 주의할 점은 우리가 만들 부모 클래스의 소멸자는 항상 virtual 로 하자
- 아래의 코드에서 부모 클래스 소멸자가 virtual 이 아니라면, 자식의 소멸자가 호출되지 않게 된다.
- 왜냐면,
- C++는 기본적으로 "정적 바인딩"이기 때문에, 소멸자도 우리가 생성한 객체의 타입인 Base를 따라갈 것이기 때문이다.
#include <iostream>
using namespace std;
class Base
{
public:
Base()
{
cout << "base 생성\n";
}
virtual ~Base()
{
cout << "base 소멸\n";
}
};
class Derived : public Base
{
public:
Derived()
{
cout << "derived 생성\n";
}
~Derived()
{
cout << "derived 소멸\n";
}
};
int main()
{
Base* b = new Derived;
delete b;
return 0;
}
- 동적 할당된 객체의 메모리 해제
- 우리가 new를 통해 동적 할당을 한다면, 항상 delete를 통해 해제해 주어야 한다.
- 과제 코드의 경우 Zoo라는 클래스에 Animal* 를 담은 변수(animals)가 있고, 이 안에 동적 할당된 객체들이 들어가게 된다.
- 그렇기 때문에 Zoo의 소멸자에서 animals 배열을 순환하면서, delete를 해주었다.
- 이때...
- delete[ ] animals 를 쓰려고 했는데, 이건 잘못된 행동이었다.
- 왜냐면 delete[ ]의 의미는 동적 할당된 배열을 삭제할 때 사용하는 것이기 때문이다.
- 다시 말해서 new[ ] 로 생성한 배열을 삭제할 때 쓰는 것이다.
- 먼저 내가 작성한 코드의 내용을 다시 생각해보면,
- Zoo 클래스에 있는 Animal* animals[10];은 정적으로 할당 되어 있는 배열이다. (Animal* 타입을 10개 가진 배열)
- 동적으로 할당된 값들은 Animal* 즉 animals 배열 안에 있는 값들이다. (new 를 했지, new [ ]를 한것이 아니기 때문에)
- 그러므로 Zoo 소멸자에서 delete[ ] animals를 호출하는 것은 잘못된 동작이다.
- 아래처럼 배열을 돌면서 각각의 Animal* 를 해제해주는 것이 맞다.
#include <iostream>
using namespace std;
class Animal
{
public:
Animal()
{
cout << "animal make\n";
}
~Animal()
{
cout << "animal die\n";
}
};
class Zoo
{
public:
Zoo()
{
cout << "open zoo\n";
}
~Zoo()
{
for (int i = 0; i < cnt; ++i)
delete animals[i];
//delete[] animals; 잘못된 동작
}
void Add(Animal* animal)
{
animals[cnt] = animal;
cnt++;
}
private:
Animal* animals[10];
int cnt = 0;
};
int main()
{
int n;
cin >> n;
Zoo zoo;
for (int i = 0; i < n; ++i)
{
Animal* animal = new Animal;
zoo.Add(animal);
}
return 0;
}
- (동적 할당된 객체의 메모리 해제) 아직 이 내용임
- 그렇다면, delete[ ] 를 쓰려면, 아래 코드와 같이 구성해야 한다.
- 코드를 설명 해보자면,
- 기존에 원하는 동작은 Animal*를 가지는 크기 10개짜리 배열이므로,
- Zoo 클래스의 변수는 Animal** animals; 와 같이 선언해야 한다.
- 이후로 생성할 때 size를 넣어주어서 new Animal*[size]; 를 통해 배열을 동적 할당 해주었다.
- 그리고 Zoo 소멸자에서도 아래와 같이 수행해주면 된다.
- Animal* 타입의 배열 소멸 -> delete [ ] animals;
- 배열 안에 들어있는 각 Animal* 객체 소멸 -> for문을 통해 delete animals[i];
- 마지막으로 delete zoo; 를 꼭 해주자
#include <iostream>
using namespace std;
class Animal
{
public:
Animal()
{
cout << "animal make\n";
}
~Animal()
{
cout << "animal die\n";
}
};
class Zoo
{
public:
Zoo() = delete;
Zoo(int size)
:cnt(0)
{
animals = new Animal*[size];
cout << "open zoo\n";
}
~Zoo()
{
for (int i = 0; i < cnt; ++i)
{
delete animals[i];
}
delete[] animals;
}
void Add(Animal* animal)
{
animals[cnt] = animal;
cnt++;
}
private:
Animal** animals;
int cnt = 0;
};
int main()
{
int n;
cin >> n;
Zoo* zoo = new Zoo(10);
for (int i = 0; i < n; ++i)
{
Animal* animal = new Animal;
zoo->Add(animal);
}
delete zoo;
return 0;
}
실행 결과
- 메모리 누수
- 메모리 누수가 발생할 수 있는 몇 가지 경우를 적어보면 (출처는 chat gpt)
- 동적 메모리 할당 후 해제하지 않은 경우 (new 하고 delete 안한 경우)
- 중간에 예외처리 동작으로 인해 메모리 해제가 누락되는 경우
- 동적 배열 선언시 delete를 사용하는 경우
- 다차원 배열의 해제에 delete만 사용한 경우
- 클래스 소멸자에서 메모리 해제를 누락한 경우
- 그렇다면 각각의 해결책을 적어보면
- new 하면 delete 하기
- 스마트 포인터로 raw 포인터 대체하기 (이건 사실 다른곳에도 해당하는 해결법이긴 함)
- delete[ ] 사용하기
- 동적할당한 배열의 내용물 메모리 해제 + 동적할당한 배열 메모리 해제
- 클래스 내부 소멸자에 동적할당한 객체의 메모리 해제
- 코드로 정리해보자면 다음과 같다.
- 각 문제번호가 함수의 번호이다.
- // 주석처리된 부분이 해야 하는데 하지않고, 넘어간 부분을 말한다.
#include <iostream>
#include <memory>
using namespace std;
void Func1()
{
int* ptr = new int(42);
cout << *ptr << "\n";
//delete ptr; delete로 해제해주기
}
void Func2()
{
int* ptr = new int(42);
throw runtime_error("Exception!\n");
delete ptr;
//unique_ptr<int> ptr = make_unique<int>(42); 스마트포인터 쓰기
}
void Func3()
{
int* arr = new int[10];
delete arr;
//delete[] arr; 배열의 동적할당 해제하기
}
void Func4()
{
int row = 3;
int col = 5;
int** matrix = new int* [row];
for (int i = 0; i < row; ++i)
{
matrix[i] = new int[col];
}
//배열의 내용물도 동적할당 했으므로, 해제해주기
/*for (int i = 0; i < row; ++i)
delete matrix[i];*/
delete[] matrix;
}
class Base
{
public:
Base()
{
int num = 10;
address = new int(num);
}
~Base()
{
//delete address; 동적할당한 멤버변수 메모리 해제
}
private:
int* address;
};
int main()
{
Base* base = new Base();
delete base;
return 0;
}
- 배열에 제한된 크기 고려
- 우리는 크기가 10짜리 배열을 클래스의 멤버변수로 가지고 있었다.
- 그렇기 때문에 만약 10 보다 더 많은 갯수의 Animal*를 넣는다면, 배열이 터질 것이다.
- 문제를 풀 때에는 입력된 값에서 부터 조건을 걸어 절대로 크기가 10이 넘는 숫자가 들어가지 않도록 했다.
- 더 추가적으로 안전한 코드를 만들기 위해서는 각각의 배열의 요소인 Animal* 를 사용할 때 animals[i] == nullptr 과 같은 체크를 해주면 더 좋다고 생각한다. (언리얼의 IsValid와 유사한 의도)