개발일지

문제설명 입출력 예제 개념 이 문제는 모든 국가가 연결되어 있고, 모든 비행기 티켓 가격이 동일하다는 특성 때문에 최소 신장 트리 문제처럼 보일 수 있다. 하지만 여기서 중요한 점은 상근이가 한 국가에서 다른 국가로 이동할 때, 필요에 따라 다른 국가를 거쳐갈 수 있다는 것이다. 이는 실질적으로 모든 비행기를 직접 타고 갈 필요가 없다는 것을 의미한다. 따라서 이 문제의 답은 MST 알고리즘을 사용하지 않고도 간단히 구현할 수 있다. 상근이가 모든 국가를 여행하기 위해서는 전체 국가의 수 - 1 만큼의 비행기를 타면 된다. 왜냐하면 한 국가에서 출발해 모든 다른 국가를 방문하려면, 국가의 수보다 비행기를 하나 적게 타면 되기 때문이다. 풀이 #include using namespace std; int m..

문제설명 입출력 예제 개념 이 문제는 각 숫자를 입력받을 때마다 중간값을 계산하고 출력하는 것이다. 단순하게 배열에 값을 추가하고, 매 반복마다 중앙값을 출력하려면 시간 복잡도가 O(N^2)이 되어 시간 초과가 발생할 수 있다. 이를 해결하기 위한 최적화된 알고리즘이 두 힙 알고리즘이다. 두 힙 알고리즘은 최대 힙과 최소 힙을 이용한다. 이 방식에서는 현재까지 입력받은 수 중 중간값 이하의 수를 최대 힙에, 중간값 초과의 수를 최소 힙에 저장한다. 따라서 중간값은 항상 최대 힙의 루트에 위치하게 된다. 이 알고리즘의 각 연산은 로그 시간 복잡도를 가지므로, 전체 시간 복잡도는 입력의 개수에 비례하는 선형 로그 시간 복잡도 O(N logN)를 가지게 된다. 이렇게 해서 큰 입력에 대해서도 효율적으로 문제를..

문제설명 입출력 예제 개념 최소 비용을 통해 목표를 달성하는 그리드 알고리즘을 활용하는 문제다. 이 문제의 핵심 아이디어는 가장 낮은 기름값을 갖는 주유소를 찾아, 그곳에서 기름을 충전하는 것이다. 따라서 현재 위치에서 다음 도시로 이동하기 위해 필요한 기름을 충전하는데, 현재 주유소의 기름 가격과 다음 주유소의 기름 가격을 비교하여 최소 비용을 항상 유지하게 기름값을 갱신하면 된다. 풀이 #include #include using namespace std; int main() { long long N; cin >> N; vector station(N), road(N-1); for (int i = 0; i > road[i]; for (int i = 0; i < N; ++..

문제설명 입출력 예제 개념 각 사람이 돈을 인출하는 데 필요한 시간 합의 최솟값을 출력하는 문제다. 대표적인 그리디 알고리즘으로 효율적으로 해결할 수 있는 문제로서, 실행 시간이 가장 짧은 프로세스부터 우선적으로 처리하는 최단 작업 우선 스케줄링 방식을 이용하면 된다. 여기서 돈을 인출하는데 걸리는 시간을 작업으로 보고, 이 작업들을 가장 짧은 것부터 처리하면 모든 사람이 돈을 인출하는데 필요한 최소 시간을 구할 수 있다. 풀이 #include #include #include using namespace std; int main() { int N; cin >> N; vector v(N); int* sum = new int[N]; for (int i = 0; i > v[i]; s..

