코딩 테스트는 프로그래밍 능력을 평가하기 위해 주어진 문제를 해결하는 과정이다. 일반적으로 알고리즘, 자료구조, 수학적 사고, 문제 해결 능력을 측정하며 주어진 시간 내에 코드로 문제를 해결해야 한다. 온라인 플랫폼을 통해 진행되거나 대면 시험 형태로 이루어질 수 있으며 기업에서는 이를 통해 지원자의 기술적 역량과 논리적 사고를 평가한다. 코딩 테스트 문제는 배열, 문자열, 그래프 탐색, 정렬, 동적 프로그래밍, 또는 기타 컴퓨터 과학 개념을 활용한 문제로 구성되며, 효율성과 정확성이 중요하다.
코딩 테스트에 주로 이용되는 언어는 C++과 Python이다. C++과 파이썬은 각각의 장단점이 뚜렷하다. C++은 빠른 실행 속도와 세밀한 메모리 관리, STL(Standard Template Library)을 활용한 강력한 자료구조 및 알고리즘 지원으로 시간 복잡도가 중요한 문제에 유리하다. 특히 벡터, 맵, 우선순위 큐 등의 STL은 효율적인 구현을 돕는다. 그러나 C++은 상대적으로 복잡한 문법과 엄격한 타입 체계를 가져 초보자에게는 진입 장벽이 높고, 코드 작성 및 디버깅 시간이 길어질 수 있다. 반면, 파이썬은 간결하고 읽기 쉬운 문법과 방대한 내장 라이브러리로 빠른 프로토타이핑과 직관적인 코딩이 가능하다. 리스트와 딕셔너리 같은 기본 자료구조가 강력하며, 특히 문자열 처리와 수학 계산 문제에 적합하다. 하지만 파이썬은 인터프리터 언어로 실행 속도가 느려 시간 제한이 빡빡한 문제에서는 불리할 수 있다. 따라서 C++은 최적화가 중요한 고난도 문제에, 파이썬은 개발 속도와 가독성이 요구되는 문제에 적합한 선택지로 활용된다.
1. 코딩 테스트 팁
코딩 테스트에서 성공적인 문제 해결을 위해서는 단순히 코드를 작성하는 것뿐만 아니라, 문제 이해, 계획, 구현, 테스트 전반에 걸친 체계적인 접근이 중요하다. 아래는 제시된 팁을 더욱 자세히 설명한 내용이다.
1) 테스트 케이스에 집중
테스트 케이스는 코드가 모든 상황에서 올바르게 작동하는지 검증하는 데 매우 중요하다. 특히, 아래와 같은 다양한 케이스를 고려해야 한다.
a. 기본 테스트 케이스
문제에서 제공된 기본 입력과 출력에 대한 검증을 먼저 수행한다. 기본 케이스가 성공해야 더 복잡한 케이스로 넘어갈 수 있다.
b. 엣지 케이스
입력의 경계 조건을 테스트하라. 예를 들어:
- 배열의 크기가 0일 때.
- 최대 크기 또는 최소 크기일 때.
- 값이 최대/최소일 때 (INT_MAX, INT_MIN).
- 중복 요소, 동일 값 등이 입력될 때.
c. 예외 케이스
잘못된 입력, 의도하지 않은 상황에서도 코드가 제대로 작동하거나 적절히 실패해야 한다.
- 예: 분모가 0인 상황, 배열 인덱스가 범위를 벗어날 때 등.
d. 성능 테스트 케이스
입력 크기가 매우 클 때 시간과 메모리 효율성을 검증한다.
- 예: 백만 개의 요소로 구성된 배열.
- 최대한의 연산이 필요한 경우(최악의 경우 시간 복잡도).
// 예를 들어 배열에서 최대값을 찾는 문제
vector<int> testCase1 = {1, 2, 3}; // 기본 테스트 케이스
vector<int> testCase2 = {1000000000}; // 최대 값 테스트
vector<int> testCase3 = {}; // 빈 배열 (엣지 케이스)
vector<int> testCase4 = {INT_MIN, INT_MAX}; // 경계값 테스트
2) 문제를 읽고 계획
문제 이해와 계획은 시간을 절약하고 실수를 줄이는 데 필수적이다. 아래 단계를 거쳐야 한다.
a. 문제의 의도를 정확히 파악하라
문제에서 무엇을 묻고 있는지, 어떤 출력이 요구되는지를 명확히 이해하라. 잘못된 가정을 하면 문제를 잘못 해결할 수 있다.
- 문제의 입력 조건, 출력 형식을 확인하라.
- 문제를 분해하고 논리적으로 해결 방식을 설계하라.
b. 예제 분석
주어진 예제 입력과 출력을 철저히 분석하고, 어떤 로직이 필요한지 확인하라. 특히 예제 간의 차이점을 분석하며 공통 패턴을 찾아라.
c. 알고리즘 계획
다음 사항을 염두에 두고 알고리즘을 설계하라.
- 주어진 입력 조건에 맞는 데이터 구조를 결정.
- 시간 복잡도와 공간 복잡도를 고려.
- 예외 처리 방안을 포함.
3) 시간 복잡도 분석
알고리즘이문제를 해결하는 데 걸리는 시간을 분석하는 것은 코딩 테스트에서 필수적이다. 테스트 입력의 크기와 알고리즘의 시간 복잡도가 적절히 맞아야 한다.
a. 입력 크기 확인
문제에서 제공된 입력 크기를 읽고, 적절한 알고리즘을 선택하라.
- 입력 크기가 작다면 단순한 완전 탐색(브루트 포스)도 가능.
- 입력 크기가 매우 크다면 효율적인 알고리즘(예: 이분 탐색, 동적 프로그래밍 등)을 선택해야 한다.
b. 시간 복잡도 계산
알고리즘의 반복문, 재귀 호출 등을 분석하여 실행 시간의 증가 속도를 파악하라.
- O(1): 상수 시간 (예: 배열의 특정 인덱스 접근)
- O(log N): 로그 시간 (예: 이분 탐색)
- O(N): 선형 시간 (예: 배열 전체 탐색)
- O(N^2): 이차 시간 (예: 이중 루프)
- O(2^N): 지수 시간 (예: 모든 부분집합 계산)
c. 공간 복잡도 분석
사용하는 데이터 구조의 메모리 사용량을 고려하라.
4) 단위 테스트
단위 테스트를 활용하면 코드의 작은 부분을 독립적으로 검증할 수 있다. 코딩 테스트 중에도 함수 단위로 구현과 테스트를 병행하면 디버깅 시간을 줄일 수 있다.
a. 작은 함수로 분리
- 문제를 해결하는 로직을 작은 함수로 분리하여 각각을 테스트하라.
- 각 함수는 하나의 작업만 수행하도록 설계하라.
b. 테스트 주도 개발
- 함수 단위로 다양한 입력값을 넣고, 예상 결과와 실제 결과를 비교하라.
디버깅
(1) 표준 입력 설정
- 코딩테스트는 표준 입력을 사용하는 경우가 많으므로, 파일 입력/출력을 연습한다
#include <iostream>
#include <fstream>
using namespace std;
int main() {
ifstream input("input.txt");
ofstream output("output.txt");
int n;
input >> n;
output << "Number: " << n << endl;
return 0;
}(2) 테스트 케이스 자동 생성
- 다양한 테스트 케이스를 생성하여 코드의 안정성을 검증
#include <iostream>
#include <cstdlib>
using namespace std;
int main() {
srand(time(0));
for (int i = 0; i < 10; ++i) {
cout << rand() % 100 << " ";
}
return 0;
}
범주변수명 예시설명
| 일반적인 변수명 | temp, result, data, value, count, index, flag | 임시값, 결과값, 데이터, 상태 확인 등 |
| 수학/알고리즘 | sum, avg, min, max, x, y, z, num, diff, step | 합계, 평균, 최소/최대값, 좌표 등 |
| 데이터 구조 | arr, list, queue, stack, node, tree, graph, map, dict, set, key, value | 배열, 리스트, 노드, 맵, 딕셔너리 등 |
| 날짜/시간 | date, time, timestamp, start_time, end_time, current_time, elapsed | 날짜와 시간 정보 |
| 상태/플래그 | is_valid, is_active, is_done, status, state, mode, type | 상태, 모드, 유효성 확인 등 |
| 파일/네트워크 | path, file, filename, url, response, request, buffer, socket | 파일 경로, 요청/응답, 네트워크 관련 |
| 루프 관련 | i, j, k, iter, item, current, next, prev | 반복문에서 사용되는 변수 |
| 머신러닝/데이터 | X, y, train, test, feature, label, model, loss, accuracy, epoch, weights | 데이터, 모델, 훈련/테스트 데이터 등 |
| Unity/게임 개발 | player, enemy, position, rotation, speed, health, score, object, collision | 게임 객체 및 속성 관련 |
| 웹 개발 | user, session, token, request, response, html, css, script, form | 웹 요청, 응답, 사용자 정보 등 |
2. 필수 알고리즘 정리
1. 깊이 우선 탐색 (Depth-First Search, DFS)
DFS는 그래프나 트리 구조를 탐색하는 기본 알고리즘입니다. 한 노드에서 출발해 더 이상 갈 수 없을 때까지 깊게 탐색하고, 더 이상 진행할 수 없을 때 이전 단계로 돌아와 다른 경로를 탐색합니다. 재귀나 스택을 사용하여 구현할 수 있으며, 주로 연결 요소 찾기, 사이클 탐지 등에 사용됩니다.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<vector<int>> graph;
vector<bool> visited;
void dfs_stack(int start) {
stack<int> st;
st.push(start);
while(!st.empty()) {
int node = st.top();
st.pop();
if(visited[node]) continue; // 이미 방문한 노드 건너뛰기
visited[node] = true;
cout << node << " "; // 현재 노드 처리
// 인접 노드를 스택에 추가 (역순으로 추가하면 원래 순서대로 탐색 가능)
for(auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) {
int next = *it;
if(!visited[next]) {
st.push(next);
}
}
}
}
int main() {
int n = 5; // 노드 수
graph.resize(n);
visited.resize(n, false);
// 그래프 간선 추가 (예시)
graph[0] = {1, 2};
graph[1] = {0, 3, 4};
graph[2] = {0};
graph[3] = {1};
graph[4] = {1};
cout << "스택 기반 DFS 탐색 결과: ";
dfs_stack(0); // 0번 노드부터 탐색 시작
cout << endl;
return 0;
}
2. 너비 우선 탐색 (Breadth-First Search, BFS)
BFS는 그래프의 최단 경로 탐색에 유용한 알고리즘으로, 시작 노드로부터 거리가 가까운 순서대로 탐색합니다. 큐를 사용해 구현하며, 한 단계씩 넓게 퍼져나가면서 방문하지 않은 인접 노드를 탐색합니다. 최단 거리 문제, 레벨 탐색 등에 활용됩니다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> graph;
vector<bool> visited;
void bfs(int start) {
queue<int> q;
visited[start] = true;
q.push(start);
while(!q.empty()) {
int node = q.front();
q.pop();
cout << node << " "; // 현재 노드 처리
for (int next : graph[node]) {
if (!visited[next]) {
visited[next] = true;
q.push(next);
}
}
}
}
int main() {
int n = 5; // 노드 수
graph.resize(n);
visited.resize(n, false);
// 그래프 간선 추가 (예시)
graph[0] = {1, 2};
graph[1] = {0, 3, 4};
graph[2] = {0};
graph[3] = {1};
graph[4] = {1};
cout << "BFS 탐색 결과: ";
bfs(0); // 0번 노드부터 탐색 시작
cout << endl;
return 0;
}
3. 다익스트라 알고리즘 (Dijkstra's Algorithm)
다익스트라 알고리즘은 가중치가 있는 그래프에서 한 시작점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 우선순위 큐를 사용하여 현재까지의 최단 거리를 업데이트하며, 시간 복잡도는 O(E log V)입니다.
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
typedef pair<int, int> pii;
const int INF = numeric_limits<int>::max();
void dijkstra(int start, const vector<vector<pii>>& graph, vector<int>& dist) {
priority_queue<pii, vector<pii>, greater<pii>> pq;
dist[start] = 0;
pq.push({0, start});
while(!pq.empty()) {
int distance = pq.top().first;
int node = pq.top().second;
pq.pop();
if(distance > dist[node]) continue;
for(auto& edge : graph[node]) {
int next = edge.first;
int weight = edge.second;
if(dist[next] > dist[node] + weight) {
dist[next] = dist[node] + weight;
pq.push({dist[next], next});
}
}
}
}
int main() {
int V = 5; // 정점 수
vector<vector<pii>> graph(V);
// graph[u].push_back({v, w}); 형식으로 간선 정보 추가
graph[0].push_back({1, 10});
graph[0].push_back({2, 3});
graph[1].push_back({2, 1});
graph[1].push_back({3, 2});
graph[2].push_back({1, 4});
graph[2].push_back({3, 8});
graph[2].push_back({4, 2});
graph[3].push_back({4, 7});
graph[4].push_back({3, 9});
vector<int> dist(V, INF);
int start = 0;
dijkstra(start, graph, dist);
cout << "최단 거리 결과:" << endl;
for(int i = 0; i < V; ++i) {
cout << "노드 " << start << "에서 노드 " << i << "까지: ";
if(dist[i] == INF) cout << "도달 불가";
else cout << dist[i];
cout << endl;
}
return 0;
}
4. 배열 돌리기
이 문제를 효율적으로 해결하기 위한 핵심 아이디어는 주어진 배열을 여러 개의 “레이어(layer)”로 분리하고, 각 레이어를 독립적으로 회전시키는 것입니다. 가장 바깥쪽 둘레부터 시작하여 안쪽으로 점점 들어가면서 배열을 레이어별로 나누면, 복잡한 전체 좌표 계산 없이도 각 레이어만 따로 회전시켜 전체 배열을 쉽게 회전시킬 수 있습니다.
먼저, 배열의 크기 N×MN \times M에서 가능한 레이어의 수를 결정합니다. 이는 배열의 최소 차원 min(N,M)\min(N, M)을 2로 나눈 값으로 구할 수 있습니다. 이유는 각 레이어가 적어도 두 줄 이상의 행과 열로 구성되어야 하기 때문입니다. 예를 들어, int layers = min(N, M) / 2;와 같이 레이어 수를 계산할 수 있습니다.
각 레이어에 대해 처리 과정은 다음과 같습니다. 먼저 해당 레이어에 속하는 모든 원소를 추출하여 순서대로 하나의 리스트나 벡터에 저장합니다. 이때 추출 순서는 상단 가로 변 → 우측 세로 변 → 하단 가로 변 → 좌측 세로 변의 순서로 진행하여, 하나의 연속된 리스트를 만듭니다. 그런 다음, 리스트의 총 원소 개수를 len이라고 할 때, 주어진 회전 횟수 RR을 R mod len으로 줄여 불필요한 반복을 피합니다. 실제 회전은 이 값을 이용해 리스트를 앞에서부터 kk만큼 뒤로 옮기거나 마지막에서부터 kk만큼 앞으로 옮기는 방식으로 수행합니다. 여기서 k=Rmod lenk = R \mod len입니다.
회전이 완료된 리스트는 원래의 레이어 위치에 다시 배치됩니다. 상단 가로 변부터 시작하여 우측 세로 변, 하단 가로 변, 좌측 세로 변 순으로 회전된 원소들을 차례대로 채워 넣습니다. 이 과정을 모든 레이어에 대해 반복하면, 배열 전체가 원하는 만큼 회전된 상태가 됩니다.
마지막으로, 회전이 완료된 배열을 출력하면 문제의 답을 얻을 수 있습니다. 이러한 접근 방식은 배열을 레이어별로 분리하여 독립적으로 처리하므로, 복잡한 인덱스 계산을 줄이고 효율적인 알고리즘 구현이 가능하게 합니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M, R;
cin >> N >> M >> R;
vector<vector<int>> arr(N, vector<int>(M));
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
cin >> arr[i][j];
int layers = min(N, M) / 2;
for (int layer = 0; layer < layers; ++layer) {
int top = layer;
int left = layer;
int bottom = N - layer - 1;
int right = M - layer - 1;
// 레이어의 원소들을 추출
vector<int> elems;
// 상단 가로
for (int j = left; j <= right; ++j) elems.push_back(arr[top][j]);
// 우측 세로
for (int i = top + 1; i <= bottom - 1; ++i) elems.push_back(arr[i][right]);
// 하단 가로
for (int j = right; j >= left; --j) elems.push_back(arr[bottom][j]);
// 좌측 세로
for (int i = bottom - 1; i >= top + 1; --i) elems.push_back(arr[i][left]);
// 회전 조정: R번 회전 시 실제 필요한 이동 수 계산
int len = elems.size();
int rotations = R % len;
// 리스트를 회전시키기 위해 범위 뒤로 이동
rotate(elems.begin(), elems.begin() + rotations, elems.end());
// 회전된 원소들을 다시 배열에 배치
int idx = 0;
// 상단 가로
for (int j = left; j <= right; ++j) arr[top][j] = elems[idx++];
// 우측 세로
for (int i = top + 1; i <= bottom - 1; ++i) arr[i][right] = elems[idx++];
// 하단 가로
for (int j = right; j >= left; --j) arr[bottom][j] = elems[idx++];
// 좌측 세로
for (int i = bottom - 1; i >= top + 1; --i) arr[i][left] = elems[idx++];
}
// 결과 출력
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
cout << arr[i][j] << " ";
}
cout << "\n";
}
return 0;
}'Development > Coding Test' 카테고리의 다른 글
| Coding Test [2]: SQL 프로그래밍 (SQL Programming) (0) | 2025.01.11 |
|---|---|
| Coding Test [1] : C++ 프로그래밍 (C++ Programming) (0) | 2024.12.30 |