Recursion(재귀)
2023. 6. 14. 18:40
알고리즘 + 자료구조
함수가 자기 자신을 적어도 한번 이상 호출한다면, 그것은 재귀함수이다. 재귀 함수를 시각화 했을때, 재귀 트리의 가지가 뻗어나가는 모양에 따라, 재귀 알고리즘을 분류할 수 있다. Linear Recursion : 가지가 갈라지지 않는 경우 Binary Recursion : English Ruler 문제 같은 경우 Multiple Recursion : abc, acb, bac...... 같은 조합 문제일 경우 재귀 함수의 장점은 정의가 간단하다는 것이고, nested for loop 같은 가독성이 좋지 않은 코드를 피할 수 있다는 점에 있다. 그러나, 함수를 호출하면, 컴퓨터는 이를 메모리에 기록하고, 함수가 반환될 때까지, 호출 스택에 쌓이게 된다. 따라서 메모리가 한정적인 상황이라면, 재귀 알고리즘을 ..
Recursion - English Ruler
2023. 6. 14. 16:58
알고리즘 + 자료구조
자의 눈금은 프랙탈과 비슷하다. 그렇다면, base case는 어떻게 될까? 가장 작은 눈금이 0 보다 커야한다. English Ruler 클래스를 만들어보자. 내부 작동원리는 프로그래머의 자율성을 따라야 하므로 생성자와 drawRuler() 만 노출하고 사용자에게 노출하기 싫은 메소드는 private 필드에 넣어야 한다. 멤버 변수 m_majorLength는 눈금 막대의 길이이고(말그대로 눈금 막대의 길이이다) m_numInches는 자 전체의 길이이다. class EnglishRuler{ public: EnglishRuler(size_t numInches, size_t majorLength) : m_numInches { numInches }, m_majorLength { majorLength }{ }..
Singly Linked List
2022. 10. 17. 17:29
알고리즘 + 자료구조
#include #include using namespace std; struct single_node{ int data; single_node* next; }; class single_lst{ public: using node = single_node; using node_ptr = node*; public: struct single_lst_iterator{ public: single_lst_iterator(node_ptr p) :ptr(p){} int& operator*(){ return ptr->data; } node_ptr get(){ return ptr; } single_lst_iterator& operator++(){ ptr = ptr->next; return *this; } single_ls..
순수 가우스 소거법 Naive Gaussian Elimination
2022. 7. 14. 11:57
알고리즘 + 자료구조
Naive Gaussian Elimination은 n개의 미지수를 가진 n개의 선형방정식을 풀기위해 고안된 것이다. 하지만 최적화가 되지 않은 버전이다. 3중 for문으로 구성되어 있기 때문에, chopping 혹은, Rounding 에러가 발생한다. 통상적인 행렬에는 소수점 7~9까지의 정확도를 보이지만, 방데르몽드 행렬 은 온전히 연산할 수 없다. #include #include template void PrintMatrix(std::vector& mat){ for(auto& row : mat){ for(auto& ele : row){ std::cout
호너씨와 조립제법과 수도미분
2022. 7. 10. 02:07
알고리즘 + 자료구조
어떤 값을 테일러 시리즈로 전개하고 전개식으로 계산하면, 그 끝에서는 원래 값과 일치할까? 하지만 극한에 이르러서는 차이가 생기고, 이 차이가 완전히 다른 결과를 낳는다면? 컴퓨터로 어떤 값을 계산할 때, double형의 데이터를 int형으로 형 변환될 때, 소수점 뒤에 값은 날아간다. 이때, 그 값은 chopping 된 값이다. 반대로, 사람이 chopping 할 수도 있는데, 유효숫자를 고려하지 않고, 그냥 편의대로 소수점 몇 번째 자리는 무시하는 것이다. 아무튼... 수치해석에서는 반올림할 때, 우리가 통상적으로 알고 있던 방식으로 하지 않고, 마지막 수가 5라면, 그 위의 자릿수가 짝수가 오도록 내림/올림 한다. 가령, 1.45를 반올림하면, 1.5이지만, 수치해석에서는 1.4로 한다. 만약에 1..