Category: Javascript Coding Test

Problem Description

We are trying to raise donations to help the less fortunate. Each donor simply needs to input the amount they can donate. The amount entered by the donor is stored in a list, and a function to calculate the total amount donated is to be implemented. Additionally, the maximum amount a donor can donate is limited to 100,000 won.

Input

The number of donors n (1 <= n <= 1000) and each donor’s donation amount are provided.

Output

Print the total sum of all donations.

Example Input

    5
    10000
    25000
    50000
    120000
    30000
    

Example Output

    95000
    

Approach to Problem Solving

This problem requires a simple algorithm to process the given input values and calculate the total. We can approach it by storing the donation amounts in an array and summing all elements in the array to derive the result. The following are the steps to solve this problem.

Step 1: Taking Input

To take input, we will receive the number of donors (n) and each donor’s donation amount from the user. These input values will be stored in an array. Donations exceeding 100,000 won will be ignored, so a logic to check this is needed.

Step 2: Storing Donation Amounts in an Array

Only valid donation amounts will be added to the array, and a variable will be set to calculate the total donation amount.

Step 3: Calculating and Printing the Total

Calculate the sum of donation amounts stored in the array and print the result.

JavaScript Code Implementation

Now let’s implement the entire logic in JavaScript code. Below is the code based on the logic described above:

function calculateDonation() {
    const n = parseInt(prompt("Please enter the number of donors: "));
    let donations = [];
    let totalDonation = 0;

    for (let i = 0; i < n; i++) {
        let donation = parseInt(prompt(`Please enter the ${i + 1}th donation amount: `));

        // Add to the array only if the donation amount is 100,000 won or less
        if (donation <= 100000) {
            donations.push(donation);
            totalDonation += donation;
        } else {
            console.log("The donation amount must be 100,000 won or less.");
        }
    }

    console.log(`Total donations: ${totalDonation} won`);
}

calculateDonation();
    

Code Explanation

Analyzing the code, the calculateDonation function is defined, where the user first inputs the number of donors. Then, using a for loop, each donation amount is inputted, and a conditional statement adds it to the array only if it is 100,000 won or less, calculating the sum at the same time. If the donation amount exceeds this, a warning message is printed. Finally, the total donation amount is displayed.

Conclusion

In this tutorial, we implemented a simple program to manage donation data using JavaScript. This code allows easy calculation of total donations and includes logic to check the number of donors and the validity of donation amounts. Through this experience of solving simple problems, we can gain confidence in solving algorithmic challenges.

Additional Practice Problems

To further practice problem solving, try tackling the following additional problems:

1. Add a feature to sort the donation amounts in ascending order.
2. Calculate the average donation amount of the donors.
3. Implement a feature to automatically add an additional 10% donation when the number of donors exceeds 10.

Final Remarks

Programming practice requires a deep understanding that goes beyond just solving problems. Based on the experiences and knowledge gained through this problem-solving process, aim to create your own programs or tackle more complex algorithmic challenges with confidence.

Author: [Your Name]

Written on: [Date]

Table of Contents

1. 1. Introduction
2. 2. Problem Description
3. 3. Understanding the Floyd-Warshall Algorithm
4. 4. JavaScript Implementation
5. 5. Time Complexity
6. 6. Conclusion

1. Introduction

Algorithm problems are frequently presented in coding tests, and the ability to understand and implement various algorithms is important. This course will cover the Floyd-Warshall algorithm and teach how to implement it in JavaScript. The Floyd-Warshall algorithm is useful for finding the shortest paths between all pairs of vertices in a graph, particularly suited for large graphs.

2. Problem Description

Problem: Write an algorithm to find the shortest paths between all vertices in a given directed graph. The graph consists of edges with weights. If there is no path between two vertices, the value of the shortest path is handled as infinity.

Input:
- Number of vertices N (1 ≤ N ≤ 100)
- Number of edges M (1 ≤ M ≤ 10000)
- Edge information of M edges (A, B, C): weight C from A to B

