Directed Cycle Detection

in Study on C/C++, Algorithm

Cycle detection in a directed graph is a fundamental problem in graph theory with applications in deadlock detection, dependency resolution, and circuit analysis. The algorithm I’ve implemented uses a depth-first search (DFS) approach with a recursive traversal strategy to identify cycles in directed graphs.

Key Concepts

The algorithm relies on three key data structures:

  1. A visited flag for each vertex to track which vertices have been explored
  2. An on_stack array to track vertices currently in the DFS recursion stack
  3. An edge_to array to maintain the DFS tree structure for cycle reconstruction

Implementation

struct Vertex 
{
    Vertex(int v) { index = v; }

    int index = -1;
    bool visited = false;
    vector<Vertex*> out_neighboors;
}

class Graph
{
public:
    Graph(int num_vertices)
    {
        vertices.resize(num_vertices);
        for (int i = 0; i < num_vertices; i++)
            vertices[i] = new Vertex(i);
    }

    ~Graph() 
    {
        for (auto* v : vertices)
            delete v;
    }

    void addEdge(int v, int w)
    {
        verticies[v]->out_neighboors.push_back(vertices[w]);
    }

    void DetectCycle()
    {
        on_stack.resize(vertices.size(), false);
        cycle.clear();
        edge_to.resize(vertices.size(), nullptr);

        for (auto* v : vertices)
            v->visited = false;

        for (auto* v : vertices)
        {
            DetectCycleRecurr(v)
            if (!cycle.empty()) {
                cout << "cycle Detected" << endl;
            }
        }
    }

    void DetectCycleRecurr(Vertex* v)
    {
        v->visited = true;
        on_stack[v->index] = true;

        for(auto* w : v->out_neighboors)
        {
            if (!cycle.empty())
                return;
            else if (!w->visited) 
            {
                edge_to[w->index] = v;
                DetectCycleRecurr(w);
            }
            else if (on_stack[w->index])
            {
                Vertex* x = v;
                cycle.push_back(x);

                while(x->index != w->index) 
                {
                    cycle.push_back(x);
                    x = edge_to[x->index]
                }

                reverse(cycle.begin(), cycle.end())
                return;
            }
        }
    }

private:
    vector<Vertex*> vertices;
    vector<Vertex*> cycle;
    vector<bool> stack;
    vector<Vertex*> edge_to;
}

int main() 
{
    Graph g(3);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
}

Time Complexity

Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges. Each vertex and edge is processed exactly once in the worst case

The cycle reconstruction takes at most O(V) time

Space Complexity: O(V)

on_stack, edge_to, and recursion stack each require O(V) space. The cycle array stores at most V vertices

Bellman Ford Algorithm

in Study on C/C++, Algorithm

  • Reviewing what I studied, how this work will be explained as well.

The Bellman Ford Algorithm is a graph search algorithm that finds the shortest path from a source vertex to all other vertices in a weighted graph. It is similar to Dijkstra’s Algorithm but can handle graphs with negative weight edges. However, it can detect negative cycles, which are cycles whose total weight is negative.

Key Differences from Dijkstra’s Algorithm

  1. Negative Weight Edges: Bellman Ford can handle negative weight edges, whereas Dijkstra’s Algorithm assumes all edges have non-negative weights.
  2. Negative Cycles: Bellman Ford can detect negative cycles, which is not possible with Dijkstra’s Algorithm.

Algorithm Overview

  1. Initialization: Initialize the distance to the source vertex as 0 and all other vertices as infinity.
  2. Relaxation: Relax the edges repeatedly. For each edge, if the distance to the destination vertex can be reduced by going through the current vertex, update the distance.
  3. Negative Cycle Detection: After relaxing all edges V-1 times, check for negative cycles by attempting one more relaxation. If any distance can still be reduced, a negative cycle exists.

Time Complexity

The time complexity of the Bellman Ford Algorithm is O(V*E), where V is the number of vertices and E is the number of edges. This is because in the worst case, we relax all edges V-1 times.

Implementation

Here’s a corrected and complete implementation of the Bellman Ford Algorithm:

void Print(vector<double>& dist)
{
	for (int i = 0; i < dist.size(); i++)
		cout << setw(6) << dist[i];
	cout << endl;
}

struct Edge
{
	int v, w;
	double weight;
};

