꿈꾸는공학도

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 해봐도 된다.

def smallest_pos_int(arr:list[int]) -> int: s = set() # 1) 양의 정수만 s 에 저장 for num in arr: if num > 0: s.add(num) # 2) 1부터 n+1까지 차례대로 s에 존재하는지 확인 n = len(arr) # 정답은 잘 해봐야 n+1이다..................... for i in range(1, n+2): # n+1 까지 확인, range 범위를 위해 n+2 if i not in s: # 집합 membership check: 평균 O(1) return i # 위 for문에서 항상 return이 ..

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자리에 있는 친구..

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height-balanced binary search tree. Example 1:Input: head = [-10,-3,0,5,9]Output: [0,-3,9,-10,null,5]Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.Example ..

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