꿈꾸는공학도

C++ 알고리즘의 대표적인 자료구조인 Priority Queue의 근간이 되는 Heap 구조를 Complete Binary Tree형태로 표현하였다. Array가 아닌 Linked list로 표현하여서 Time complexity는 모두 enqueue / dequeue O( log N ) 이고, 코드를 구현하며 주의해야할 점은, heap property를 깨지 않기 위해 en/dequeue를 할 때마다 heapify-up/down을 시행해야 한다는 것이다. Enqueue는 그래서 일단 element를 Tree의 Last Node에 삽입하고, 그 친구를 Heap - up 하며 Dequeue는 일단 root와 last-node를 스위칭 한 다음에 last-node를 제거한다. 그리고 root자리에 있는 친구..

Algortihm의 대표적인 친구들인 MST, SSSP, APSP에 대한 이론 공부 Review를 빠르게 진행해보려고 한다.한 번씩 봤던 내용이니까 이론을 빨리 다루고, Code와 익숙해져보자. 각각의 경우 종류는 많지만, 대표적으로 쓰이는 몇 가지만 적어보려고 한다. 1. Minimum Spanning Tree한 Grpah에서 가장 낮은 cost로 전체 vertices를 도는 것을 계산하는 알고리즘이다. 그리고 여기서 Spanning Tree란, 어떤 Graph의 모든 Vertex를 다 포함하고 있는연결구조를 말한다.개중에 가장 Total Weight 이 작은 친구를 Minimum Spanning Tree라고 부르는 것이다. 이 MST 중 가장 유명한 알고리즘 2개를 다루겠다. 첫 번째, Prim's ..

Algorithm의 대명사인 Shortest Path와 관련된 실습이다.SSSP / APSP를 구현해보는 실습을 할 것이다. 대표적으로 FloydWarshall과 BellmanFord 알고리즘을 확인해보자. 실습자료는 위와 같다.#include #include #include #include // 아래 header는 내가 추가#include using namespace std;/*//////////////////////// Description ////////////////////////////There are n cities in a logistics network, numbered from 0 to n−1. The edges array represents the logistics routes bet..

이번 실습의 주제는 C++ Function Implementation이다.실습의 목표는 아래와 같다.  애증의 DP문제의 경우, 이해가 좀 어려운데 주석과 아래 예시를 보면 그래도 좀 느낌이 온다. 근데 문제는 이 느낌이 항상 답지를 보고 나서야 온다는 것-_-..문제 풀기 전부터 이 느낌이 머리에 딱 꽂치는 사람은 진짜 프로그래밍 고수다. 분명허다!! 나머지 문제는 Priority queue를 이용해 풀면 쉽다. 코드는 아래에 공유#include #include #include #include #include // 내가 추가using namespace std; // 내가 추가#include struct ListNode { int val; ListNod..

간단한 Tree 구조를 만들어서 Python 과 C 프로그래밍으로 Tree를 Traversal 하는 code를 짜봤다.첨부 파일을 통해서 실습을 진행할 수 있으며, Main 함수로 결과를 직접 확인해볼 수 있다. 요런 형태의 Tree로 테스트해봤는데, 마음대로 Tree구조를 바꿔서 Test 해봐도 된다.

C++을 이용해서 Type Casting 과 Exception Handling을 해보겠다. Type Casting이란 특정 Variable을 다른 data type으로 변화시키는 것이며 종류로는 1. C-style Casting2. Static cast3. Dynamic cast4. Const cast5. Reinterpret cast 이렇게 다섯가지 정도를 알아보자.Elec* elec = new pikachu();Fire* char = (Fire*)elec;// Compile error는 없지만 ERROR static_cast 으로 compile time에 casting을 걸어버려서 깔끔하다.  Exception Handling은 Try - Catch 구문이다.일단 try 안쪽에 있는 구문을 실행해보고..

이번엔, C++ 코딩을 하며 자주 마주하는 디버깅의 현장을 살펴보겠다. 관련자료는 아래와 같다.  용량이 크진 않으니 VS Code를 통해 C++ 코딩 작업을 할 경우, 잘 참고해서 하면 되겠다. 기본적으로 디버깅할땐 print문을 통해서 디버깅하는 방법이 있고, VS Code 상의 Debug Extention을 이용하는 방법이 있다. 전자는 직관적이지만, 귀찮고 후자는 효과적이지만 방법을 터득하기가 귀찮다. 일단 간단하게 Debugging 실습을 진행해보자. #include #include using namespace std;int main(){ list lst = {1,2,3,4,5}; // i want to practice using pop_back function in list! ..

금번 C++ 공부에선, Function Overloading 과 Templates 부분을 공부하고 관련 내용을 실습해보겠다.실습자료는 아래와 같다.  기본적으로 Function의 parameter에는 defulat 값을 넣을 수 있다.int divide( int a, int b = 2 ) { return a/b;} Function의 Overloading이란, Function들끼리 같은 이름을 Share하는데 Parameter type에 따라서 Return이 달라지는 것이다. 이 때, Return type만 가지고는 Function들 끼리 overload 할 수 없다. 다음은, Function Overload의 예시다. 보면, mySwap이라는 함수가 있는데, 이름이 다 같아도 input data의 typ..

C++과 관련된 시험에서 꼭 빠지지 않고 등장하는 것이 이 OOP 문제이다. OOP는 Class를 하나 만들어놓고, 그에 파생되는 객체를 가지고 노는 Programming이다. 이번에 해 볼 실습은, 2D Vector Class를 만들고, 해당 Class에 각 종 Operator를 Overroad 해본 뒤, OOP를 써서 Class 구현이 잘 되었는지 테스트 해보고, 2D Vector를 상속받은 Derived Class 3D Vector를 만들어 Class의 Inherit, Method의 Override를 잘 구현했는지 Test 해보겠다. 문제 풀이를 위한 Skeleton code는 아래와 같다.#include #include using namespace std;// Base class for 2D ve..

Algorithm Part의 기본적인 Data Structure인 Heap에 대해서 Implementation 연습을 시작해본다. Heap의 경우 Priority Queue라고도 생각하면 되고, Max/Min Heap으로 구분된다. 특징으론 Max Heap을 예로 들었을 때, Heap Data 구조에 입력되는 Data는 크기가 큰 순서(Max)대로 우선순위를 갖은 체 저장된다. 이 말은, Heap에서 특정 Data를 꺼낼 때(Deque) 가장 크기가 큰 녀석이 추출되는 것이다. 일반적으로 우리가 아는 queue구조에서 우선 순위만 선입선출이 아닌, Data 크기에 따라 결정된다는 것을 알고 있으면 된다. 따라서, 내부에 저장된 Data를 임의로 Search 할 수는 없지만 우리가 정한 Logic( Max..