C++ 알고리즘 문제풀이 | 코딩테스트 필수 문제 10선
이 글의 핵심
C++ 알고리즘 코딩테스트 필수 문제 10선을 다룹니다. Two Sum, 이진 탐색, 동적 프로그래밍, 그래프 탐색 등 실전에서 자주 출제되는 유형별 문제와 최적화된 C++ 풀이를 제공합니다. 시간복잡도 분석과 함께 STL 활용법을 익힐 수 있습니다.
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:
- 정렬, 탐색
- 그리디, DP
- 그래프 (BFS, DFS)
- 고급 (세그먼트 트리 등)
Q2: 문제를 못 풀겠어요!
A:
- 작은 예제로 시작
- 브루트포스부터 생각
- 패턴 찾기
- 비슷한 문제 찾기
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++)
- 컴파일러 경고를 최대로 켜고(
-Wall -Wextra등 팀 합의), Sanitizer(ASan/UBSan)로 미정의 동작을 조기에 잡습니다. - 최적화는 프로파일 결과를 본 뒤에 합니다.
- STL
<algorithm>사용 시 반복자 무효화·비교자 일관성을 함께 검토합니다.
실전 체크리스트 (C++)
- 경고·정적 분석에서 새로운 이슈가 없는가?
- 빈 범위·단일 원소 등 경계 조건을 테스트했는가?
이 글에서 다루는 키워드 (관련 검색어)
C++, 알고리즘, 코딩테스트, 문제풀이, PS 등으로 검색하시면 이 글이 도움이 됩니다.
관련 글
- 배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리
- 정렬 문제 풀이 | 코딩 테스트 정렬 패턴 완벽 정리
- DP 실전 문제 | 코딩 테스트 DP 문제 풀이 전략
- C++ 코딩테스트 팁 |
- C++ 코딩 테스트 |
심화 부록: 구현·운영 관점
이 부록은 앞선 본문에서 다룬 주제(「C++ 알고리즘 문제풀이 | 코딩테스트 필수 문제 10선」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.
내부 동작과 핵심 메커니즘
flowchart TD A[입력·요청·이벤트] --> B[파싱·검증·디코딩] B --> C[핵심 연산·상태 전이] C --> D[부작용: I/O·네트워크·동시성] D --> E[결과·관측·저장]
sequenceDiagram participant C as 클라이언트/호출자 participant B as 경계(런타임·게이트웨이·프로세스) participant D as 의존성(API·DB·큐·파일) C->>B: 요청/이벤트 B->>D: 조회·쓰기·RPC D-->>B: 지연·부분 실패·재시도 가능 B-->>C: 응답 또는 오류(코드·상관 ID)
- 불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
- 결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
- 경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
- 백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.
프로덕션 운영 패턴
| 영역 | 운영 관점 질문 |
|---|---|
| 관측성 | 요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가 |
| 안전성 | 입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가 |
| 신뢰성 | 재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가 |
| 성능 | 캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가 |
| 배포 | 롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가 |
| 용량 | 피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가 |
스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.
확장 예시: 엔드투엔드 미니 시나리오
앞선 본문 주제(「C++ 알고리즘 문제풀이 | 코딩테스트 필수 문제 10선」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.
- 입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
- 핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
- 실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
- 호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
- 부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.
handle(request):
ctx = newCorrelationId()
validated = validateSchema(request)
authorize(validated, ctx)
result = domainCore(validated)
persistOrEmit(result, idempotentKey)
recordMetrics(ctx, latency, outcome)
return result문제 해결(Troubleshooting)
| 증상 | 가능 원인 | 조치 |
|---|---|---|
| 간헐적 실패 | 레이스, 타임아웃, 외부 의존성, DNS | 최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검 |
| 성능 저하 | N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스 | 프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거 |
| 메모리 증가 | 캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납 | 상한·TTL·힙/FD 스냅샷 비교 |
| 빌드·배포만 실패 | 환경 변수, 권한, 플랫폼 차이, lockfile | CI 로그와 로컬 diff, 런타임·이미지 버전 핀 |
| 설정 불일치 | 프로필·시크릿·기본값, 리전 | 스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화 |
| 데이터 불일치 | 비멱등 재시도, 부분 쓰기, 캐시 무효화 누락 | 멱등 키·아웃박스·트랜잭션 경계 재검토 |
권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.
배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.