Level 3. 입국심사 도저히 이 문제가 왜 이분 탐색 문제인지 감이 안 잡혀서 찾아보았다. 이분 탐색 문제는 입력의 크기가 매우 큰데 하나의 답을 찾아야 하는 것이 특징이다. 포인트는 사람 수가 아닌, 시간을 중심으로 이분 탐색을 진행해 답을 찾는다는 것이었다. 가장 오래 걸리는 심사관에게 모두 심사를 받는 경우를 최악의 경우로 설정한다. 이분 탐색을 진행할 때마다 주어진 시간 동안 모든 사람이 심사를 받을 수 있는지 확인한다. 각 (주어진 시간 / 심사 시간)을 합한 값이 심사할 수 있는 사람의 수라는데 처음엔 왜 이렇게 되는지 이해가 되지 않았다. 하지만, 사람이 아니라 각 심사관을 중심으로 생각해보면 실제로 그렇다. #include #include #include using namespace s..

Level 2. 택배상자 스택을 활용한 간단한 시뮬레이션 문제다. 그냥 매번 보조 벨트에 넣고, 뺄 때는 보조 벨트에서만 빼면 된다. #include #include #include using namespace std; int solution(vector order) { int answer = 0; size_t n = order.size(); stack stck; for (int i = 1; i

Level 3. 합승 택시 요금 플로이드-워셜 알고리즘을 응용하는 문제다. 모든 점들 간의 최단 거리를 구해야 할 때 사용한다. 3중 for문을 이용하는 O(n³) 시간 복잡도 때문에, 정점의 개수가 200개 미만으로 적은 것이 특징이다. 초기화 시 ∞를 무조건 INT_MAX로 설정하면, 더할 때 음수가 돼버리므로 주의해야 한다. 우선 모든 점들 간의 최단 거리를 구한 후, (S → I 비용) + (I → A 비용) + (I → B 비용)이 S에서 I까지 합승 후 각자 집으로 간 비용이다. 이 값들의 최솟값을 구하면 된다. #include #include #include #define UNREACHABLE 19'900'000 using namespace std; int solution(int n, int..

set 자료구조나 lower_bound(), upper_bound() 함수에 사용자 정의 타입을 사용하기 위해서는 < 연산자를 오버로드 해주어야 한다. 하지만, 각 경우에 따라 오버로드 함수의 시그니처가 다르다. struct Item { int data; // set friend bool operator < (const Item& A, const Item& B) { return A.data < B.data; } // lower_bound friend bool operator < (const Item& left, int right) { return left.data < right; } // upper_bound friend bool operator < (int left, const Item& right) ..

Level 2. 카카오프렌즈 컬러링북 전형적인 완전 탐색 문제다. DFS가 깔끔해서 썼지만 BFS로 풀 수도 있다. #include #include #include using namespace std; int rDFS(unsigned i, unsigned j, int color, vector& picture) { if (picture.size()

Level 3. 기지국 설치 전파가 닿지 않는 구간들을 구해, 각 구간을 (2w + 1) 크기씩 채워주면(나누면) 된다. 기지국의 번호가 정렬된 상태로 주어지므로, 앞에서부터 구간을 구할 수 있다. #include #include #include using namespace std; int solution(int n, vector stations, int w) { int answer = 0; int start = 1; vector section; for (int st : stations) { section.emplace_back(st - w - start); start = st + w + 1; } if (start