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..

시간 복잡도와 공간복잡도 비교 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..

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

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

션팅 알고리즘(Shunting Yard Algorithm)은 중위 표기법(infix notation) 수식을 후위 표기법(postfix notation)으로 변환하는 알고리즘이다. 중위 표기법은 일반적으로 우리가 일상적으로 사용하는 수식 표기법이다. 예를 들어, "3 + 4 * 2 / (1 - 5)^2"와 같은 형태를 갖는다. 하지만, 컴퓨터가 수식을 계산하는 경우에는 후위 표기법을 사용하는 것이 효율적이다. 션팅 알고리즘은 다음과 같은 절차로 수식을 후위 표기법으로 변환한다. 1. 수식의 각 토큰(숫자 및 연산자)을 순차적으로 읽는다. 2. 토큰이 숫자인 경우, 출력 큐(output queue)에 추가한다. 3. 토큰이 연산자인 경우, 연산자 스택(operator stack)에 추가한다. 4. 연산자를..

트리(Tree) 자료구조란 계층적 관계를 가지는 노드(node)들로 이루어진 자료구조로, 루트(root) 노드에서 시작하여 자식(child) 노드들이 계속해서 연결된 형태로 구성된다. 각 노드는 하나의 값(value)을 가지며, 부모(parent) 노드와 자식 노드들 간의 관계는 트리 구조에서 중요한 역할을 한다. 트리의 특징은 다음과 같다. 1. 단일 루트 노드를 가진다 2. 각 노드들은 자식 노드들을 가지고 있으며, 이들은 서로 동등한 관계를 가진다. 3. 순환 구조(cycle)가 없다. 4. 모든 노드는 반드시 하나의 부모 노드만을 가진다. 트리 자료구조의 활용 예시로는 파일 시스템이나 게임에서의 캐릭터 관계 등이 있다. 또한 이진 탐색 트리(binary search tree)와 같은 특수한 형태의..