문제설명 입출력 예제 개념 이 문제는 회의 시간이 겹치지 않도록 하면서 동시에 가능한 한 많은 수의 회의를 배정하는 문제다. 이를 해결하는 방법 중 하나는 먼저 회의들을 종료 시간 기준으로 오름차순 정렬하는 것이다. 그리고, 가장 먼저 끝나는 회의를 선택한 후, 이전에 선택한 회의와 시간이 겹치지 않는 회의 중 가장 빨리 끝나는 회의를 다음으로 선택하는 것이다. 이러한 방식을 반복함으로써 가능한 많은 수의 회의를 배정할 수 있다. 풀이 #include #include #include using namespace std; int main() { int N, n, k, count = 1; cin >> N; vector v(N); 회의의 수 N, 그리고 회의의 시작과 끝에 대한 입력을 초기화할 변수 n, k,..

문제설명 입출력 예제 개념 K원을 만드는데 필요한 최소한의 동전 개수를 구하는 문제다. 가장 가치가 큰 동전부터 사용하는 것이 최선의 서택이므로, 이러한 선택을 통해 가장 적은 동전을 사용하여 주어진 금액을 만들 수 있는 최적의 해답을 찾을 수 있다. 즉, 그리디 알고리즘을 사용하여 문제를 효율적으로 풀 수 있다. 풀이 #include #include using namespace std; int main() { int N, K, n, answer = 0; cin >> N >> K; vector v(N); for (int i = 0; i > v[i]; for (auto it = v.rbegin(); it != v.rend(); ++it) { if (*it < K) { answer..

문제설명 입출력 예제 개념 문제의 목표는 주어진 문자열에서 특정 '폭발' 문자열을 제외하고 출력하는 것이다. 이를 해결하기 위해 입력 문자열에서 특정 문자열을 식별하고 삭제하는 과정이 필요하다. 이러한 과정은 문자열을 찾는 작업에서 O(n)의 시간 복잡도와 특정 문자열을 삭제한 후 남은 요소들을 이동시키는 작업에서 O(n)의 시간 복잡도를 갖게 된다. 따라서 두 연산을 합치면 전체 알고리즘의 최악의 경우 시간 복잡도가 O(n^2)이 되므로, 큰 입력에 대해 비효율적이라는 결론을 내릴 수 있다. 이를 해결하는 가장 효과적인 방법은 스택을 사용하는 것이다. 폭발 문자열의 마지막 문자와 현재 입력받은 문자를 비교하여, 완전히 일치할 경우 해당 문자열을 제거하는 방식으로 진행하면 된다. 풀이(1) 스택 활용 #..

문제설명 입출력 예제 개념 우선순위 큐의 정렬 순서를 직접 지정하면 풀 수 있는 문제다. 구조체를 이용하여 연산자를 오버로딩하여도 되고, 단순히 비교 함수를 인자로 추가해도 된다. 풀이 #include #include #include using namespace std; bool abs_operator(int a, int b) { return abs(a) == abs(b) ? a > b : abs(a) > abs(b); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, n; priority_queue pq(abs_operator); cin >> N; while (N--) { cin >> n; if (n == 0) { if (pq.e..

문제설명 입출력 예제 개념 지난 게시글인 최대 힙 문제처럼 우선순위 큐를 이용하여 풀면 쉽게 해결할 수 있다. 즉, 우선순위 큐를 최소 힙으로 정렬하면 된다. 풀이 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, n; priority_queue pq; cin >> N; while (N--) { cin >> n; if (n == 0) { if (pq.empty()) printf("0\n"); else { printf("%d\n", pq.top()); pq.pop(); } } else pq.push(n); } }

문제설명 입출력 예제 개념 주어진 문제는 우선순위 큐의 기본적인 연산을 이해하고 있는지 묻는 문제다. 따라서 우선순위 큐를 최대 힙으로 정렬한 후, 문제의 요구 사항에 맞게 입출력을 조절하면 풀 수 있다. 풀이 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, n; priority_queue pq; cin >> N; while (N--) { cin >> n; if (n == 0) { if (pq.empty()) printf("0\n"); else { printf("%d\n", pq.top()); pq.pop(); } } else pq.push(n); } } 특이 사항..