반응형 Programming456 [C/C++] 백준 #3036 링(수학) 이번 문제는 최대공약수 개념만 이해하면 어렵지 않게 풀 수 있습니다. 반지름의 길이 비율의 역수배로 다음 링은 회전을 하게 됩니다.예를 들어서 첫번째 링의 반지름이 3이고, 두번째 링의 반지름이 6이라면, 두번째 링은 첫번째 링보다 반지름이 2배이므로, 회전수는 1/2가 됩니다. 이것을 이해한다면, 어렵지 않게 문제를 풀 수 있습니다. 이 C/C++ 프로그램은 Baekjoon 문제 #3036 “Ring”에 대한 솔루션입니다. 이 문제는 여러 개의 톱니바퀴가 있을 때 첫 번째 톱니바퀴의 회전수를 기준으로 다른 톱니바퀴의 회전수를 간단한 분수로 나타내는 문제입니다. 코드를 단계별로 설명하겠습니다. //------------------------------------------------// bae.. 2024. 10. 28. [C/C++] 프로젝트 오일러 #86 Cuboid Route(Brute Force) 난이도는 35%의 문제이지만, 단순 방법으로 처리하면 그래도 적당한 시간에 해답을 찾을 수 있습니다. 문제는 각 모서리의 길이가 정수인 직육면체의 대척점 길이가 정수가 되는 경우를 찾는 것이죠. \(W \times H \times D\) 형태에서 대척점의 길이는 \( \sqrt{ W^2 + H^2 + D^2 } \)이 됩니다. 이것이 정수가 되기 위해서는 \( W^2 + H^2 + D^2 \)이 제곱수여야 합니다. 수학적인 방법도 존재하겠죠. 피타고라스 수를 연결하면 될 듯 합니다. 3-4-5 와 5-12-13 은 연결이 됩니다. 즉, \(3^2 + 4^2 + 12^2\)은 제곱수가 될 수 있는 것이죠. 문제의 출처는 다음과 같습니다.https://projecteuler.net/problem=86 제가.. 2024. 10. 18. [C/C++] 프로젝트 오일러 #85 Counting Rectangles(Brute Force) 이번 문제는 난이도는 15% 정도입니다.문제 자체가 어려운 것은 아니어서, 보통은 단순한 방법으로 풀어보고, 알고리즘 효율을 꾀하는 편이긴 하지만, 여기서는 단순한 방법으로 문제를 풀어보았습니다. 문제의 출처는 다음과 같습니다.https://projecteuler.net/problem=85 이 프로그램은 Project Euler의 문제 85를 해결하기 위한 C/C++ 프로그램입니다. 문제의 목표는 주어진 제한 조건 하에서 사각형의 개수를 계산하는 것입니다. 이 코드는 특정 사각형 수와 목표 값 사이의 오차가 가장 작은 직사각형의 크기를 찾으려고 합니다. //------------------------------------------------// Project Euler #85 - Counting.. 2024. 10. 8. [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 ··· 3 4 5 6 7 8 9 ··· 76 다음 728x90 반응형
