hades

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

🥅 설계https://www.acmicpc.net/problem/1920 🔍 분석수의 개수가 최대 100000개이고, 찾으려는 수의 개수가 최대 100000개이므로, 순차 탐색을 할 경우, O(10^10)으로 시간 제한을 초과한다. 따라서, 이분 탐색을 활용한다. 👊 풀이 #include #include #include using namespace std; int n, m, target; vector numbers(100001); bool binary_search(int target){ int start = 0, end = n-1, mid; while (start target) { end = mid - 1; } } return false; } int main() { cin...

🥅 문제https://www.acmicpc.net/problem/1463 🔍 설계시간 제한이 0.15초이고, N이 최대 1000000이므로, 보통 1초 당 1억 번의 연산을 하기 때문에 재귀함수를 사용한다면, Ω(N^2)의 시간 복잡도로 시간 제한을 초과한다. N에서 시작하는 것이 아니라, 반대로 1에서 시작하여 문제에서 주어진 연산을 반대로 하여 다이나믹 프로그래밍으로 설계한다면, O(N)으로 해결할 수 있다. 👊 풀이#include #include #include using namespace std;int n, INF = 1e9+7;vector dp(1000001, INF);int main() { cin >> n; dp[1] = 0; for (int i=1; idp[i]는 i로부터 1을 만들기 ..

🥅 문제https://www.acmicpc.net/problem/1926 🔍 설계1로 이루어진 영역의 개수와 넓이를 계산해야 한다. 1로 구성된 어떤 칸에서 가로세로에 인접한 1을 계속해서 추가하여 하나의 영역을 구성해야 하므로, BFS를 사용하면 된다. 도화지를 구성하는 칸의 정보를 입력받는다. 한 칸씩 반복문을 통해 순회하면서, 1이라면 그 칸을 한 그림을 이루는 시작점으로 하여 한 그림의 넓이를 반환하는 bfs 함수를 실행한다.  방문 여부를 저장하는 visited 배열을 만들 수도 있으나, 공간 복잡도를 줄이기 위해 1이었던 칸을 방문하였으면 0으로 바꾸는 방식으로 작성하였다.  👊 풀이#include #include #include #include using namespace std;int..

🥅 문제https://www.acmicpc.net/problem/11047 🔍 설계K를 달성시키는 동전의 최소 개수를 구해야 하는데, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수라는 조건이 있으므로, 가치가 큰 동전부터 최대한 사용하는 그리디 문제라는 것을 파악할 수 있다. 👊 풀이#include #include #include #include using namespace std;int n, k, result = 0;vector coins(10);int main() { cin >> n >> k; for (int i=0; i> coins[i]; } for (int i=n-1; i>=0; i--){ result += k / coins[i]; k %= coins[i]; } cout

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.