C++73 5. Dynamic Programming, Backtracking 5.1 Dynamic Programming 5.1-1 Memoization Note) 기존의 피보나치 수열 코드#pragma onceint fibo(int n){ if (1 == n) { return 1; } if (2 == n) { return 1; } return fibo(n - 1) + fibo(n - 2);} Note) 기존 피보나치 수열의 코드를 도식화하면 아래와 같음. 이 경우, n의 크기가 커지면 커질수록 재귀함수의 호출 횟수가 비약적으로 늘어남. 그래서 한 번 계산된 피보나치 값은 저장해둔다면, 꽤나 큰 효과를 얻을 수 있음. 즉, 재귀함수만 사용하는 것이 아닌 저장을 위한 메모리를 적절하게 함께 사용함. 이때 저장을 위한 메모리 사용 기법을 Me.. 2022. 12. 1. 4. Graph, DFS, BFS 4.1 Graph4.1-1 그래프 Def) 그래프(Graph) 개체 간의 연결 관계를 표현할 수 있는 비선형 자료구조 ex. 도시들 간의 연결, 지하철 노선도, SNS 친구 관계도 등 Note) 결국 트리는 그래프의 한 종류이다. 즉, 트리를 추상화하면 그래프가 됨. Note) 그래프의 구성 요소 - 그래프 G = (V, E) - 정점 V(Vertex, Node) 그래프를 구성하는 기본 단위. 노드. 데이터를 저장하거나 상태를 표현 - 엣지 E(Edge, Link) 정점과 정점을 잇는 선. 간선. 방향을 가질 수도 있음. 가중치(Weight)를 가질 수도 있음. Note) 그래프 관련 용어가중치(Weight)엣지에 .. 2022. 11. 22. 3. Tree, Binary Search Tree 3.1 Tree3.1-1 Binary Tree Note) 이진 트리 좀 더 자세한 내용은 여기에서 참고.#include #include using namespace std;templateclass STree{ struct SNode { public: SNode(const T& InData) : Data(InData) , LeftChild(nullptr) , RightChild(nullptr) { } public: T Data; std::unique_ptr LeftChild; std::unique_ptr RightChild; };public:.. 2022. 11. 4. 2. Sort, Search, Stack, Queue 2.1 Sort Note) 정렬의 종류 버블 정렬 / 퀵 정렬 / 선택 정렬 / 삽입 정렬 / 병합 정렬 / 힙 정렬 Note) 정렬의 차이 시간 복잡도 / 공간 복잡도 / 안정성 / 직렬 Vs. 병렬 Note) 정렬 알고리듬의 안정성 똑같은 키 값을 가진 데이터들의 순서가 바뀌지 않으면 안정적인 정렬. 바뀌면 불안정한 정렬. 안정성이 보장 안되어도 대부분은 문제가 되진 않음. 그래서 잘 모르고, 생각도 안하는 부분. Note) 안정성이 문제가 되는 경우 정렬 기준이 되는 정렬 키 값이 실제 데이터와 다를 경우. ex. std::map과 같은 자료구조의 정렬. ex. 구조체 혹은 클래스의 일부 멤버로만 정렬하는 경우. Note.. 2022. 10. 23. 이전 1 2 3 4 5 6 7 ··· 19 다음