constexpr double kInf = numeric_limits<double>::infinity();
vector<double> dist(V, kInf);
for (int v = 1; v < V; v++)
{
	for (auto e : edges)
	{
		if (dist[e.w] > dist[e.v] + e.weight) {
			dist[e.w] = dist[e.v] + e.weight;
			prev[e.w] = e.v;
		}
	}
	Print(dist);
}

Then how do you think about getting the negative edges!? It’s basically same logic! if the distance the next edge is greater than the current(whole) distance, then we can conclude that there will be negative edge. Normally, the dist arrays two indices where negative values are very likely that it’s negative cycle.

Resource

Rod Cutting Problem

in Study on C/C++, Algorithm

  • Reviewing what I studied, how this work will be explained as well.

Rod Cutting Problem is a problem that we have a rod of length n and we want to cut the rod into n pieces, and we want to maximize the profit. For example, let’s look at the table below. If I have a rod of length 4, then we have 4 ways to cut the rod. Then we calculate the profit for each case

  1. Cut the rod into 1, 1, 1, 1 => max profit = 1 + 1 + 1 + 1 = 4
  2. Cut the rod into 2, 2 => max profit = 5 + 5 = 10
  3. Cut the rod into 3, 1 or 1, 3 => max profit = 8 + 1 = 9
  4. Length 4 rod itself => max profit = 9

the maximum profit we can get is 10.

Length:                     0  1  2  3  4   5   6   7   8   9  10
vector<int> price_table = { 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };

So, let solve this in naive recursive way

int RecurCutRod(const vector<int>& prices, int length)
{
	if (length == 0)
		return 0; // return length* prices[0];

	int max_price = numeric_limits<int>::min();
	for (int i = 1; i <= length; i++)
	{
		max_price = std::max(max_price, prices[i] + RecurCutRod(prices, length - i));
	}

	return max_price;
}

Then, let’s do top-down, top-down basically needs a cache, so that repetitive calculation must be excluded, and used the data retrieved from memo.

// initialize 
vector<int> memo(length + 1);
memo[0] = 0;

// function
int MemoizedCutRodHelper(const vector<int>& prices, int length, vector<int>& memo)
{
	if (memo[length] >= 0)
		return memo[length];

    int max_prices;
    if (length == 0){
        max_price = 0
    }
    else {
        max_price = std::max(max_price, MemoizedCutRodHelper(prices, length - i, memo))    
    }
	
    for (auto& t : memo) cout << setw(3) << t; cout << endl;
	return memo[length];
}

Then, let’s do bottom-up, Bottom-up Apprach is called tabulation, so we need kinda like table. I would say bottom up approch can be more familier if you are good at for-loop! (jk)

int BottomUpCutRod(const vector<int>& prices, int length)
{
	vector<int> table(length + 1, -1); -1로 초기화
	table[0] = 0; // length* prices[0];

	for (int j = 1; j <= length; j++)
	{
		int max_price = numeric_limits<int>::min();
		for (int i = 1; i <= j; i++) {
			max_price = std::max(max_price, prices[i] + table[j - 1]);
		}
		for (auto& t : table) cout << setw(3) << t; cout << endl;
		table[j] = max_price;
	}

	return table[length];
}

But when we think about the time complexity. it would be depending on the O (length). Of course, we do have space complexity which is about O(length + 1).

Resource

Index Min Priority Queue

in Study on C/C++, Algorithm

  • Reviewing what I studied, how this work will be explained as well.

Index Min Priority Queue

We’ve covered binary heap, priority queue and so forth, but one of the useful priority queue we’re going to look at is Index Min Priority Queue. This is a traditional priority queue variant which on top of the regular PQ operations supports quick updates and deletions of key-value pairs (for example, key can be double type, and value is int type).

Problems: Hospital Example

Suppose we have people who need to be taken care of, and it really depends on their conditions. For example, Mary is in labor, which has a higher priority than the others. Here is the issue: Richard went to a different hospital, and doesn’t really need to be taken care of anymore, and Nadia’s stomach pain + vomiting turned out to be an infectious disease, so she moved to high priority. This means our priority queue needs to be updated.

In the hospital example, we saw that it’s crucial to be able to dynamically update the priority (values) of certain people (keys). The Indexed Priority Queue (IPQ) data structure lets us do this efficiently. The first step in using an IPQ is to assign index values to all the keys, forming a bidirectional mapping.