Output:
- Print an N x N matrix representing the lengths of the shortest paths between the destination vertices.
        

3. Understanding the Floyd-Warshall Algorithm

The Floyd-Warshall algorithm uses dynamic programming techniques to compute the shortest paths between all pairs. The algorithm includes the following steps:

1. Initialize distance values between all pairs of vertices (i, j). Set weights for directly connected vertices and infinity (INFINITY) for non-connected ones.
2. Set each vertex as an intermediate vertex and check the shortest path from i to j. Using k as the intermediate vertex, check if the path i -> k -> j is shorter than the direct path i -> j.
3. Repeat this process for all vertices.

By doing this, we can ultimately find the shortest paths between all pairs of vertices.

function floydWarshall(graph) {
  const dist = JSON.parse(JSON.stringify(graph)); // Copy the graph to initialize the distance matrix

  const n = graph.length; // Number of vertices
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][j] > dist[i][k] + dist[k][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
  return dist;
}
        

4. JavaScript Implementation

Now let’s implement the Floyd-Warshall algorithm in JavaScript. First, we will handle input, initialize the graph, and then write a function to calculate the shortest paths:

function initializeGraph(N, edges) {
  const graph = Array.from({ length: N }, () => Array(N).fill(Infinity));
  for (let i = 0; i < N; i++) {
    graph[i][i] = 0; // The case for going to itself is 0
  }

  edges.forEach(([A, B, C]) => {
    graph[A][B] = Math.min(graph[A][B], C); // Update to the minimum weight if there are multiple edges
  });

  return graph;
}

// Main function to solve the problem
function solve(N, M, edges) {
  const graph = initializeGraph(N, edges);
  const shortestPaths = floydWarshall(graph);

  console.log("Shortest Path Matrix:");
  shortestPaths.forEach(row => console.log(row.join(" ")));
}
        

5. Time Complexity

The time complexity of the Floyd-Warshall algorithm is O(N^3). This is because a triple loop is used to check each pair of vertices when N is the number of vertices. Therefore, it can be efficiently used when the number of vertices is reasonably small (100 or less), but for graphs with hundreds of vertices, other algorithms should be considered.

6. Conclusion

In this course, we explored the theory of the Floyd-Warshall algorithm and how to implement it in JavaScript. By understanding the algorithm and practicing the code implementation, we can enhance our problem-solving skills in coding tests. Next time, we will cover even more diverse algorithms.

Coding tests are a great way to evaluate programming skills. Today, we will look at how to solve the Minimum Spanning Tree (MST) problem.
This problem is applicable in various fields, especially in problems related to computer networks.
There are several algorithms to construct a minimum spanning tree, but particularly Kruskal’s Algorithm and Prim’s Algorithm are widely used.

Problem Description

Let’s solve the problem of finding a minimum spanning tree given the edges that represent the graph below.
Each edge is assigned a weight, and we need to find a connected graph where the total weight is minimized.

Problem Definition

    Input:
        [(1, 2, 4), (1, 3, 1), (2, 3, 2), (2, 4, 5), (3, 4, 8), (1, 4, 3)]
    Output:
        List of edges in the minimum spanning tree: [(1, 3, 1), (2, 3, 2), (1, 4, 3), (2, 4, 5)]
        Sum of minimum weights: 11

Problem Solving Process

Step 1: Understanding Graph Data Structure

A graph consists of vertices (nodes) and edges.
Here, edges are provided in the form of tuples as `(start vertex, end vertex, weight)`.
We need to construct the graph using this data.

Step 2: Sorting Edges

Kruskal’s Algorithm first sorts the edges based on their weights.
We sort the given list of edges in ascending order to be able to select the edges with the minimum weights.

Step 3: Cycle Detection Using Union-Find Structure

To check whether a cycle occurs when adding edges, we use the Union-Find data structure.
This data structure has two main functions:

• Find: Find which set a specific element belongs to
• Union: Merge the sets that two elements belong to

