C++ 알고리즘 문제풀이 | 코딩테스트 필수 문제 10선

1. 두 수의 합 (Two Sum)

문제: 배열에서 합이 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 {};
}

// 시간복잡도: O(n)
// 공간복잡도: O(n)

2. 이진 탐색 (Binary Search)

문제: 정렬된 배열에서 target을 찾아라.

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;
}

// 시간복잡도: O(log n)

3. 최대 부분 배열 합 (Maximum 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;
}

// 카데인 알고리즘
// 시간복잡도: O(n)

4. 동전 거스름돈 (Coin Change)

문제: 최소 동전 개수로 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];
}

// 동적 프로그래밍
// 시간복잡도: O(amount * coins.size())

5. 섬의 개수 (Number of Islands)

문제: 2D 그리드에서 섬의 개수를 세어라.

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';  // 방문 표시
        
        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
// 시간복잡도: O(m * n)

6. 유효한 괄호 (Valid Parentheses)

문제: 괄호 문자열이 유효한지 확인하라.

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

// 시간복잡도: O(n)

7. 최장 증가 부분 수열 (LIS)

문제: 가장 긴 증가하는 부분 수열의 길이를 구하라.

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;
}

// 동적 프로그래밍
// 시간복잡도: O(n²)

// 최적화 버전 (이진 탐색)
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();
}

// 시간복잡도: O(n log n)

8. 배낭 문제 (0/1 Knapsack)

문제: 최대 무게 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];
}

// 시간복잡도: O(n * W)

9. 최단 경로 (Dijkstra)

문제: 시작 노드에서 모든 노드까지의 최단 거리를 구하라.

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;
}

// 시간복잡도: O((V + E) log V)

10. 순열/조합 생성

문제: 모든 순열을 생성하라.

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]);  // 백트래킹
    }
}

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

// 시간복잡도: O(n!)

// 조합
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();
    }
}

코딩테스트 팁

1. 입출력 최적화

// 빠른 입출력
ios_base::sync_with_stdio(false);
cin.tie(nullptr);

// 파일 입출력
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

2. 자주 쓰는 템플릿

#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);
    
    // 코드...
    
    return 0;
}

3. 디버깅 매크로

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

int main() {
    int x = 10;
    debug(x);  // 로컬에서만 출력
}

자주 발생하는 실수

실수 1: 정수 오버플로우

// ❌ 오버플로우
int sum = a * b;

// ✅ long long 사용
long long sum = (long long)a * b;

실수 2: 배열 범위 초과

// ❌ 범위 체크 없음
if (grid[i+1][j] == 1) { ... }

// ✅ 범위 체크
if (i+1 < n && grid[i+1][j] == 1) { ... }

실수 3: 시간 초과

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

// ✅ O(n²) 또는 O(n log n)으로 개선

FAQ

Q1: 어떤 알고리즘을 먼저 배워야 하나요?

A:

1. 정렬, 탐색
2. 그리디, DP
3. 그래프 (BFS, DFS)
4. 고급 (세그먼트 트리 등)

Q2: 문제를 못 풀겠어요!

A:

1. 작은 예제로 시작
2. 브루트포스부터 생각
3. 패턴 찾기
4. 비슷한 문제 찾기

Q3: 시간복잡도는 어떻게 계산하나요?

A:

• 단일 루프: O(n)
• 중첩 루프: O(n²)
• 이진 탐색: O(log n)
• 정렬: O(n log n)

Q4: 추천 문제 사이트는?

A:

• LeetCode (영어)
• 백준 (한국어)
• 프로그래머스 (한국어)
• Codeforces (영어)

Q5: 코딩테스트 준비 기간은?

A:

• 기초: 1-2개월
• 중급: 3-6개월
• 고급: 6개월+

Q6: STL을 꼭 알아야 하나요?

A: 네, vector, map, set, algorithm 함수는 필수입니다.

---

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

• C++ 코딩테스트 팁 | “백준/프로그래머스” 합격하는 10가지 비법
• C++ 코딩 테스트 | “백준·프로그래머스” 알고리즘 유형별 STL 활용법
• C++ 알고리즘 | “STL algorithm” 핵심 정리

실전 팁

실무에서 바로 적용할 수 있는 팁입니다.

디버깅 팁

• 문제가 발생하면 먼저 컴파일러 경고를 확인하세요
• 간단한 테스트 케이스로 문제를 재현하세요

성능 팁

• 프로파일링 없이 최적화하지 마세요
• 측정 가능한 지표를 먼저 설정하세요

코드 리뷰 팁

• 코드 리뷰에서 자주 지적받는 부분을 미리 체크하세요
• 팀의 코딩 컨벤션을 따르세요

---

실전 체크리스트

실무에서 이 개념을 적용할 때 확인해야 할 사항입니다.

코드 작성 전

• 이 기법이 현재 문제를 해결하는 최선의 방법인가?
• 팀원들이 이 코드를 이해하고 유지보수할 수 있는가?
• 성능 요구사항을 만족하는가?

코드 작성 중

• 컴파일러 경고를 모두 해결했는가?
• 엣지 케이스를 고려했는가?
• 에러 처리가 적절한가?

코드 리뷰 시

• 코드의 의도가 명확한가?
• 테스트 케이스가 충분한가?
• 문서화가 되어 있는가?

이 체크리스트를 활용하여 실수를 줄이고 코드 품질을 높이세요.

---

이 글에서 다루는 키워드 (관련 검색어)

C++, 알고리즘, 코딩테스트, 문제풀이, PS 등으로 검색하시면 이 글이 도움이 됩니다.

---

관련 글

• 배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리
• 정렬 문제 풀이 | 코딩 테스트 정렬 패턴 완벽 정리
• DP 실전 문제 | 코딩 테스트 DP 문제 풀이 전략
• C++ 코딩테스트 팁 |
• C++ 코딩 테스트 |