Alt text

Create a bidriectional mapping between your N keys and the domain [0, N) using a bidrectional hashtable.

Key             |   Key Index
"Marry"        <->    0
"Akarsh"       <->    1
"James"        <->    2
"Naida"        <->    3
"Richard"      <->    4
"Leah"         <->    5

There are several operations in IPQ as following and their time complexity: | Operations | Time Complexity | |——|————| | Empty() | O(1) | | Contains(key) | O(1) | | Size() | O(1) | | Insert() | O(log N) | | MinIndex() - Peek | O(1) | | MinKey() - Peek| O(1) | | DelMin(key) | O(log N) | | KeyOf() & ValueOf(key) | O(1) | | ChangeKey() | O(log N) | | DecreaseKey(key, value) & update | O(log N) | | IncreaseKey(key, value) & update | O(log N) | | Delete() & Update() | O(log N) | | Exch(key, key) | O(1) | | Greater() | O(1) | | Swim(value) | O(log N) | | Sink(value) | O(log N) |

Then why do I metion, it’s bidrectional mapping? Given the key value, we should be able to find the where this node is positioned in heap(position mapping). Also, Given the index value in value table, we should also be able to find the key value.

To show what is bidrectional, look at the image below: Alt text

Implementation

template<typename Key>
class IndexMinPQ
{
public:
    IndexMinPQ(int cap)
    {
        capacity = cap;
        size = 0;
        keys.resize(capacity + 1);
        pq.resize(capacity + 1);
        inverseMap.resize(capacity + 1, -1) // InverseMap
    }

    bool Empty()
    {
        return size == 0;
    }

    bool Contains(int i)
    {
        return inverseMap[i] != -1;
    }

    int Size() { return size; }

    void Insert(int i, Key key) 
    {
        size += 1;
        inverseMap[i] = size;
        pq[size] = i;
        keys[i] = key;
        Swim(size);
    }

    int MinIndex()
    {
        return pq[1];
    }

    Key MinKey()
    {
        return keys[pq[1]];
    }

    int DelMin()
    {
        int m = pq[1];
        Exch(1, size--);
        Sink(1);
        inverseMap[m] = -1;
        keys[m] = 0.0;
        pq[size + 1] = -1;
        return m;
    }

    Key keyOf(int i)
    {
        return keys[i];
    }

    void ChangeKey(int i, Key key)
    {
        if (!Contains(i)) {
        	throw::std::invalid_argument("index does not exist");
        }

        if (key < keys[i]) {
        	keys[i] = key;
        	Swim(qp[i]);
        }
        else if (key > keys[i]) {
        	keys[i] = key;
        	Sink(qp[i]);
        }
    }

    void DecreaseKey(int i, Key key)
    {
        keys[i] = key;
        Swim(qp[i]);
    }

    void IncreaseKey(int i, Key key)
    {
        keys[i] = key;
        Swim(inverseMap[i]);
    }

    void Delete(int i)
    {
        int index = inverseMap[i];
        Exch(index, size--);
        Swim(index);
        Sink(index);
        keys[i] = 0.0;
        inverseMap[i] = -1;
    }

    void Exch(int i, int j) // swap
    {
        int swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
        inverseMap[pq[i]] = i;
        inverseMap[pq[j]] = j;
    }

    bool Greater(int i, int j)
    {
        return keys[pq[i]] > keys[pq[j]];
    }

    void Swim(int k)
    {
        while(k > 1 && Greater(pq[k/2], pq[k])){
            Exch(k / 2, k);
            k /= 2;
        }
    }

    void Sink(int k)
    {
        while(2 * k <= size)
        {
            int j = 2 * k;
            if (j < size && Greater(j, j+1))
                j++;
            if (!Greater(k, j)) break;
            Exch(k, j);
            k = j;
        }
    }

private:
    int size = 0;
    int capacity = 0;
    vector<int> pq;
    vector<int> inverseMap;
    vector<Key> keys;
}

The most important operation would be Swim and Sink.

The Swim operation works as follows:

  1. Start with the element at index k that needs to be “swum up” the heap
  2. Loop until either:
    • We reach the root of the heap (k > 1)
    • The parent is not greater than the current element (!Greater(pq[k/2], pq[k]))
  3. In each iteration:
    • Compare the current element with its parent (located at index k/2)
    • If the parent is greater than the current element (in a min heap), exchange them (Exch(k/2, k))
    • Update k to the parent’s position (k /= 2) to continue moving up the heap

