광's의 IT 이야기

Algorithm 검색 결과

해당 글 214건

[백준] 알고리즘 1929번 - 소수 구하기 문제

N이 소수인지 판별하는데 시간복잡도는 O(루트N) 이다. 이 문제의 경우 1부터 백만까지의 소수가 있는지 없는지 저장해두고 M과 N사이의 소수를 출력해줘야 한다. N이 백만인 경우 시간복잡도는 루트n = 1000 각각의 n의 소수를 구하기 위해서는 1000이 걸리고 N개의 시간복잡도를 계산하면 1000000*1000 = 많은 시간이 걸린다. 이런 시간초과를 해결하기 위해서 에라토스테네스의 체(1부터 N까지의 모든 범위의 소수를 구하기 위해서)를 사용한다. 2,3,4,5,6,7,8,9,10 * ** * **~~~~~~ 2의 배수의 숫자를 제거한다. 3의 배수의 숫자를 제거한다. 5의 배수의 숫자를 제거한다. 쭉 백만까지 진행한다. 중복된 공배수의 숫자를 제거하기 위해서 이중포문의 j+=i 를 이용하여 공배..

Algorithm 2020. 12. 25. 00:33

[백준] 알고리즘 1978번 - 소수 찾기

#include using namespace std; bool prime(int number) { if (number n; while (n--) { int number; cin >> number; if (prime(number) == true) { ans++; } } cout

Algorithm 2020. 12. 22. 16:23

[백준] 알고리즘 2089번 - -2진수 문제

#include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; if (n == 0) { cout

Algorithm 2020. 12. 21. 22:05

[백준] 알고리즘 2745번 - 진법 변환

#include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string s; long sum = 0; int b,trans=0; cin >> s >> b; int flag = s.size() - 1; while (flag >= 0) { for (int i = 0; i < s.size(); i++) { if ('A'

Algorithm 2020. 12. 15. 17:22

[백준] 알고리즘 11005번 - 진법 변환 2 문제

#include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector v1; int n, b,r=0; cin >> n >> b; while (n != 0) { r = n % b; n /= b; v1.push_back(r); } for (int i = v1.size(); i > 0; i--) { if (v1[i - 1] >= 10 && b > 10) { char result = v1[i - 1]-10 + 'A'; cout

Algorithm 2020. 12. 15. 00:39

[백준] 알고리즘 수학 - 나머지연산, GCD, LCM, 진법변환, 소수

(a+b)%c = (a%c + b%c)%c (a*b)%c=(a%c * b%c)%c 나누기의 경우 성립하지 않는다. 뺄셈의 경우 음수를 대비해야한다. (a-b)%c=((a%c-b%c)+c)%c GCD - 최대공약수 두 수 A와 B의 공통된 약수 중에서 가장 큰 정수이다. LCM - 최소공배수 두 수의 공통된 배수 중에서 가장 작은 정수이다. 유클리드 호제법 - GCD(a,b) = GCD(b,a%b) a%b의 값이 0이될때의 b의 값이 최대공약수이다. 소수 - 약수가 1과 자기 자신만 있는 수를 뜻한다. 소수는 2보다 크거나 같고, 소수-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다. for(int i=2;i

Algorithm 2020. 12. 14. 13:36

[백준] 알고리즘 2011번 - 암호코드 문제

#include using namespace std; long dp[5001]; int number[5001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string s; int mod = 1000000; cin >> s; s = '0' + s; dp[0] = 1; for (int i = 0; i < s.size(); i++) { number[i] = s[i] - '0'; } for (int i = 1; i 0) { dp[i] += dp[i - 1]; dp[i] %= mod; } if (number[i - 1] == 1 || (number[i - 1] == 2 && number[i]

Algorithm 2020. 12. 14. 00:03

[백준] 알고리즘 2225번 - 합분해 문제

#include using namespace std; long dp[201][201]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k,mod= 1000000000; cin >> n >> k; for (int i = 0; i

Algorithm 2020. 12. 13. 01:25

[백준] 알고리즘 9461번 - 파도반 수열 문제

#include using namespace std; long long dp[101]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T; cin >> T; dp[1] = 1, dp[2] = 1, dp[3] = 1; while (T--) { int n; cin >> n; for (int i = 4; i

Algorithm 2020. 12. 12. 20:09

[백준] 알고리즘 2133번 - 타일 채우기 문제

#include using namespace std; int dp[31]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; dp[0]=1, dp[2] = 3; for (int i = 4; i

Algorithm 2020. 12. 11. 18:28