If no cycle occurs, we select the edge; otherwise, we ignore the edge.
We define the basic Union-Find class and its methods required to implement the algorithm.

Step 4: Implementing MST

Now we will combine the implementations of all steps to ultimately find the MST.
Below is an example of the Kruskal’s algorithm implemented in JavaScript.

    class UnionFind {
        constructor(size) {
            this.parent = Array.from({length: size}, (_, index) => index);
            this.rank = Array(size).fill(1);
        }

        find(node) {
            if (this.parent[node] !== node) {
                this.parent[node] = this.find(this.parent[node]);
            }
            return this.parent[node];
        }

        union(node1, node2) {
            const root1 = this.find(node1);
            const root2 = this.find(node2);
            if (root1 !== root2) {
                if (this.rank[root1] > this.rank[root2]) {
                    this.parent[root2] = root1;
                } else if (this.rank[root1] < this.rank[root2]) {
                    this.parent[root1] = root2;
                } else {
                    this.parent[root2] = root1;
                    this.rank[root1]++;
                }
            }
        }

        connected(node1, node2) {
            return this.find(node1) === this.find(node2);
        }
    }

    function kruskal(edges, numVertices) {
        edges.sort((a, b) => a[2] - b[2]); // Sort edges by weight
        const uf = new UnionFind(numVertices);
        const mst = [];
        let totalWeight = 0;

        for (const [u, v, weight] of edges) {
            if (!uf.connected(u - 1, v - 1)) {
                uf.union(u - 1, v - 1);
                mst.push([u, v, weight]);
                totalWeight += weight;
            }
        }

        return { mst, totalWeight };
    }

    const edges = [
        [1, 2, 4],
        [1, 3, 1],
        [2, 3, 2],
        [2, 4, 5],
        [3, 4, 8],
        [1, 4, 3]
    ];
    const numVertices = 4;

    const { mst, totalWeight } = kruskal(edges, numVertices);
    console.log("List of edges in the minimum spanning tree:", mst);
    console.log("Sum of minimum weights:", totalWeight);

Step 5: Analyzing Results

The results obtained through the implemented algorithm are as follows.
We analyze whether the algorithm works correctly by checking the list of edges in the minimum spanning tree and the total weight.
As a result, we successfully formed the minimum spanning tree based on the given edges.

• List of edges in the minimum spanning tree: [(1, 3, 1), (2, 3, 2), (1, 4, 3), (2, 4, 5)]
• Sum of minimum weights: 11

Conclusion

Today, we examined how to solve the minimum spanning tree problem using JavaScript.
Various algorithms can be applied using the given list of edges, and we can understand the characteristics of graphs in the process.
While tackling such problems, we can gain experience in algorithm performance analysis and optimization,
and since this is a topic likely to appear in actual coding tests, be sure to practice sufficiently.

1. Problem Statement

Breadth-First Search (BFS) is one of the search algorithms commonly used in graphs or tree structures. In this tutorial, we will use BFS to solve the “Shortest Path Finding” problem.

Problem: Find the Shortest Path

Write a function to find the shortest path between two nodes in the given graph. The graph is provided in the form of an adjacency list, and the nodes are represented as strings.

Input Format

        graph: {
            "A": ["B", "C"],
            "B": ["A", "D", "E"],
            "C": ["A", "F"],
            "D": ["B"],
            "E": ["B", "F"],
            "F": ["C", "E"]
        }
        start: "A"
        end: "F"
    

Output Format

        ["A", "C", "F"]
    

2. Problem Analysis

The reason we use BFS to find the shortest path is that BFS explores all neighboring nodes at once, guaranteeing the fastest path. Unlike DFS (Depth-First Search), BFS explores all nodes connected to the current node first before moving to the next level. This characteristic makes BFS suitable for shortest path searches.

3. Algorithm Design

Below is the basic flow of the shortest path finding algorithm using BFS:

1. Add the starting node to the queue and mark it as visited.
2. Remove a node from the queue and check all its neighbor nodes.
3. Add any unvisited neighbor nodes to the queue and set the parent of that node to the current node.
4. Repeat steps 2-3 until the ending node is found.
5. When reaching the end node, backtrack through the parent nodes to construct the shortest path.

