Queue의 기본 데이터 타입으로 환형 리스트뿐만 아니라, 배열을 사용할 수 있다. capacity로 N개의 공간을 할당하고, 실제 데이터의 개수는 n, 가장 앞에 있는 원소의 인덱스를 front_index, 마지막 원소의 인덱스를 rear_index라고 한다면, 모듈러 연산을 활용하여 Queue에 원소를 추가하거나 제거할 때, O(n)의 공간 복잡도를 피할 수 있다. #pragma once #include // 예외 클래스 class RuntimeException{ public: RuntimeException(const std::string& err) : errorMsg(err){} std::string getMessage() const{ return errorMsg; } private: std::st..

태양계는 8개의 행성과 그 행성들의 위성들, 그리고 소행성 벨트와 카이퍼 벨트로 이루어져 있다. 태양계의 모든 천체를 시뮬레이션하기 어렵기 때문에, 9-body 시스템이라 생각한다. 뉴턴의 중력법칙에 따라, 외력이 없다면, i 번째 물체에 작용하는 힘은 요런 식이다. 여기서, i는 i 번째 행성, j는 태양이라고 하면, 8+7+6+5+4+3+2+1 개의 힘을 계산해야 한다. 단순히 행성 간의 중력은 무시한다고 하면, 8번 만으로 족하지만, 겉멋을 중요시하기 때문에 모두 계산한다. 그리고 이 힘을 가지고, 매 frame 마다, 행성의 위치를 업데이트시켜 준다. 태양계가 만들어진 조건은 완전 운빨이다. 각각의 천체의 mass, distance, orbital velocity 가 조금이라도 어긋나면, 행성은 ..

시간 복잡도와 공간복잡도 비교 best-case average-case worst-case space complexity Insertion Sort O(n) O(n²) O(1) Merge Sort O(n log n) O(n) Quick Sort O(n log n) O(n²) O(n) Heap Sort O(n log n) O(1) Counting Sort O(n + k) O(k) Insertion Sort 특징 삽입 정렬은 같은 크기의 데이터 시퀀스라도, 이미 정렬된 정도에 따라 빠를 수도 느릴 수 도 있다. 역으로 정렬된 경우 최악의 성능을 보인다. 데이터 셋의 크기가 시간에 따라 증가할 때, 실시간 정렬을 요구하는 경우에 사용한다. Pros 어느 정도, 이미 정렬된 경우 매우 매우 효과적이다. auxi..

Dynamic Dispatch - 클래스가 가상 함수를 가질 경우 Dynamic Dispatch는 클래스 메소드가 오브젝트의 타입에 따라 다르게 작동하는 것이다. Virtual Function을 통해서 클래스의 다형성을 구현할 때, Dynamic Dispatch가 사용된다고 할 수 있다. 그러나 Virtual Function을 실행할 때, 컴파일러는 자동적으로 Runtime LookUp(클래스의 계층구조를 따라 적합한 함수를 선택하는 것)이라는 추가적인 동작을 한다. Vtable은 클래스가 Virtual Function을 가질 때, 자동적으로 생성되는 자료구조이며, 이 Vtable은 해당 클래스의 Virtual Function을 가리키는 포인터를 가지고 있다. 따라서, 추가적인 메모리를 할당한다. Run..

같은 기능을 하고, 같은 시간 복잡도를 가진 알고리즘 일지라도, 어셈블리 레벨에서의 원시연산 Primitive Operation이 일어나는 횟수에 따라, 실행시간에 차이가 있을 수도 있다. 일반적으로 원시 연산을 다음을 포함한다. 변수에 값 할당 함수 호출 산술 연산(사용하는 CPU에 따라, '더하기' 가 더 빠를수도, '곱하기' 가 더 빠를수도 있다. '나누기'는 가장 비용이 크다.) 두 수의 비교 인덱싱 객체의 참조 따라가기 리턴

DFS와 BFS는 그래프 탐색 알고리즘 중 대표적인 두 가지 알고리즘이다. DFS (Depth First Search) 깊이 우선 탐색으로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 더 이상 방문할 노드가 없을 때까지 모든 경로를 탐색하고, 백트래킹(backtracking)을 통해 경로를 변경해가며 탐색한다. 스택이나 재귀 함수를 이용하여 구현할 수 있다. 가장 먼저 발견한 경로를 탐색하므로 메모리의 사용이 적으나, 최단 경로를 보장하지 않는다. BFS (Breadth First Search) 너비 우선 탐색으로, 그래프에서 가까운 부분부터 탐색하는 알고리즘이다. 시작 노드에서 시작하여 이웃한 노드들을 모두 방문한 후, 그 이웃한 노드들의 이웃들을 방문하는 식으로 네트워크 전체를 탐색한다..