Sink Operation needs to go down the heap, which means we need to check both children. Here’s the complete process:

  1. Loop until we reach the bottom of the tree (while 2*k <= size)
  2. Calculate the index of the left child (j = 2*k)
  3. Compare left and right children (if j < size && Greater(j, j+1))
  4. If the right child exists (j < size) and is smaller than the left child (Greater(j, j+1)), select the right child by incrementing j
  5. This ensures we select the smaller of the two children in a min heap
  6. Check if the current node is already smaller than the selected child (!Greater(k, j))
  7. If so, the heap property is satisfied, so break out of the loop
  8. If not, exchange the current node with the selected child (Exch(k, j))
  9. Update k to the position of the child (k = j) and continue the process

Resource

Dynamic Programming

in Study on C/C++, Algorithm

  • Reviewing what I studied, how this work will be explained as well.

Dynamic Programming is a method for solving a complex problem by breaking it down into simpler sub-problems. It’s one of a method for solving optimization problems. There are two components of Dynamic Programming:

  1. Optimal Substructure
  2. Overlapping Subproblems

Optimal Substructure

Optimal Substructure means that the optimal solution to a problem can be constructed from optimal solutions to its sub-problems. Basically, if you break it down to smaller array from big array, and you have an optimal solution to smaller array, you can use it to solve the big array. But when you think about this Optimal Substructure, it’s similar to Divide and Conquer. However there are differences. For example, in Divide and Conquer, we divide the big array into smaller array (divide), calculate, combine, and merge. But we try to find the set of sub-problems that have optimal solutions, and use it to solve the big problem. Also, we can compared this with Greedy Algorithm. Within all the solution that we get from optimal substructure (which is the set of sub-problems), we choose the best solution is the greedy algorithm.

This is normally done by using recursion.

Overlapping Subproblems

When we solve the problem using recursion, we solve the same sub-problem multiple times. This is called Overlapping Subproblems. For example, in the Fibonacci sequence, we can conclude in the following way:

             [ 1 ] n = 1
fib =        [ 1 ] n = 2 
             [ fib(n-1) + fib(n-1) ], n = 3, 4, 5, ...

Then, we can simply draw the tree of the sub-problems (draw yourself!). Then we can see that, fib(4) = fib(3) + fib(2) is calculated twice. This is called Overlapping Subproblems. Then, we can use the same sub-problem as cache to solve the problem.

Two types of Dynamic Programming

  • Top-Down (Memoization)
  • Bottom-Up (Tabulation)

Top-Down (Memoization)

  • Solve the sub-problem using recursing
  • Memoize the overlapping sub-problems
  • Reuse the memoized sub-problems to solve the big problem

Bottom-Up (Tabulation)

  • Solve the sub-problem using iteration
  • Using the tabulation, we can store the result of the sub-problem in a table

