C++ Algorithms | 'Must-Solve' Problems for Coding Tests

C++ Algorithms | 'Must-Solve' Problems for Coding Tests

· 15분 읽기 · 수정 Intermediate Tutorial
C++ Algorithms | 'Must-Solve' Problems for Coding Tests

이 글의 핵심

C++ algorithm problem-solving. Covers sorting, searching, DP, greedy, and graph algorithms with practical examples and applications.

These snippets are interview-style patterns you can drop into competitive programming or coding tests. Prefer std:: algorithms (lower_bound, sort, priority_queue) when they clarify intent and avoid off-by-one bugs; use raw loops when the problem is tiny or needs a very specific traversal. Each snippet notes typical time/space complexity—always re-check constraints (n, value ranges) before choosing O(n²) vs O(n log n) vs O(n).

1. Two Sum

Problem: Find the indices of two numbers in an array that add up to the target.

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;
    
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        
        if (seen.find(complement) != seen.end()) {
            return {seen[complement], i};
        }
        
        seen[nums[i]] = i;
    }
    
    return {};
}

// Time Complexity: O(n)
// Space Complexity: O(n)

Problem: Find the target in a sorted array.

int binarySearch(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

// Time Complexity: O(log n)

3. Maximum Subarray

Problem: Find the maximum sum of a contiguous subarray.

int maxSubArray(vector<int>& nums) {
    int maxSum = nums[0];
    int currentSum = nums[0];
    
    for (int i = 1; i < nums.size(); i++) {
        currentSum = max(nums[i], currentSum + nums[i]);
        maxSum = max(maxSum, currentSum);
    }
    
    return maxSum;
}

// Kadane's Algorithm
// Time Complexity: O(n)

4. Coin Change

Problem: Find the minimum number of coins needed to make up the given amount.

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i >= coin) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    return dp[amount] > amount ? -1 : dp[amount];
}

// Dynamic Programming
// Time Complexity: O(amount * coins.size())

5. Number of Islands

Problem: Count the number of islands in a 2D grid.

class Solution {
private:
    void dfs(vector<vector<char>>& grid, int i, int j) {
        if (i < 0 || i >= grid.size() || 
            j < 0 || j >= grid[0].size() || 
            grid[i][j] == '0') {
            return;
        }
        
        grid[i][j] = '0';  // Mark as visited
        
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
    
public:
    int numIslands(vector<vector<char>>& grid) {
        int count = 0;
        
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        
        return count;
    }
};

// DFS
// Time Complexity: O(m * n)

6. Valid Parentheses

Problem: Check if a string of parentheses is valid.

bool isValid(string s) {
    stack<char> st;
    unordered_map<char, char> pairs = {
        {')', '('},
        {'}', '{'},
        {']', '['}
    };
    
    for (char c : s) {
        if (pairs.find(c) == pairs.end()) {
            // Opening parenthesis
            st.push(c);
        } else {
            // Closing parenthesis
            if (st.empty() || st.top() != pairs[c]) {
                return false;
            }
            st.pop();
        }
    }
    
    return st.empty();
}

// Time Complexity: O(n)

7. Longest Increasing Subsequence (LIS)

Problem: Find the length of the longest increasing subsequence.

int lengthOfLIS(vector<int>& nums) {
    vector<int> dp(nums.size(), 1);
    int maxLen = 1;
    
    for (int i = 1; i < nums.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }
    
    return maxLen;
}

// Dynamic Programming
// Time Complexity: O(n²)

// Optimized Version (Binary Search)
int lengthOfLIS_optimized(vector<int>& nums) {
    vector<int> tails;
    
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    
    return tails.size();
}

// Time Complexity: O(n log n)

8. 0/1 Knapsack

Problem: Find the maximum value within the weight limit W.

int knapsack(vector<int>& weights, vector<int>& values, int W) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (weights[i-1] <= w) {
                dp[i][w] = max(
                    dp[i-1][w],
                    dp[i-1][w - weights[i-1]] + values[i-1]
                );
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    
    return dp[n][W];
}

// Time Complexity: O(n * W)

9. Shortest Path (Dijkstra)

Problem: Find the shortest distance from the start node to all other nodes.

vector<int> dijkstra(vector<vector<pair<int,int>>>& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto [v, weight] : graph[u]) {
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}

// Time Complexity: O((V + E) log V)

10. Permutations/Combinations

Problem: Generate all permutations.

void permute(vector<int>& nums, int start, vector<vector<int>>& result) {
    if (start == nums.size()) {
        result.push_back(nums);
        return;
    }
    
    for (int i = start; i < nums.size(); i++) {
        swap(nums[start], nums[i]);
        permute(nums, start + 1, result);
        swap(nums[start], nums[i]);  // Backtracking
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    permute(nums, 0, result);
    return result;
}

// Time Complexity: O(n!)

// Combinations
void combine(int n, int k, int start, vector<int>& current, 
             vector<vector<int>>& result) {
    if (current.size() == k) {
        result.push_back(current);
        return;
    }
    
    for (int i = start; i <= n; i++) {
        current.push_back(i);
        combine(n, k, i + 1, current, result);
        current.pop_back();
    }
}

Coding Test Tips

1. Input/Output Optimization

// Fast I/O
ios_base::sync_with_stdio(false);
cin.tie(nullptr);

// File I/O
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

2. Frequently Used Templates

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // Code...
    
    return 0;
}

3. Debugging Macros

#ifdef LOCAL
#define debug(x) cerr << #x << " = " << (x) << endl
#else
#define debug(x)
#endif

int main() {
    int x = 10;
    debug(x);  // Prints only in local environment
}

Common Mistakes

Mistake 1: Integer Overflow

// ❌ Overflow
int sum = a * b;

// ✅ Use long long
long long sum = (long long)a * b;

Mistake 2: Array Out-of-Bounds

// ❌ No boundary check
if (grid[i+1][j] == 1) { ... }

// ✅ Add boundary check
if (i+1 < n && grid[i+1][j] == 1) { ... }

Mistake 3: Time Limit Exceeded

// ❌ O(n³)
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k++)

