C++ TIL day 9

2024. 12. 27. 20:01·C++

1. 과제 풀이

  • 과제 깃허브 주소
    • 과제1 필수: https://github.com/GBL22M/SCC_CH2-1/blob/main/assignment/Essential.cpp
    • 과제1 도전: https://github.com/GBL22M/SCC_CH2-1/blob/main/assignment/Challenge.cpp
    • 과제2 필수: https://github.com/GBL22M/SCC_CH2-1/blob/main/assignment/Essential.cpp
    • 과제2 도전: https://github.com/GBL22M/SCC_CH2-1/blob/main/assignment/Challenge.cpp

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)이 될 수 있다.
          • 이를 해결하기 위해서 많이 쓰는 방식은
            1. 중간값 선택
              • 가장 왼쪽, 가장 오른쪽, 가운데 값 중에서 중앙값을 선택하는 방식
            2. 데이터값에 따른 중간값 선택
              • 데이터가 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)
      1. 동적 메모리 할당 후 해제하지 않은 경우 (new 하고 delete 안한 경우)
      2. 중간에 예외처리 동작으로 인해 메모리 해제가 누락되는 경우
      3. 동적 배열 선언시 delete를 사용하는 경우
      4. 다차원 배열의 해제에 delete만 사용한 경우
      5. 클래스 소멸자에서 메모리 해제를 누락한 경우
    • 그렇다면 각각의 해결책을 적어보면
      1. new 하면 delete 하기
      2. 스마트 포인터로 raw 포인터 대체하기 (이건 사실 다른곳에도 해당하는 해결법이긴 함)
      3. delete[ ] 사용하기
      4. 동적할당한 배열의 내용물 메모리 해제 + 동적할당한 배열 메모리 해제
      5. 클래스 내부 소멸자에 동적할당한 객체의 메모리 해제
    • 코드로 정리해보자면 다음과 같다.
      • 각 문제번호가 함수의 번호이다. 
      • // 주석처리된 부분이 해야 하는데 하지않고, 넘어간 부분을 말한다.
#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와 유사한 의도)

'C++' 카테고리의 다른 글

C++ 템플릿 - 헤더파일에서 구현하자  (0) 2024.12.30
C++ 코딩 스탠다드  (2) 2024.12.30
C++ TIL day 8  (0) 2024.12.26
Smart Pointer 보충  (0) 2024.12.24
C++ TIL day 7  (2) 2024.12.24
'C++' 카테고리의 다른 글
  • C++ 템플릿 - 헤더파일에서 구현하자
  • C++ 코딩 스탠다드
  • C++ TIL day 8
  • Smart Pointer 보충
gbleem
gbleem
gbleem 님의 블로그 입니다.
  • gbleem
    gbleem 님의 블로그
    gbleem
  • 전체
    오늘
    어제
    • 분류 전체보기 (184)
      • Unreal Engine (73)
      • C++ (19)
      • 알고리즘(코딩테스트) (27)
      • TIL (60)
      • CS (4)
      • 툴 (1)
  • 블로그 메뉴

    • 홈
    • 카테고리
  • 링크

    • 과제용 깃허브
    • 깃허브
    • velog
  • 공지사항

  • 인기 글

  • 태그

    additive animation
    map을 vector로 복사
    싱글턴
    const
    DP
    enhanced input system
    cin함수
    gamestate
    매크로 지정자
    C++
    actor 클래스
    motion matching
    blend pose
    템플릿
    상속
    BFS
    addonscreendebugmessage
    Vector
    applydamage
    character animation
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
gbleem
C++ TIL day 9
상단으로

티스토리툴바