Algorithm

🔒 문제 💭 생각의 흐름 배열은 선형 자료구조로 전체 길이 / 2를 기준으로 좌우 대칭을 이루고있다. 맨 첫자리 끝자리 첫자리 + 1 끝자리 - 1 index를 사용하여 대칭을 이루는 문자열을 Swapping 해주기만 하면 된다. 🔑 풀이 (C++) string reverseWord(string str){ char characterArray[str.length() + 1]; const int length = sizeof(characterArray); strncpy(characterArray, str.c_str(), length); // after strncpy null-terminate character should not be created characterArray[length] = '\0'; for..

When to use? 임의의 한 정점에서 모든 정점으로의 최단 경로 및 비용을 구할 때. 특정 출발 지점에서 도착지점까지의 최단 경로 및 비용을 구할 때 # shortest path # greedy Algorithm 1. Create shortestPath Set, distance array table || (visited array) 2. initialize all vertices with make start node weight '0', reamin node weight 'INF' 3. set || priorityQueue != empty (a) Pick minimum vertex (b) check all adjacent edge weight compare distance [adjacentVerte..

구현 방식 2가지 1. Priority Queue. // O(n log n) for(int i = 1; i O(n * log n) ∴ O (n * log n) BuildHeap Analysis When to use? k Largest(Smallest) elements in array Implementation (C++) // make Max Heap void PriorityQueue::shiftDown(int index) { int maxIndex = index; do { index = maxIndex; const int leftChildIndex = getLeftChildIndex(index); const int rightChildIndex = getRightChildIndex(index); if (l..

Complete Binaray Tree every level, all nodes are filled ordering left to right except possibly last node When to use? -> Implements Prirority Queue! * Full Binrary Tree : every node has two children ADT of Prirority Queue implements using MAX Heap array -> parent index : i / 2 left child index : i * 2 right child index : i * 2 + 1 maxSize: Capacity size: The number of current elements which heap..

When to use get MST of undirected & weighted Graph Idea maintain two sets of vertices (1: MST, 2: not visited) find cut vertex minimum weight in each loop until all vertices be included in MST 📝 cut vertex: connect vertex which connects two disjoint subsets Algorithm (1) Create key-value table (vertex - weight) , empty MST Set (2) initialize first value of key as '0' to visit first, remain key a..

🔒 문제 💭 생각의 흐름 MST (Minimum Spanning Tree) + Undirected Graph => 2가지 방법! Kruskcal Prim✔️ mstSet: 방문된 MST 원소의 집합 not visited Set: 아직 방문하지 않은 노드 번호 - 비용 집합 find minimum cut vertex : mstSet과 not visited Set을 최소 비용으로 연결하는 노드 찾기 mstSet -> 어차피 weight의 총합을 구하는 것이므로 방문 순서를 저장할 필요가 없겠다 -> unorderd_set not visited Set -> 배열로 생성시 따로 visited Boolean 배열이 필요하므로 map 자료구조 사용 ⭐ find minimum cut vertex -> not vist..