반응형 Programming/BOJ277 [C/C++] 백준 #3079 입국심사(이분탐색) 백준 온라인 저지 #3079 문제인 “입국심사” 문제는 다음과 같습니다.문제 개요• N개의 입국심사대가 있으며, 각 심사대마다 사람을 심사하는 데 걸리는 시간이 다릅니다.• M명의 사람이 입국심사를 받으려고 기다리고 있습니다.• 모든 사람이 입국심사를 마치는 데 걸리는 최소 시간을 구하는 문제입니다.입력1. 첫째 줄에 N(심사대의 개수)와 M(심사를 받아야 할 사람 수)이 주어집니다.2. 둘째 줄부터 N개의 줄에 각 심사대에서 한 명을 심사하는 데 걸리는 시간이 주어집니다.출력• 모든 사람이 입국심사를 마치는 데 걸리는 최소 시간을 출력합니다.해결 방법• 이분 탐색을 활용하여 최소 시간을 구하는 것이 핵심입니다.• 특정 시간을 기준으로 모든 사람이 심사를 받을 수 있는지 판단하며, 조건을 만족하는 최소 .. 2024. 11. 12. [C/C++] 백준 #3055 탈출(너비 우선 탐색) 백준 온라인 저지 문제 #3055는 “탈출”이라는 제목의 문제로, 주어진 2차원 맵에서 고슴도치가 물을 피하면서 동굴로 탈출하는 경로를 찾는 시뮬레이션 문제입니다. 문제의 주요 포인트는 다음과 같습니다.문제 설명1. 맵 구성: 고슴도치는 S로, 동굴은 D로 표시되어 있습니다. 물은 *로 표시되며 매 시간마다 상하좌우로 확산합니다. 빈 공간은 .로 표현됩니다.2. 목표: 고슴도치는 물이 찰 예정인 칸을 피하면서 최소한의 이동 시간으로 동굴(D)에 도달해야 합니다.3. 제약 조건:• 고슴도치는 한 번에 상하좌우로 한 칸씩 움직일 수 있습니다.• 물은 매 시간마다 고슴도치보다 먼저 확산되어 고슴도치의 경로를 막을 수 있습니다.4. 출력 조건: 고슴도치가 동굴로 탈출할 수 있는 최소 시간을 출력하며, 탈출이 불.. 2024. 11. 7. [C/C++] 백준 #3036 링(수학) 이번 문제는 최대공약수 개념만 이해하면 어렵지 않게 풀 수 있습니다. 반지름의 길이 비율의 역수배로 다음 링은 회전을 하게 됩니다.예를 들어서 첫번째 링의 반지름이 3이고, 두번째 링의 반지름이 6이라면, 두번째 링은 첫번째 링보다 반지름이 2배이므로, 회전수는 1/2가 됩니다. 이것을 이해한다면, 어렵지 않게 문제를 풀 수 있습니다. 이 C/C++ 프로그램은 Baekjoon 문제 #3036 “Ring”에 대한 솔루션입니다. 이 문제는 여러 개의 톱니바퀴가 있을 때 첫 번째 톱니바퀴의 회전수를 기준으로 다른 톱니바퀴의 회전수를 간단한 분수로 나타내는 문제입니다. 코드를 단계별로 설명하겠습니다. //------------------------------------------------// bae.. 2024. 10. 28. [C/C++] 백준 #3013 부분 수열의 중앙값(누적 합) 문제를 푼지는 꽤 되었는데, 지금에 작성하라고 한다면, 이진검색을 사용하지 않고, t 값에 대한 테이블값을 별도로 만들어서 저장하는 방식을 택했을 듯 합니다. 데이터의 전체 갯수가 100,000이니까, 누적합 테이블을 만들 때에는 200,000개 정도의 추가 공간을 만들면 됩니다. 그러면 정렬 후 이진 검색하는 시간 비용을 줄일 수 있습니다. 정렬 시간 복잡도는 \(O(N \log N)\)이고, 이진검색하는 비용도 \(O(N \log N)\)이 되니까요. 문제는 다음 링크에 있습니다.https://www.acmicpc.net/problem/3013 이 문제는 주어진 배열에서 특정 값 b를 기준으로 좌우의 수들을 분석하고, 이 기준을 중심으로 하는 부분 배열의 개수를 세는 문제입니다. 우선 문제의 .. 2024. 9. 30. [C/C++] 백준 #2981 검문(유클리드 호제법) 백준 온라인 저지 문제 2981번 "검문"을 해결하기 위해서는 주어진 수들로부터 차이들의 최대공약수를 구하고, 그 공약수의 약수들을 찾아 출력하는 것입니다. 최대공약수를 찾을 때에는 유클리드 호제법을 이용하면 됩니다. 문제의 링크는 다음과 같습니다.https://www.acmicpc.net/problem/2981 ### 주요 함수 및 흐름 설명#### 1. **`gcd(int a, int b)` 함수:** - 두 수의 **최대공약수(GCD, Greatest Common Divisor)**를 구하는 함수입니다. - 유클리드 호제법(Euclidean Algorithm)을 사용하여 `a`와 `b`의 GCD를 구합니다. - **유클리드 호제법**은 다음의 과정을 반복하는 알고리즘입니다: 1.. 2024. 9. 20. [C/C++] 백준 #2887 행성 터널(크루스칼 알고리즘) 이번 문제는 크루스칼 알고리즘을 이용해서 풀었습니다. https://www.acmicpc.net/problem/2887 하지만, V개의 행성을 모두 연결한다면, \(V(V-1)\)만큼의 간선이 생기므로, 정렬을 할 때, 주어진 V값에 대해서 느려질 수 있습니다.간선의 갯수는 최소 비용 신장 트리(Minimum Spanning Tree)를 프림 알고리즘을 이용하든, 크루스칼 알고리즘을 이용하든 모두 시간 복잡도가 주어진 V값의 최대치라면, 시간초과가 됩니다. \(E = V(V-1)\)이 된다면, 프림 알고리즘 상에서는 \(O(E \log V) = O(V^2 \log V)\), 크루스칼 알고리즘 상에서는 \(O(E \log E) = O(V^2 \log V\) 형태가 되겠죠. 물론 프림 알고리즘을 구현할 .. 2024. 8. 25. 이전 1 2 3 4 ··· 47 다음 728x90