4. Code Implementation

Below is the implementation code for the shortest path finding function using BFS:

        function findShortestPath(graph, start, end) {
            // Object for queue and marking visited nodes
            let queue = [start];
            let visited = {};
            let parent = {};
            
            visited[start] = true;
            parent[start] = null;

            while (queue.length > 0) {
                let currentNode = queue.shift(); // Remove node from queue
                
                // If the end node is reached
                if (currentNode === end) {
                    return reconstructPath(parent, start, end);
                }

                // Explore the neighbors of the current node
                for (let neighbor of graph[currentNode]) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        parent[neighbor] = currentNode; // Set the current node as the parent of the neighbor
                        queue.push(neighbor); // Add the neighbor to the queue
                    }
                }
            }
            return []; // Return empty array if there is no path
        }

        function reconstructPath(parent, start, end) {
            let path = [];
            let current = end;
            while (current !== null) {
                path.push(current);
                current = parent[current];
            }
            return path.reverse(); // Return path in reverse order
        }
    

5. Algorithm Analysis

The code above uses BFS to find the shortest path. The time complexity is O(V + E), where V is the number of nodes and E is the number of edges. This algorithm is memory efficient because it utilizes an adjacency list.

6. Time Complexity and Space Complexity Analysis

The time complexity is O(V + E), as all nodes and edges are explored once. The space complexity is also O(V) because arrays for the queue, visited markers, and parent storage are proportional to the number of nodes.

7. Test Cases

Let’s create a few test cases to check the above code.

        const graph = {
            "A": ["B", "C"],
            "B": ["A", "D", "E"],
            "C": ["A", "F"],
            "D": ["B"],
            "E": ["B", "F"],
            "F": ["C", "E"]
        };

        console.log(findShortestPath(graph, "A", "F")); // Output: ["A", "C", "F"]
        console.log(findShortestPath(graph, "B", "F")); // Output: ["B", "E", "F"]
        console.log(findShortestPath(graph, "D", "A")); // Output: ["D", "B", "A"]
        console.log(findShortestPath(graph, "A", "A")); // Output: ["A"]
    

8. Conclusion

In this tutorial, we solved the shortest path problem using Breadth-First Search (BFS) with JavaScript. BFS is a useful method for traversing graphs using structures like adjacency lists and can be applied to various problems. Continue practicing algorithms and solving more problems.

9. Additional Resources

If you want to learn more algorithm problems and solutions, try using online coding test platforms. You can enhance your skills through various problems and hints available.

Hello. Today, we will delve into the Bellman-Ford algorithm for those of you preparing for JavaScript coding tests. The Bellman-Ford algorithm is one of the algorithms used to find the shortest path in graph theory, with the advantage that it can be applied even when there are edges with negative weights. In this article, we will cover the overview, principles, problem-solving process, and implementation in JavaScript of the Bellman-Ford algorithm.

1. Overview of the Bellman-Ford Algorithm

The Bellman-Ford algorithm is a graph algorithm used to find the shortest path from one vertex to another. This algorithm has the following characteristics:

• It can be used even if there are edges with negative weights.
• It can verify if there are cycles in the graph, or if no negative cycles exist.

2. Principles of the Bellman-Ford Algorithm

The Bellman-Ford algorithm operates on the following principles:

1. Set the starting vertex and initialize the distance value for that vertex to 0. Set the distance values for all other vertices to infinity.
2. Examine each edge once to update the shortest distance from the starting vertex to the ending vertex of each edge.
3. Repeat this process V - 1 times (the shortest path in a graph passes through at most V - 1 edges).
4. Finally, check all edges again. If any distance values are updated, it is concluded that a negative cycle exists.

3. Problem Statement

Let’s solve the following problem:

Problem:
When given n cities and m roads, each road has a weight that represents the distance from the starting city to the destination city.
Generally, the starting city is city 1, and the destination city is city n.
Write a function to find the shortest distance from city 1 to city n. (There may be negative edges.)

