본문 바로가기

자료구조와 알고리즘/[서적]C++로 구현하는 자료구조와 알고리즘9

4장-1. 알고리즘 분석-1 상수 함수 f(n) = c 이 때 c = 5, c = 27, c = 2¹⁰과 같이 고정된 임의의 상수임 즉, 어떠한 매개변수 n에 대해 상수 함수 f(n)은 c를 반환함 다시 말해 n의 값에 상관없이 f(n)은 항상 상수 c와 같다. 상수 함수는 간단한 만큼 알고리즘 분석에 유용하다. 왜나면 두 숫자 더하기, 값을 변수에 넣기, 두 개 숫자 비교하기 같은 기본 연산에서 스탭의 수를 특정 지으므로. 로그 함수 자료 구조와 알고리즘의 분석에서 놀라운 것은 로그 함수가 흔하게 사용된다는 것. f(n) = logₐn 이고, a > 1)이 흔하게 사용 됨 특히, logₐn과 같거나 큰 정수 중 가장 작은 정수를 쉽게 계산할 수 있다. 그 이유는 그 숫자가 1보다 작거나 같을 때까지 n을 a로 나눌 수 있는 횟수와.. 2022. 9. 19.
3장-6. 재귀 함수 선형 재귀 재귀의 가장 간단한 형태 호출이 발생할 때 최대 하나의 재귀호출이 발생함 #include int LinearSum(int* arr, int n) { if (n == 1) return arr[0]; else return LinearSum(arr, n - 1) + arr[n - 1]; } int main() { int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int sum = LinearSum(arr, 10); std::cout end의 상황에 도달하게 되기 때문 후미 재귀 재귀 함수를 사용할 때는 성능도 생각해야 한다. 컴퓨터 메모리가 부족할 때는 재귀 알고리즘에서 비재귀 알고리즘을 이끌어내야 함 void iterativeReverseArray(int* a.. 2022. 9. 16.
3장-5. 재귀 함수 재귀란 무엇인가? for문이나 while문 이외에 반복을 구현하는 또 다른 방법 자신의 정의 내에서 자기 자신을 호출하는 것 재귀는 반복적인 작업을 수행하는데 명쾌하고 강력한 대안을 제시한다! 계승 함수 양의 정수 n의 계승(n!)는 1부터 n까지의 정수곱이다. n = 0이라면 n!는 1로 정의된다. 더 일반적으로는 n >= 0이다. 5! = 5 x 4 x 3 x 2 x 1 = 120 이런 n!를 나타내기 위해 factorial(n) 이라는 표현을 사용한다. 계승 함수는 재귀적인 공식을 제시하는 방법으로도 정의된다. factorial(5) = 5 * (4 * 3 * 2 * 1) = 5 * factorial(4) 그래서 일반적으로 양에 정수에 대해 factorial(n)은 n * factorial(n-1).. 2022. 9. 13.
3장-4. 일반적인 링크드 리스트 구현 (단일, 이중, 환형) 단일 링크드 리스트 구현 일반적인 단일 링크드 리스트는 SLinkedList라고 불린다. C++의 템플릿 매커니즘을 통해 string이 아닌 다른 타입들도 받을 수 있도록 한다. 따라서 링크드 리스트를 구성하는 노드(SNode)도 템플릿으로 작성된다. #pragma once // SLinkedList를 구성하는 노드 template class SNode { private: E elem;// 노드가 가진 값 SNode* next; // 다음 요소를 가리키는 포인터 friend class SLinkedList; }; // 일반화된 단일 링크드 리스트 template class SLinkedList { public: SLinkedList(); ~SLinkedList(); bool empty() const;//.. 2022. 9. 12.

티스토리툴바