ORTHODOX

안녕하세요 오늘은 브루트 포스를 이용한 문제풀이를 하겠습니다. 코드: #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N; cin>>N; if(N

안녕하세요 오늘은 단순 브루트 포스 문제를 풀어보겠습니다 이 문제는 상식과는 다르게 삼중 for문으로 단순하게 풀어도 시간이 0ms이 나옵니다 코드: #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, M,ans, min = 9999999; cin>>N>>M; vector v(N); for(int i = 0; i> v.at(i); } int sum; for(int i = 0; i

안녕하세요 오늘은 에라토스테네스의 체를 이용한 소수판정 문제를 풀어보겠습니다. 이러한 소수 판정문제는 bool array를 이용하여 에라토스테네스의 체를 구현해주시면 쉽게 풀립니다. 하단 코드를 참고하시길 바랍니다. #include using namespace std; bool era[9999]; int main(){ for(int i = 1; in; int l = n/2, r= n/2; while(1){ if(era[l] == true and era[r] == true){ break; } l--; r++; } cout

안녕하세요 오늘은 에라토스테네스의 체를 이용한 소수 판정 문제를 풀어보겠습니다. 이 문제는 bool array를 이용하여 에라토스테네스의 체를 구현해주시면 어려움이 없습니다. 하단 코드를 참고하세요. #include #include using namespace std; vector v; bool era[246914]; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); for(int k = 0; k>x; if(x==0) break; v.push_back(x); v_size++; } for(int i = 2; i

알고리즘 분류: 수학, 정수론, 소수판정 코드: #include #include using namespace std; vector v; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int a; cin>>a; while(1){ if(a==1) break; for(int i = 2; i

알고리즘 분류: 수학, 정수론, 소수판정 코드: #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int M, N, min = 10001; long long int sum = 0; cin>>M>>N; if(M==1 and N==1){ cout

안녕하세요 오늘은 특정한 알고리즘을 사용하는 것이 아닌 수학적 사고력을 이용한 문제를 풀어보겠습니다. 이 문제는 특정한 알고리즘을 생각해내는것보다 단순히 이 문제의 원리를 생각해야합니다. 코드: #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; for(int i = 0; i>x>>y; if(y-x == 1){ cout

안녕하세요 오늘은 다이나믹 프로그래밍을 이용한 문제를 풀어보겠습니다. 1 11 00 100, 111, 001, 1001, 1111, 0011, 0000, 1100 10011, 11111, 00111, 00001, 11001, 10000, 11100, 00100 f(n) = {f(n-1) + "1"} + {f(n-2) + "00"} 메모장에 끄적이면서 생각했습니다. f(n)의 경우는 f(n-1) 뒤에 "1"을 붙인 경우와, f(n-2) 뒤에 "00"을 붙인 경우를 합한것입니다. 따라서 개수는 f(n) = f(n-1) + f(n-2)입니다 이것을 구현하겠습니다 주의해야할 점: v.at(n)이 int의 범위를 넘어가지 않도록 v.at(i)을 설정해줄때부터 15746을 계속 나눈 나머지를 대입합니다. 코드: #..

안녕하세요 오늘은 다이나믹 프로그래밍을 이용한 문제를 풀겠습니다. 피보나치 수열은 워낙 유명해서 다들 아시죠? F(n) = F(n-1) + F(n-2) 이 문제를 두가지 방법으로 풀었습니다 첫번째는 피보나치 함수를 만들어서 재귀로 호출해주는 방법입니다 코드는 다음과 같습니다. #include using namespace std; int fibonacci(int n){ if(n==0) return 0; if(n==1) return 1; return fibonacci(n-1) + fibonacci(n-2); } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int a; cin>>a; coutn; n++; v.at(1) = 0; v.at(2) =..

안녕하세요 오늘은 다이나믹 프로그래밍을 이용한 알고리즘 문제를 풀어보겠습니다. 경험상, 일반적인 다이나믹 프로그래밍 문제는 점화식이 많은 것 같습니다. 위 문제도 똑같습니다. 잘 생각하면 f(n-3)인 식뒤에 +3, f(n-2)인 식 뒤에 +2, f(n-1)인 식 뒤에 +1을 하면 f(n)을 만드는 식의 모든 경우의 수인것을 알 수 있습니다. f(n)중에 마지막이 +1로 끝나는 모든 경우의 수는 f(n-1) + 1, +2로 끝나는 모든 경우의 수는 f(n-2) + 2, +3으로 끝나는 모든 경우의 수는 f(n-3) + 3입니다 따라서 f(n) = f(n-1) + f(n-2) + f(n-3)임을 구했습니다. 그냥 재귀 호출로 하면 시간이 오래걸리므로 벡터를 하나 만들어서 호출할떄 마다 그 값을 벡터에 저장..