4. Problem-Solving Process

Here is a detailed explanation of how to solve this problem using the Bellman-Ford algorithm:

4.1. Input Data Structure Design

We need to define the input data required to solve the problem. First, we need to design a structure that contains the number of cities, the number of roads, and information about each road. Below is an example of how to represent roads using an array of objects:

    // Number of cities and number of roads
    const n = 5; // Number of cities
    const m = 8; // Number of roads

    // Road information (starting city, destination city, distance)
    const roads = [
        { from: 1, to: 2, weight: 4 },
        { from: 1, to: 3, weight: 2 },
        { from: 2, to: 3, weight: 5 },
        { from: 2, to: 4, weight: 10 },
        { from: 3, to: 2, weight: 1 },
        { from: 3, to: 4, weight: 3 },
        { from: 4, to: 5, weight: 3 },
        { from: 2, to: 5, weight: 12 }
    ];
    

4.2. Initialization

Next, we initialize the distance values. The distance for city 1 is set to 0, and the distances for the other cities are set to infinity:

    const INF = Infinity; // Infinite value
    const distance = Array(n + 1).fill(INF); // Distance array from 1 to n
    distance[1] = 0; // Initialize distance for starting city
    

4.3. Implementing the Bellman-Ford Algorithm

Now, let’s implement the Bellman-Ford algorithm. We will update the distance values by iterating through the edges n-1 times:

    for (let i = 1; i < n; i++) {
        for (const road of roads) {
            if (distance[road.from] + road.weight < distance[road.to]) {
                distance[road.to] = distance[road.from] + road.weight;
            }
        }
    }
    

4.4. Checking for Negative Cycles

Finally, we implement a process to check all edges again to see if there are any negative cycles:

    let hasNegativeCycle = false;

    for (const road of roads) {
        if (distance[road.from] + road.weight < distance[road.to]) {
            hasNegativeCycle = true; // Negative cycle exists
            break;
        }
    }

    if (hasNegativeCycle) {
        console.log("A negative cycle exists.");
    } else {
        console.log("Shortest distance:", distance[n]);
    }
    

5. Complete Code

Putting all the above processes together, we will create a complete JavaScript code:

    function bellmanFord(n, roads) {
        const INF = Infinity;
        const distance = Array(n + 1).fill(INF);
        distance[1] = 0;

        // Bellman-Ford algorithm
        for (let i = 1; i < n; i++) {
            for (const road of roads) {
                if (distance[road.from] + road.weight < distance[road.to]) {
                    distance[road.to] = distance[road.from] + road.weight;
                }
            }
        }

        // Check for negative cycles
        let hasNegativeCycle = false;
        for (const road of roads) {
            if (distance[road.from] + road.weight < distance[road.to]) {
                hasNegativeCycle = true;
                break;
            }
        }

        if (hasNegativeCycle) {
            console.log("A negative cycle exists.");
        } else {
            console.log("Shortest distance:", distance[n]);
        }
    }

    // Example usage
    const n = 5;
    const roads = [
        { from: 1, to: 2, weight: 4 },
        { from: 1, to: 3, weight: 2 },
        { from: 2, to: 3, weight: 5 },
        { from: 2, to: 4, weight: 10 },
        { from: 3, to: 2, weight: 1 },
        { from: 3, to: 4, weight: 3 },
        { from: 4, to: 5, weight: 3 },
        { from: 2, to: 5, weight: 12 }
    ];

    bellmanFord(n, roads);
    

6. Conclusion

In this article, we thoroughly explored the basic concepts and principles of the Bellman-Ford algorithm, as well as the process of solving problems using it. This algorithm is useful when there are edges with negative weights and is one of the important algorithms to learn in graph theory. Since it is a frequently tested topic in coding tests, be sure to understand it well.

I hope you continue to build your skills through various algorithms and problem-solving, and feel free to leave any questions in the comments. Thank you!