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

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

이 글의 핵심

Interview-style C++ patterns: binary search on answer, two pointers, heaps, DP—complexity notes and when to trust std:: algorithms.

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:

  • C++ STL algorithms — English series hub
  • C++ Coding Test Tips | “10 Proven Strategies for Success”
  • C++ Coding Test | “STL Usage by Algorithm Type”
  • C++ Algorithms | “Essential STL Algorithm Guide”

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.