When to use Dynamic Programming?

  • State Transition
  • Simple Condition -> Fibonacci, Tiling, Digit DP(if digit condition is met, count the number of cases)
  • Array -> Kadane’s algorithm (sub-array sum), Kapsack Problem, Matrix(DAG, #of Path, Path Cost), String(LIS, LCS, Edit Distance), Max Profit (Buy and Sell Stock), Rod Cutting, Matrix Chain Multiplication
  • Tree -> DAG, DAG Shortest Path, DAG Longest Path, DAG Topological Sort, # of BST.
  • Optimization Problem -> Convex Hull, Matrix Multiplication Order

Dijkstra Algorithm

in Study on C/C++, Algorithm

  • Reviewing what I studied, how this work will be explained as well.

Dijkstra Algorithm is a shortest path algorithm that finds the shortest path from a starting node to all other nodes in a graph. Instead of using BFS, it uses priority queue to find the shortest path.

Constraints:

  • No negative weight edges
  • No negative cycles

This is not dependent on the how many nodes we are passing through, but the weight of the edges. (distance in this case.)

Let’s see the steps of the algorithm.

  1. Initialize the distance of the starting node to 0, and the rest of the nodes to infinity.
  2. Push the starting node to the priority queue & Pop the starting node from the priority queue.
  3. Update the distance of the adjacent nodes (setting infinity to the edge weight), then push them to the priority queue.
  4. Then select the node with the smallest distance from the priority queue and repeat the process.

Code is as follows.

#include <iostream>
#include <list>
#include <vector>
#include <limits>
#include <queue>
#include <iomanip>

using namespace std;

// Sedgewick p. 642
class DirectedEdge
{
public:
	int v;         // edge tail
	int w;         // edge head
	double weight; // edge weight

	DirectedEdge(int v, int w, double weight)
	{
		this->v = v;
		this->w = w;
		this->weight = weight;
	}

	double Weight() { return weight; }
	int From() { return v; }
	int To() { return w; }
};

class EdgeWeightedDigraph
{
public:
	int num_vertices;
	int num_edges;
	vector<vector<DirectedEdge>> adj;

	EdgeWeightedDigraph(int num_vertices)
	{
		this->num_vertices = num_vertices;
		this->num_edges = 0;
		adj.resize(this->num_vertices);
	}

	void AddEdge(DirectedEdge e)
	{
		adj[e.From()].push_back(e);
		num_edges += 1;
	}

	vector<DirectedEdge>& Adj(int v) { return adj[v]; }
};

class DijkstraShortestPaths
{
public:
	DijkstraShortestPaths(EdgeWeightedDigraph& g, int s)
		:
		prev(g.num_vertices, -1),
		dist(g.num_vertices, numeric_limits<double>::infinity()),
		visited(g.num_vertices, false)
	{
		dist[s] = 0.0; // distance for self is 0

		pq.push(pair<double, int>{ 0.0, s });

		PrintIndex(dist);
		PrintDist(dist);

		while (!pq.empty())
		{
			int v = pq.top().second;
			pq.pop();

			if (visited[v]) continue;
			visited[v] = true;

			Relax(g, v);
		}

		PrintPaths();
	}

	void Relax(EdgeWeightedDigraph& g, int v)
	{
		// Get the edge of the v
		for (DirectedEdge& e : g.Adj(v)) {
			int w = e.To();
			
			if (visited[w]) continue;

			// update
			double new_dist = dist[v] + e.Weight();
			if (dist[w] > new_dist) {
				dist[w] = new_dist;

				prev[w] = e.From();
				pq.push({ dist[w], w});
			}
		}
		PrintDist(dist);
	}

	void PrintIndex(vector<double>& dist)
	{
		cout << "Vertex: ";
		for (int i = 0; i < dist.size(); i++)
			cout << setw(6) << i;
		cout << endl;
	}

	void PrintDist(vector<double>& dist)
	{
		cout << "Dist  : ";
		for (int i = 0; i < dist.size(); i++)
			cout << setw(6) << dist[i];
		cout << endl;
	}

	void PrintPaths()
	{
		for (int i = 0; i < prev.size(); i++) {
			deque<int> path;
			path.push_front(i);
			int v = prev[i];
			while (v != -1) {
				path.push_front(v);
				v = prev[v];
			}

			for (auto v : path) {
				cout << v;
				if (v != path.back())
					cout << "->";
			}
			cout << endl;
		}
	}

private:
	vector<int> prev;     
	vector<double> dist;
	vector<bool> visited;

	priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
};

The update function is shown below, as new_distance is smaller than the current distance, we update the distance and push the node to the priority queue.

double new_dist = dist[v] + e.Weight();
	if (dist[w] > new_dist) {
		dist[w] = new_dist;

		prev[w] = e.From();
		pq.push({ dist[w], w});
}

Time Complexity

  • If we use just a simple array, you can get O(V^2), but if you use priority queue, you can get (V+E) * LogV because priority queue insertion / deletion (Log V), then this happens for each Vertex => V * Log V. Edge Iteration => O(E) Then for relaxation, we update the distance to add that edge would be E * LogV. So we can conclude that it is (V+E) LogV in average. So, sum all it up (O(ELogV + E + VLogV)) => O(V+E logV).

Resource

Binary Heap

in Study on C/C++, Algorithm

  • Reviewing what I studied, how this work will be explained as well.

Binary Heap is a complete binary tree that satisfies the heap property.

Heap Property

  • Max-Heap : Parent node is greater than or equal to child node.
  • Min-Heap : Parent node is less than or equal to child node.

Heap Constraints

  1. Access the max element instantaneously (that’s why the max element in in the root) -> Max HeapMin Heap
  2. which extends to the idea that, the parent node should be bigger than the children node.
  3. Swap (If we are to insert the last element into last tree level, then we need to compare the value, and update the tree)

Heap Operations

  • Search (O(N))
  • Deletion (Log N)
  • Peek (O(1))
  • Insertion (Log N) -> Worst Case / But Best Case is O(1)
  • Heapify (O(N))

Heapify

If you take a look at the heapify function, it is a function that takes an array, and makes it a heap. So this approximation can be done as follows.

In the logic, we don’t calculate the leaf nodes, we only did siftDown from the first non-leaf node (which is second last node). Maximum number of nodes in each level is floor(n_total / 2^h+1). (h is the height of the tree). Then we can calculate this… 1 * n/4 + 2 * n/8 + 3 * n/16 + … + h * n/2^(h+1).. then n/4 {1 + 2/4 + 3/8 + 4/16 + … + h/2^(h-1)}.. then n/4 {1 + 1/2 + 1/4 + 1/8 + … + 1/2^(h-1)}.. then n/4 {1 / (1 - 1/2)^2} = n. (1/(1-x)^2) = sigma(n *x^(n-1)). This is why it is O(N).

Heap Implementation

struct MaxHeap {
    vector<int> heap;

    MaxHeap() {
        heap.resize(1); // heap 은 무조건 1 부터 시작, 안보이는 0 이 존재
    }

    // ---- priority queue
    void push(int x) {
        int index = int(heap.size());
        heap.push_back(x);
        siftUp(index);
    }

    void siftUp(int index) {
        for (int i = index; i > 1 && heap[i / 2] < heap[i]; i /= 2)  // O(logN)
            swap(heap[i / 2], heap[i]);
    }

    int top() const {
        return heap[1];    
    }

    bool pop() {
        int N = int(heap.size());
        if (N <= 1)
            return false;
        swap(heap[1], heap[N - 1]);
        heap.pop_back();
        siftDown(1);
        return true;
    }

    void siftDown(int index) {
        int N = int(heap.size());
        cout << N << endl;
        for (int i = index, j = index * 2; j < N; i = j, j *= 2) {
            if (j + 1 < N && heap[j] < heap[j + 1])
                j++;
            if (heap[i] >= heap[j])
                break;
            swap(heap[i], heap[j]);
        }
    }

    void heapify(const int arr[], int size) {
        heap.resize(1);
        heap.insert(heap.end(), arr, arr + size);
        
        for (int i = size / 2; i >= 1; i--)
            siftDown(i);
    }
};

The interesting fact about this heap.

Let’s mark that the parent heap is denoted as i, then child on left is i * 2, and right is i * 2 + 1. If you actually draw the tree, parent node is 0001, then left child is 0010, and right child is 0011. then parent node is 0100, left child is 0101, and right child is 0110. then parent node is 0111, left child is 1000, and right child is 1001. then parent node is 1010, left child is 1011, and right child is 1100.

This is interesting! Why? from the parent node, the resulting of left child is shifting left by 1, and right child is shifting left by 1 and adding 1. Then we can back track how many parent nodes are from the child node. For example, if node 9 is 1001, remove MSB, 001. We can see that 0(left)->0(left)->1(right) in that direction, so we have three parent nodes from child node 9.

In the next post, I will show you the leet code problem that uses this heap property.

LeetCode - Diet Plan Performance [Sliding Windows - Easy] - 1176

in Study on C/C++, Algorithm

How to Solve

int dietPlanPerformance(vector<int>& calories, int k, int lower, int upper) {
    int points = 0;
    int current_sum = 0;

    for (int i = 0; i < calories.size(); i++) {
        current_sum += calories[i]; // 일단 현재의 Current Sum 을 구한다.

        if (i - k >= 0) {                           // 만약 윈도우 사이즈를 넘어가면, 왼쪽 원소를 빼준다. 즉 이말은 즉슨, k = 1 이면 전에 있던 0 을 빼줘, 1 만 보게끔 하는것이다. 
            current_sum -= calories[i - k]; 
        }

        if (i - k + 1 >= 0) {                      // 윈도우의 시작점 Index 다. k = 2 라고 하면, i - k + 1 = 0 이, 0 부터 만들어진다는 뜻이다. 
            if (current_sum < lower) {
                points--;
            } else if (current_sum > upper) {
                points++;
            }
        }
    }
}

Review

하… Easy 라고 했는데 오랜만에 하니까, Sliding Window 문제가 생각이 안나서 좀 헤맸다. Sliding Windows 라는건 Array[i] 가 있다고 하면, w size 만큼 윈도우를 옮겨가면서 처리하는 문제를 말한다.

LeetCode 222. Count Complete Tree Nodes [Easy]

in Study on C/C++, Algorithm

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

You can use the priority queue to solve this problem or use the property of the complete binary tree.

class Solution {
public:
    int getHeight(TreeNode* node) {
        int height = 0;
        TreeNode* curr = node;
        while (curr) {
            height++;
            curr = curr->left;
        }
        return height;
    }

    bool exist(TreeNode* root, int index){
        int h = 0;
        for (int i = index; i > 1; i >>= 1)
            h++;
        
        TreeNode* curr = root;
        while(curr) {
            if (h == 0)
                return true;
            if (index & (1 << --h))
                curr = curr->right;
            else 
                curr = curr->left;
        }
        return false;
    }

    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;

        int h = getHeight(root);
        int lo = 1 << (h - 1); // 8
        int hi = (1 << h) - 1;
        while(lo <= hi){
            int mid = lo + (hi - lo)/2;
            if (!exist(root, mid))
                hi = mid -1;
            else
                lo = mid + 1;
        }
        return hi;
    }
};

