Author: root

JavaScript is one of the most commonly used languages in web development and often appears in coding tests. In this article, we will cover algorithm problems that can be solved with JavaScript and learn more about time complexity notation. Through the process of solving algorithm problems, let’s understand the importance of time complexity and build a foundation for writing efficient code.

function twoSum(nums, target) {
    const map = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
}
        

Understanding Time Complexity Notation

Time complexity is an important concept used to evaluate the performance of algorithms. The execution time of an algorithm varies depending on the input size, and time complexity is the numerical expression of this.

Types of Time Complexity

• O(1): Takes a constant amount of time regardless of input size.
• O(log n): The growth rate is slow as the input size increases. The binary search algorithm falls under this category.
• O(n): Occurs when traversing an array or list once.
• O(n log n): Advanced sorting algorithms such as merge sort and quicksort belong to this category.
• O(n^2): Occurs in cases with nested loops. A typical bubble sort is an example of this.
• O(2^n): Refers to recursive problems such as calculating the Fibonacci sequence.

The Importance of Time Complexity Analysis

Choosing efficient algorithms is crucial in software development. Understanding and optimizing time complexity is essential for improving program performance and providing a better experience for users.

Final Thoughts

In this article, we explored methods for solving algorithm problems using JavaScript and time complexity notation. In future coding tests, you will be able to solve more problems based on these algorithms and time complexities.

Problem Definition

This is a problem of calculating the number of ways to fill a 2*N rectangle with tiles of size 1*2 or 2*1. In other words, for a given length N, we aim to find the number of ways to completely fill the rectangle using the tiles. This problem can be solved using the Dynamic Programming technique.

Problem Description

For example, when N=3, the 2*3 rectangle can be filled in the following ways:

• 1->1->1
• 1->2
• 2->1
• 2->2
• 2->1->1

Various cases are generated depending on how the tiles are arranged. Therefore, it is possible to recursively explore all combinations by finding appropriate rules.

Problem Approach

1. Recursive Approach

The most basic method is to use recursion to explore all possible cases. However, this is inefficient and has a high time complexity, making it impractical.

2. Dynamic Programming

Using Dynamic Programming allows us to store previous computed results and utilize them to avoid redundant calculations. This approach reduces the time complexity to O(N).

Dynamic Programming Implementation

Recurrence Relation

The following recurrence relation can be established:

dp[n] = dp[n-1] + dp[n-2]

When filling the last column with a 1×2 tile, we consider the case of dp[n-1], and when filling with a 2×1 tile, we consider the case of dp[n-2]. The base conditions are as follows:

• dp[1] = 1 (Filling with a 1*2 tile)
• dp[2] = 2 (Filling with a 2*1 or 1*2 tile)

JavaScript Example Code

