C++ 알고리즘 문제풀이 | 코딩테스트 필수 문제 10선
이 글의 핵심
문제를 많이 풀어도 유형을 연결하지 못하면 비슷한 문제에서 다시 막힙니다. 해시·DP·그래프 탐색 같은 대표 기법이 각 문제에 어떻게 적용되는지 보여 주고, 입출력 최적화와 자주 쓰는 템플릿, 정수 오버플로·배열 범위 초과·시간 초과 같은 실수를 피하는 방법을 함께 정리했습니다.
코딩테스트 문제는 겉모습이 달라도 결국 몇 가지 기법의 조합입니다. 이 글의 10문제는 각각 해시, 이진 탐색, 그리디형 DP, 1차원·2차원 DP, 그래프 탐색, 스택, 우선순위 큐, 백트래킹이라는 대표 기법 하나씩을 담고 있습니다. 코드를 외우기보다 “입력 크기가 이 정도면 어떤 복잡도까지 허용되는가”와 “이 문제의 어떤 성질이 이 기법을 쓰게 만드는가”를 중심으로 읽는 것이 좋습니다.
판단 기준으로 흔히 쓰는 어림셈이 있습니다. C++에서 단순 연산은 1초에 대략 1억(10^8) 번 정도로 봅니다. n이 10^5 이상이면 O(n log n) 이하, n이 수천이면 O(n²), n이 20 안팎이면 O(2^n)이나 O(n!)까지 가능하다는 식입니다. 문제의 제한 조건을 먼저 보고 허용되는 복잡도를 정한 뒤 알고리즘을 고르면, 시간 초과를 받고 나서 고민하는 일이 크게 줄어듭니다.
두 수의 합 (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)모든 쌍을 확인하면 O(n²)이지만, “지금 수와 짝이 되는 수(target - nums[i])를 이미 봤는가”를 해시맵으로 O(1)에 확인하면 한 번의 순회로 끝납니다. 공간을 써서 시간을 사는 가장 대표적인 예입니다. 짝을 먼저 찾아본 뒤에 현재 수를 넣는 순서가 중요한데, 반대로 넣고 나서 찾으면 target이 6이고 nums[i]가 3일 때 자기 자신과 짝을 지어 {i, i}를 돌려주는 버그가 생깁니다. 이 순서 덕분에 [3, 3]처럼 같은 값이 두 개 있는 경우도 올바르게 처리됩니다.
배열이 이미 정렬되어 있다면 해시 없이 양 끝에서 좁혀 오는 투 포인터로 O(1) 공간에 풀 수 있고, 인덱스가 아니라 값만 필요하다면 정렬 후 투 포인터(O(n log n))도 선택지입니다. unordered_map은 해시 충돌을 노린 입력(Codeforces의 해킹 등)에서 O(n)으로 느려질 수 있어, 그런 환경에서는 커스텀 해시를 쓰거나 map으로 바꾸기도 합니다. seen[complement]처럼 operator[]를 쓰면 키가 없을 때 원소를 새로 만들므로, 조회만 할 때는 find 결과의 ->second를 쓰는 습관이 안전합니다.
이진 탐색 (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)이진 탐색은 개념은 쉬운데 경계 처리에서 틀리기 쉬운 대표 알고리즘입니다. 이 구현은 [left, right] 닫힌 구간을 유지하므로 조건이 left <= right이고 갱신이 mid ± 1입니다. 반열린 구간 [left, right)로 쓰면 right = nums.size(), left < right, right = mid로 규칙이 바뀌는데, 두 방식을 섞으면 무한 루프나 원소 하나를 빠뜨리는 버그가 납니다. 한 가지 방식을 정해 두고 항상 그렇게 쓰는 것이 가장 좋은 예방책입니다.
mid = left + (right - left) / 2는 (left + right) / 2에서 두 값의 합이 int 범위를 넘는 오버플로를 피하려는 관례입니다. 실제 코딩테스트에서는 “값을 찾는” 문제보다 “조건을 만족하는 최솟값/최댓값을 찾는” 문제(매개변수 탐색)가 훨씬 자주 나오는데, 이때는 std::lower_bound(처음으로 target 이상인 위치)와 std::upper_bound(처음으로 target 초과인 위치)의 정의를 정확히 알아 두면 직접 구현할 일이 줄어듭니다. 자세한 패턴은 이진 탐색에서 다룹니다.
최대 부분 배열 합 (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)카데인 알고리즘의 핵심은 currentSum을 “i에서 끝나는 부분 배열의 최대 합”으로 정의하는 것입니다. i에서 끝나는 최선은 앞의 합에 이어 붙이거나(currentSum + nums[i]), 앞을 버리고 새로 시작하는(nums[i]) 둘 중 하나입니다. 앞의 합이 음수라면 이어 붙이는 것이 손해이므로 버리게 됩니다. 이렇게 “끝 위치를 고정한 부분 문제”로 바꾸는 발상은 DP 문제 전반에 쓰입니다.
초기값을 0이 아니라 nums[0]으로 둔 이유는 모든 원소가 음수인 경우 때문입니다. maxSum = 0으로 시작하면 [-3, -1, -2]에서 답 -1 대신 0(빈 부분 배열)을 돌려줍니다. 문제에서 빈 부분 배열을 허용하는지 확인해야 하는 이유입니다. 반대로 입력이 비어 있으면 nums[0] 접근이 정의되지 않은 동작이 되므로, 제약에 n ≥ 1이 없다면 검사가 필요합니다. 합이 int 범위를 넘을 수 있는 입력이라면 long long으로 누적합니다.
동전 거스름돈 (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())“큰 동전부터 최대한 쓰는” 그리디는 한국 화폐(500, 100, 50, 10)처럼 각 단위가 아래 단위의 배수일 때만 최적을 보장합니다. 동전이 {1, 3, 4}이고 금액이 6이면 그리디는 4+1+1(3개)을 고르지만 정답은 3+3(2개)입니다. 그래서 일반적인 동전 문제는 dp[i] = “금액 i를 만드는 최소 동전 수”로 정의하고, 마지막에 쓴 동전을 하나씩 가정해 dp[i - coin] + 1 중 최솟값을 고르는 DP로 풉니다.
dp를 amount + 1로 채운 것은 “불가능”을 뜻하는 무한대 대용입니다. 동전 최소 개수는 1원짜리만 써도 amount를 넘을 수 없으므로 amount + 1은 절대 나올 수 없는 값이고, INT_MAX를 쓰면 dp[i - coin] + 1에서 오버플로가 나는 문제를 피할 수 있습니다. 마지막 줄에서 이 값이 남아 있으면 만들 수 없다는 뜻이라 -1을 반환합니다. “최소 개수”가 아니라 “만드는 방법의 수”를 묻는 변형 문제는 바깥 반복문을 동전으로, 안쪽을 금액으로 바꿔야 순서만 다른 조합이 중복으로 세어지지 않습니다.
섬의 개수 (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)육지 칸 하나를 찾을 때마다 섬 개수를 하나 늘리고, DFS로 그 섬에 연결된 모든 육지를 '0'으로 바꿔 다시 세지 않게 합니다. 모든 칸은 최대 한 번씩만 육지에서 바다로 바뀌므로 전체가 O(m × n)입니다. 별도의 visited 배열 없이 입력 그리드를 직접 수정하는 방식은 메모리를 아끼지만, 원본이 필요한 문제라면 복사본이나 방문 배열을 써야 합니다. 범위 검사를 grid[i][j] 접근보다 먼저 하는 || 순서도 중요합니다. 순서를 바꾸면 경계 밖 인덱스를 읽게 됩니다.
재귀 DFS의 위험은 재귀 깊이입니다. 그리드 전체가 육지인 1000×1000 입력이라면 재귀가 최대 100만 단계까지 깊어질 수 있고, 기본 스택(보통 1~8MB)을 넘어 세그멘테이션 폴트(백준에서는 “런타임 에러”)가 납니다. 로컬에서 작은 예제로는 멀쩡하다가 제출하면 터지는 전형적인 경우입니다. 그리드가 크면 queue를 쓰는 BFS나 stack을 쓰는 반복 DFS로 바꾸는 것이 안전합니다. BFS·DFS 비교는 BFS와 DFS에서 다룹니다.
유효한 괄호 (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)괄호 짝은 “가장 최근에 열린 괄호가 가장 먼저 닫혀야 한다”는 구조라 스택(LIFO)과 정확히 맞습니다. 닫는 괄호를 키로, 짝이 되는 여는 괄호를 값으로 둔 맵 덕분에 괄호 종류별 if 문이 필요 없습니다. 실패 조건은 세 가지입니다. 닫는 괄호가 나왔는데 스택이 비어 있거나(")("의 첫 문자), 스택 맨 위가 짝이 아니거나("(]"), 순회가 끝났는데 스택에 여는 괄호가 남아 있는 경우("((")입니다. 마지막 return st.empty()를 return true로 쓰는 실수가 흔한데, 그러면 세 번째 경우를 통과시킵니다.
이 코드는 괄호가 아닌 문자도 모두 “여는 괄호”로 취급해 스택에 넣습니다. 입력이 괄호만으로 이루어진다는 조건이 없는 문제(수식 검사 등)라면 괄호가 아닌 문자는 건너뛰도록 조건을 추가해야 합니다. 괄호 종류가 한 가지뿐이라면 스택 대신 정수 카운터 하나로 충분합니다.
최장 증가 부분 수열 (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)O(n²) 버전은 dp[i] = “i에서 끝나는 가장 긴 증가 부분 수열의 길이”로 정의하고, 앞의 모든 j 중 nums[j] < nums[i]인 것 뒤에 붙여 봅니다. n이 수천 이하면 이것으로 충분하지만 n이 10^5이면 10^10번 연산이라 시간 초과가 납니다.
O(n log n) 버전의 tails[k]는 “길이 k+1인 증가 부분 수열들의 끝 값 중 최솟값”입니다. 끝 값이 작을수록 뒤에 더 많은 수를 붙일 수 있으므로, 새 수가 들어오면 lower_bound로 자기 이상인 첫 끝 값을 찾아 더 작은 자신으로 교체합니다. 모든 끝 값보다 크면 수열을 한 칸 늘립니다. tails는 항상 정렬된 상태라 이진 탐색이 가능합니다. 주의할 점은 tails 자체는 실제 LIS가 아니라는 것입니다. 길이만 정확하고, 실제 수열이 필요하면 각 원소가 들어간 위치와 이전 원소 인덱스를 따로 기록해 역추적해야 합니다. 또 lower_bound는 “순증가(strictly increasing)” 기준이며, 같은 값을 허용하는 “비감소” 수열을 구하려면 upper_bound로 바꿔야 합니다.
배낭 문제 (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)dp[i][w]는 “앞의 i개 물건만 고려하고 용량이 w일 때의 최대 가치”입니다. i번째 물건에 대해 넣지 않거나(dp[i-1][w]) 넣는(dp[i-1][w - weight] + value) 두 선택 중 큰 쪽을 고릅니다. 두 경우 모두 i-1 행을 참조하므로 같은 물건을 두 번 넣을 수 없고, 이것이 “0/1” 배낭의 조건입니다. 가치/무게 비율이 높은 것부터 담는 그리디는 물건을 쪼갤 수 있는 “분할 가능 배낭”에서만 최적입니다.
O(n × W)는 W에 비례하므로 W가 10^9처럼 크면 쓸 수 없습니다(의사 다항 시간). 이때는 가치 기준으로 DP 축을 바꾸거나 다른 접근이 필요합니다. 메모리는 행이 바로 이전 행만 참조한다는 점을 이용해 1차원 배열로 줄일 수 있는데, for (int w = W; w >= weights[i]; w--)처럼 용량을 큰 쪽부터 돌아야 합니다. 작은 쪽부터 돌면 방금 갱신한 값(같은 물건을 이미 넣은 상태)을 다시 참조해 같은 물건을 여러 번 넣는 “무한 배낭” 풀이가 되어 버립니다. 이 차이는 DP 패턴에서 자세히 다룹니다.
최단 경로 (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)다익스트라는 “아직 확정되지 않은 노드 중 가장 가까운 노드는 더 짧아질 수 없다”는 성질을 이용합니다. 우선순위 큐에 {거리, 노드} 순서로 넣는 이유는 pair가 첫 원소부터 비교하기 때문이고, greater<>로 최소 힙을 만들어 가장 가까운 노드부터 꺼냅니다. 기본 priority_queue는 최대 힙이라 이 비교자를 빠뜨리면 가장 먼 노드부터 꺼내 오답이나 시간 초과가 납니다.
if (d > dist[u]) continue;는 성능상 필수입니다. 같은 노드가 더 짧은 거리로 여러 번 큐에 들어갈 수 있는데(C++ priority_queue에는 키 감소 연산이 없으므로), 이미 더 짧은 거리로 처리된 오래된 항목을 건너뛰지 않으면 간선을 반복해서 다시 훑어 최악의 경우 시간 초과가 납니다. 또 이 알고리즘은 음수 간선이 있으면 틀린 답을 냅니다. 확정한 노드가 나중에 음수 간선으로 더 짧아질 수 있기 때문이며, 이때는 벨만-포드를 씁니다. 가중치 합이 int를 넘을 수 있다면(간선 10^5개 × 가중치 10^9) dist를 long long으로, 초깃값을 LLONG_MAX 대신 1e18 같은 여유 있는 값으로 두는 것이 안전합니다. 도달할 수 없는 노드는 INT_MAX로 남으므로 출력할 때 따로 처리해야 합니다.
순열/조합 생성
문제: 모든 순열을 생성하라.
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();
}
}두 함수 모두 “선택 → 재귀 → 선택 취소”의 백트래킹 구조입니다. 순열은 start 위치에 올 원소를 뒤쪽 원소와 교환해 고르고, 재귀가 끝나면 다시 교환해 원래 배열로 되돌립니다. 되돌리는 swap을 빠뜨리면 다음 반복이 바뀐 배열에서 시작해 같은 순열이 중복되거나 일부가 빠집니다. 조합은 다음 재귀를 i + 1부터 시작해 이미 고른 수보다 큰 수만 고르므로 {1, 2}와 {2, 1}이 따로 나오지 않습니다.
교환 방식의 순열은 사전순이 아니고, 입력에 중복 값이 있으면 같은 순열을 여러 번 만듭니다. 사전순 출력이 필요하거나 중복을 제거해야 한다면 정렬한 뒤 do { ... } while (std::next_permutation(nums.begin(), nums.end()));를 쓰는 편이 간단하고 두 조건을 모두 만족합니다. n!은 n = 10에서 이미 약 363만, n = 12에서 약 4.8억이라 모든 순열을 저장하는 방식은 n이 10 안팎일 때만 가능합니다. 조건을 만족하지 않는 경로를 일찍 끊는 가지치기가 백트래킹 문제의 실제 핵심입니다. 자세한 기법은 백트래킹을 참고하세요.
코딩테스트 팁
입출력 최적화
// 빠른 입출력
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// 파일 입출력
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);sync_with_stdio(false)는 C++ 스트림과 C 표준 입출력(printf/scanf)의 동기화를 끄고, cin.tie(nullptr)는 cin으로 읽기 전마다 cout을 비우는 동작을 끕니다. 입력이 수십만 줄인 문제에서 이 두 줄만으로 시간 초과가 통과로 바뀌는 경우가 흔합니다. 대신 동기화를 끈 뒤에는 cin/cout과 scanf/printf를 섞어 쓰면 안 됩니다. 출력 순서가 뒤섞여 오답이 나는데, 로컬에서는 멀쩡해 보여 원인을 찾기 어렵습니다. 출력마다 endl을 쓰는 것도 매번 버퍼를 비워 느리므로 '\n'을 씁니다.
freopen은 로컬에서 입력 파일로 테스트할 때 편하지만, 제출 코드에 남아 있으면 채점 서버에서 파일을 찾지 못해 아무것도 읽지 못합니다. 아래 디버깅 매크로처럼 #ifdef LOCAL로 감싸 두는 것이 안전합니다.
자주 쓰는 템플릿
#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;
}<bits/stdc++.h>는 표준 헤더를 전부 포함하는 GCC(libstdc++) 전용 헤더라 채점 서버에서는 편하지만, MSVC나 macOS 기본 Clang(libc++)에서는 컴파일되지 않고 컴파일 시간도 늘어납니다. 대회용 템플릿으로만 쓰고 실무 코드에는 필요한 헤더만 포함하세요. 타입 별칭은 #define ll long long보다 using ll = long long;이 안전합니다. 매크로는 단순 문자열 치환이라 ll(x) 같은 표현이나 다른 식별자와 섞일 때 예상치 못하게 확장될 수 있기 때문입니다.
디버깅 매크로
#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;long long sum = a * b;처럼 결과만 long long에 담으면 해결되지 않습니다. a * b가 int끼리의 곱으로 먼저 계산되어 이미 오버플로가 난 뒤에 변환되기 때문입니다. 한쪽 피연산자를 먼저 long long으로 바꿔야 곱셈 자체가 64비트로 계산됩니다. int 범위는 약 ±21억(2.1 × 10^9)이라 10^5 × 10^5 같은 곱이나 10^5개의 10^9 합은 모두 넘칩니다. 부호 있는 정수 오버플로는 정의되지 않은 동작이라 음수가 나오는 대신 최적화에 따라 전혀 다른 결과가 나올 수도 있습니다.
실수 2: 배열 범위 초과
// ❌ 범위 체크 없음
if (grid[i+1][j] == 1) { ... }
// ✅ 범위 체크
if (i+1 < n && grid[i+1][j] == 1) { ... }&&는 왼쪽이 거짓이면 오른쪽을 평가하지 않으므로(단락 평가) 범위 검사를 반드시 왼쪽에 둡니다. vector의 operator[]는 범위를 검사하지 않아서 한 칸 넘어 읽어도 대부분 바로 크래시하지 않고 쓰레기 값을 읽습니다. 그래서 “틀렸습니다”와 “런타임 에러”가 입력에 따라 번갈아 나오는 불안정한 증상이 됩니다. 로컬에서 -fsanitize=address나 -D_GLIBCXX_DEBUG로 컴파일하면 범위 밖 접근을 바로 잡아 줍니다. 상하좌우 이동은 int dx[] = {1, -1, 0, 0} 배열과 반복문으로 쓰면 범위 검사를 한 곳에 모을 수 있습니다.
실수 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)으로 개선시간 초과는 알고리즘 자체보다 숨은 반복에서 나는 경우가 많습니다. 반복문 안에서 vector::erase(begin())나 string의 + 연결, find(선형 탐색)를 호출하면 겉보기에는 루프 하나지만 실제로는 O(n²)입니다. 함수에 vector<int> v처럼 값으로 넘기면 호출마다 전체 복사가 일어나고, 재귀 DFS에서 이 실수를 하면 호출 횟수만큼 배열이 복사됩니다. 매개변수는 const vector<int>&나 vector<int>&로 넘기는 습관을 들이세요. 처음 C++로 문제를 풀 때 흔히 겪는 일이, 로직은 맞는데 map의 operator[]로 존재 여부를 확인하다가 원소가 계속 추가되어 메모리 초과가 나는 경우입니다. 존재 확인은 count나 find, C++20이라면 contains로 해야 합니다.
FAQ
Q1: unordered_map을 썼는데 시간 초과가 나요.
A: 해시 충돌을 유도하는 입력(Codeforces 해킹에서 흔함)이나 잦은 재해시가 원인일 수 있습니다. 원소 수를 미리 알면 reserve로 재해시를 줄이고, 적대적 입력이 우려되면 난수 시드를 섞은 커스텀 해시를 쓰거나 map(최악 O(log n) 보장)으로 바꿔 보세요.
Q2: 재귀 풀이가 로컬에서는 되는데 제출하면 런타임 에러가 나요.
A: 재귀 깊이가 채점 서버의 스택 한도를 넘었을 가능성이 큽니다. 섬의 개수처럼 깊이가 입력 크기에 비례하는 DFS는 BFS나 명시적 스택으로 바꾸고, 지역 변수로 큰 배열을 선언했다면 전역이나 vector로 옮기세요.
Q3: 답이 int 범위를 넘는지 어떻게 판단하나요?
A: 최악의 경우를 곱해 보면 됩니다. 원소 수 × 최대 값, 경로 길이 × 최대 가중치가 약 2.1 × 10^9를 넘으면 long long이 필요합니다. 애매하면 누적 변수만이라도 long long으로 두는 편이 안전합니다.
Q4: 같은 알고리즘인데 Python 풀이는 통과하고 C++은 틀려요.
A: 대부분 오버플로입니다. Python 정수는 크기 제한이 없어 같은 로직이 그대로 통과하지만, C++에서는 중간 계산이 int 범위를 넘으면 조용히 잘못된 값이 됩니다. 곱셈과 누적 합의 타입을 먼저 확인하세요.