// ✅ Optimize to O(n²) or O(n log n)

FAQ

Q1: Which algorithms should I learn first?

A:

  1. Sorting, Searching
  2. Greedy, DP
  3. Graphs (BFS, DFS)
  4. Advanced (e.g., Segment Trees)

Q2: What if I can’t solve a problem?

A:

  1. Start with small examples
  2. Think brute force first
  3. Look for patterns
  4. Find similar problems

Q3: How do I calculate time complexity?

A:

  • Single loop: O(n)
  • Nested loops: O(n²)
  • Binary search: O(log n)
  • Sorting: O(n log n)

A:

  • LeetCode (English)
  • Baekjoon (Korean)
  • Programmers (Korean)
  • Codeforces (English)

Q5: How long should I prepare for coding tests?

A:

  • Beginner: 1-2 months
  • Intermediate: 3-6 months
  • Advanced: 6+ months

Q6: Is STL necessary?

A: Yes, understanding vector, map, set, and algorithm functions is essential.

Here are some related posts you might find helpful:

Practical Tips

Debugging Tips

  • Check compiler warnings first when issues arise
  • Reproduce the problem with simple test cases

Performance Tips

  • Don’t optimize without profiling
  • Set measurable performance goals first

Code Review Tips

  • Check for common feedback points in advance
  • Follow team coding conventions

Practical Checklist

Use this checklist to ensure quality and avoid mistakes when applying these concepts.

Before Writing Code

  • Is this the best approach for solving the problem?
  • Will your team understand and maintain this code?
  • Does it meet performance requirements?

While Writing Code

  • Have you resolved all compiler warnings?
  • Have you considered edge cases?
  • Is error handling appropriate?

During Code Review

  • Is the intent of the code clear?
  • Are there sufficient test cases?
  • Is the documentation complete?

Use this checklist to reduce errors and improve code quality.

Keywords Covered in This Post

Search for terms like C++, Algorithms, Coding Test, Problem Solving, and PS to find more resources related to this post.

Other articles related to this topic.

Keywords Covered in This Article (Related Search Terms)

This article covers C++, Algorithm, Coding Test, Problem Solving, PS.