function tileWays(n) {
    if (n === 1) return 1;
    if (n === 2) return 2;

    let dp = new Array(n + 1);
    dp[1] = 1;
    dp[2] = 2;

    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

console.log(tileWays(3)); // Output: 3
    

Conclusion

The 2*N tile filling problem is a fundamental dynamic programming problem that is frequently featured in coding tests. Through this problem, we learn the importance of choosing efficient approaches when solving algorithmic problems.
It is essential to understand the basics of Dynamic Programming well and to develop the ability to solve complex problems step by step using it. I hope to become a better developer through practice on various problems.

Problem Description

This problem involves taking an array of given natural numbers and using a stack to create a sequence sorted in ascending order.
The array of natural numbers consists of integers between 1 and 1000, and each natural number is unique.
Additionally, the sequence must be constructed using only a stack while satisfying the following conditions:

• Each natural number can be used only once.
• The given natural numbers must be pushed onto the stack, and the numbers must be sorted in ascending order by popping from the stack.
• During the sequence creation, the state of the stack must be output at intermediate steps.

Input Example

5
    3
    2
    4
    1

Output Example

1
    2
    3
    4
    5

Solution Process

To solve this problem, we need to utilize the LIFO (Last-In-First-Out) characteristic of the stack.
By using the fundamental operations of the stack, push and pop, we should be able to create a sequence sorted in ascending order from the given numbers.

Step 1: Problem Analysis

To solve the problem, we must first push the given natural numbers onto the stack and appropriately pop them to output the required sequence.
Specifically, we need to consider how to manipulate the stack to sequentially output the smallest number first.
In other words, while pushing numbers onto the stack, we should compare the top number of the stack with the number we need to output later and pop appropriately.

Step 2: Algorithm Design

The following algorithm describes the step-by-step process to output the given sequence in ascending order using a stack.

1. Read the natural numbers sequentially.
2. Add the read number to the stack.
3. Check the current minimum value, and if the top number of the stack equals this minimum value, perform a pop operation and output it.
4. Repeat the above process until all input numbers are processed.

Step 3: JavaScript Code Implementation

function createSortedSequence(arr) {
        // Initialize Stack
        const stack = [];
        const result = [];
        
        // Initialize the next number to be output
        let next = 1;
        
        // Iterate through the given array
        for (let i = 0; i < arr.length; i++) {
            // Push the current number onto the stack
            stack.push(arr[i]);

            // If the top number of the stack equals next, pop it
            while (stack.length > 0 && stack[stack.length - 1] === next) {
                result.push(stack.pop());
                next++;
            }
        }
        
        // Return the result
        return result;
    }
    
    const inputArray = [3, 2, 4, 1, 5];
    console.log(createSortedSequence(inputArray));

Step 4: Code Explanation

In the above code, the createSortedSequence function takes an array containing natural numbers as input.
It initializes a stack and uses a next variable to determine which number should be output.
Then, it pushes the given array of numbers onto the stack and compares the top number of the stack with next.
If they match, it pops the number and adds it to the result array. This process continues to obtain an array sorted in ascending order.

Step 5: Test Results

When the code is executed, the following result is produced.

    [1, 2, 3, 4, 5]
    

Step 6: Conclusion

Through this problem, we gained a basic understanding of how to use stacks and learned how to utilize the properties of stacks to sort the given numbers.
Moreover, we were able to systematically carry out the entire process from problem interpretation to algorithm design, code implementation, and testing.
Solving such problems is not only useful for preparing for algorithm interviews but also in real applications.

Additional Learning Resources

To gain a deeper understanding of stack structures, we recommend referring to the following materials:

• JavaScript Array – MDN Documentation
• Stack (Abstract Data Type) – Wikipedia

Frequently Asked Questions

Q: Is it possible to solve this problem without using a stack?
A: Since the problem requires the use of the properties of stacks, it cannot be solved without using a stack.

Q: Could there be performance issues if the input is a very large array?
A: This algorithm operates with O(n) time complexity, so it works efficiently. However, memory usage may increase depending on the size of the array.

Problem Description

There is a given undirected graph. The graph consists of nodes and edges,
and each edge has a weight. Let’s solve the problem of finding the shortest path from the starting node
to all other nodes. This algorithm can be solved using Dijkstra’s algorithm.

Problem Definition

Let’s assume the graph below. The number of nodes is n, and the number of edges is e.

    Input
    n = 6
    e = 9
    edges = [
        [1, 2, 1],
        [1, 3, 4],
        [2, 3, 2],
        [2, 4, 5],
        [3, 4, 1],
        [4, 5, 3],
        [3, 5, 6],
        [5, 6, 2],
        [4, 6, 1]
    ]
    start = 1
    

Write a function that finds the shortest path from the start node (node 1) to other nodes in the given graph.
The function should return an array of the minimum distances to each node.

Algorithm Overview

Dijkstra’s algorithm is used to find the shortest path from a given node to all other nodes in graph theory.
This algorithm efficiently finds the shortest path using a priority queue. The following steps are followed
in the actual implementation.

1. Initialize the shortest distance array for each node. Set the initial value to infinity, but set the distance of the starting node to 0.
2. Add the starting node to the priority queue (min-heap).
3. Repeat while the queue is not empty.
4. Extract the node with the shortest distance from the queue and update the distances for its adjacent nodes. If the new distance is smaller than the existing distance, add it to the priority queue.
5. Return the array after calculating the shortest distances for all nodes.

JavaScript Implementation

Now, let’s implement a JavaScript function that solves the above problem based on the algorithm.

    function dijkstra(n, edges, start) {
        // 1. Construct the graph
        const graph = Array.from({ length: n + 1 }, () => []);
        for (const [u, v, weight] of edges) {
            graph[u].push({ node: v, weight });
            graph[v].push({ node: u, weight }); // undirected
        }

        // 2. Initialize shortest distance
        const distance = Array(n + 1).fill(Infinity);
        distance[start] = 0;

        // 3. Initialize the priority queue
        const pq = new MinHeap();
        pq.insert({ node: start, weight: 0 });

        while (!pq.isEmpty()) {
            const { node: currentNode, weight: currentWeight } = pq.extractMin();

            if (currentWeight > distance[currentNode]) continue;

            // 4. Process adjacent nodes
            for (const { node: neighbor, weight } of graph[currentNode]) {
                const newDistance = currentWeight + weight;
                if (newDistance < distance[neighbor]) {
                    distance[neighbor] = newDistance;
                    pq.insert({ node: neighbor, weight: newDistance });
                }
            }
        }

        return distance.slice(1); // Return distance array excluding the start node
    }

    // Min-heap class (priority queue implementation)
    class MinHeap {
        constructor() {
            this.heap = [];
        }

        insert({ node, weight }) {
            this.heap.push({ node, weight });
            this.bubbleUp();
        }

        bubbleUp() {
            let index = this.heap.length - 1;
            while (index > 0) {
                let parentIndex = Math.floor((index - 1) / 2);
                if (this.heap[index].weight >= this.heap[parentIndex].weight) break;
                [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
                index = parentIndex;
            }
        }

        extractMin() {
            if (this.heap.length === 1) return this.heap.pop();
            const min = this.heap[0];
            this.heap[0] = this.heap.pop();
            this.bubbleDown();
            return min;
        }

        bubbleDown() {
            let index = 0;
            const length = this.heap.length;
            const element = this.heap[0];

            while (true) {
                let leftChildIndex = 2 * index + 1;
                let rightChildIndex = 2 * index + 2;
                let leftChild, rightChild;
                let swap = null;

                if (leftChildIndex < length) {
                    leftChild = this.heap[leftChildIndex];
                    if (leftChild.weight < element.weight) {
                        swap = leftChildIndex;
                    }
                }

                if (rightChildIndex < length) {
                    rightChild = this.heap[rightChildIndex];
                    if (
                        (swap === null && rightChild.weight < element.weight) ||
                        (swap !== null && rightChild.weight < leftChild.weight)
                    ) {
                        swap = rightChildIndex;
                    }
                }

                if (swap === null) break;
                this.heap[index] = this.heap[swap];
                index = swap;
            }

            this.heap[index] = element;
        }

        isEmpty() {
            return this.heap.length === 0;
        }
    }
    

Test

To test the above code, you can call the function as follows to check the result.

    const n = 6;
    const edges = [
        [1, 2, 1],
        [1, 3, 4],
        [2, 3, 2],
        [2, 4, 5],
        [3, 4, 1],
        [4, 5, 3],
        [3, 5, 6],
        [5, 6, 2],
        [4, 6, 1]
    ];
    const start = 1;
    const distances = dijkstra(n, edges, start);
    console.log(distances); // [0, 1, 3, 4, 6, 7]
    

Conclusion

Dijkstra's algorithm is a very useful algorithm for finding the shortest path. Through the problems and code discussed in this tutorial,
I hope you gained an understanding of the basic concepts of Dijkstra's algorithm and its implementation in JavaScript. A deeper understanding of algorithms will help enhance your coding test skills and problem-solving abilities.

Continue to study and practice various algorithms!