Class Default Object (CDO)

in Study on Unreal engine
  • Unreal Object 가 만들어지기 위해서는, 실제 컴파일 전에 Unreal Header Tool 에 헤더 파일 분석하는 과정에서 선행이 되며, 이 과정이 완료되면, Intermediate Folder 에 Unreal Object 정보를 담음 Meta File 이 생성 된다.
  • 이 Meta 정보는 Unreal Engine이 지정한 UClass 라는, 특별한 클래스를 통해서 보관됩니다.
  • UClass 에는 Unreal Object 에 대한 클래스 계층 구조 정보와 멤버 변수, 함수에 대한 정보를 모두 기록하고 있습니다.
  • 하지만 단순히 검색하는 것에서 더 나아가, Run Time 에서 특정 클래스를 검색해 형(Type) 을 알아내 인스턴스의 멤버 변수 값을 변경하거나 특정 인스턴스의 member function 호출하는것이 가능하다.

Reflection

  • Java / C# 과 같은 경우 Reflection 이라는 이름으로 제공
  • Compile 단계에서 Unreal Object 마다 UCLass 가 생성된다면, 실행 초기의 Run Time 과정에서는 Unreal Object 마다 Class 의 정보와 함께 Unreal Object 의 Instance 가 생성됩니다.
  • 이 특별한 Instance 는 Unreal Object 의 기본 세팅을 지정하는데 사용되는데, 이를 클래스 기본 객체 (Class Default Object: CDO) 라고 한다.
  • Unreal Engine 에서 CDO 를 만드는 이유는 Unreal Object 를 생성할 떄마다 매번 초기화를 시키지 않고, 기본 인스턴스를 미리 만들어 놓고 복제하는 방식으로 메커니즘이 구성되어 있기 때문이다.
  • 예를 들어서 복잡한 기능을 수행하는 캐릭터를 담당하고, 기능이 커진다고 했을때 굉장히 큰덩어리로 될수 있다. 이럴때 100 개의 instance 를 만든다고 가정하면, 캐릭터를 하나씩 처음부터 생성 하고, 초기화 시키는 방법보다, 미리 큰 기본 객체 덩어리를 복제하고, 속성 값만 변경하는게 더 효율적이기 때문이다.
  • 정리하자면, 아래와 같이 하나의 Unreal Object 가 초기화 될 때에는 두개의 Instance 가 항상 생성 됩니다.

alt text

  • 이 생성자 클래스는 Instance 를 초기화 해 CDO 를 제작하기 위해서 사용되고, 초기화에서만 실행되고, 실제 게임 플레이에서는 생성자 코드를 사용할 일이 없다.
  • Unreal Engine 에서 게임 플레이에서 사용할 초기화 함수는 생성자 대신 Init() 이나 혹은 BeginPlay() 함수를 제공 alt text

Resource

Pagination