이번 글은 정렬 알고리즘 중에서 Quick Sort에 대한 글입니다. 퀵 정렬은 불안정 정렬에 속하며 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속합니다. 퀵 정렬은 합병정렬과 비슷하게 분할 정복(Divide And Conquer)알고리즘을 사용합니다. C++ STL의 sort()의 경우 순차열 [b, e) 원소들을 퀵 정렬로 수행하기 때문에 평균적으로는 O(N log N)의 시간복잡도를 보장을 하며 최악의 경우 O(N^2)의 시간 복잡도를 가집니다. 퀵 정렬의 원리는 pivot을 임의의 인덱스에 하나잡은 뒤 Left/Right Pivot을 양 끝으로 잡고 현재 Pivot보다 작은 값들은 왼쪽으로, Pivot보다 큰 값들은 오른쪽으로 옮기면 됩니다! 이후 Pivot을 제외한 왼쪽 부분과 오른쪽 ..
제가 상속관계에서 형변환을 할 때와 virtual 유무에 대해 햇갈렸던 부분들을 정리한 글입니다. (틀린 부분있다면 말해주시면 감사하겠습니다) 먼저 형변환의 방법으로는 int a = 10; float b = (float)a; // 옛날 C 스타일 (구식) float c = float(a); // C++ 스타일 (신식) 위와 같은 방법과 C++의 형변환 연산자 아래의 4가지가 있습니다. - static_cast : 기본 자료형 간의 형변환과 클래스 상속관계에서의 형변환만 허용한다. 명시적 형변환 (C스타일 보다 안전하다) - const_cast : 포인터와 참조자의 const 성향을 제거하는 형 변환 - dynamic_cast : 상속관계에서의 안전한 형변환 - reinterpret_cast : 상관없는 ..
이번글은 C++의 다형성의 가상함수에 대한 글입니다. C++ 다형성에 대해서 전부는 다룰 수 없고 제가 이해한 내용중에서도 "정적 바인딩", "동적 바인딩", "가상 함수", "vftable", "순수 가상함수", "추상 클래스" 정도에 대해서만 다룰려고 합니다. 먼저 아래의 코드에서 class A { public: void Func() { cout