ORTHODOX

알고리즘 분류: 수학, 정수론, 소수판정 코드: #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)임을 구했습니다. 그냥 재귀 호출로 하면 시간이 오래걸리므로 벡터를 하나 만들어서 호출할떄 마다 그 값을 벡터에 저장..

안녕하세요 오늘은 구간합 문제를 풀어보겠습니다. 해결전략: 우선은 '투포인터' 알고리즘을 이용할 겁니다 화살표는 왼쪽부터 l, r 화살표입니다 밑에 코드와 그림을 대조해 보시길 바랍니다. 코드분류: 투포인터 코드: #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int M, N; cin>> M>>N; vector v(M); for(int i= 0; i> v.at(i); } int l = 0, r = 0,sum = 0, count = 0; while(1){ if(sum >= N){ sum-=v.at(l); l++; } else if(r>=M){ br..

알고리즘 분류: 다이나믹 프로그래밍 코드: #include #include #include using namespace std; int main(){ int a; cin>>a; vector v(1000001); for(int i= 2; i

알고리즘 분류: 정렬, 투 포인터 코드: #include #include #include using namespace std; int main(){ int N, M,sum =0, count=0, l, r; cin>>N; l = 0, r = N-1; vector v(N); for(int i= 0; i>v.at(i); } sort(v.begin(), v.end()); cin>>M; while(1){ if(l>=r){ break; } sum = v.at(l) + v.at(r); if(sum==M){ count++; l++; r--; } else if(sum>M){ r--; } else{ l++; } } cout

개관 어떠한 한 문제를 풀기 위한 알고리즘은 여러가지입니다. 특정 문제를 풀때 여러가지 알고리즘중 어떤 알고리즘을 선택할지에 대한 기준은, '시간과 공간'에 있습니다. 시간은 그 소스코드가 동작하는 시간을 말합니다. 시간이 적을수록 무언가 다른 동작을 할 시간이 많아집니다. 또, 공간은 알고리즘을 실행 하는 데에 필요한 공간, 즉 컴퓨터 메모리를 말합니다. 이제 저희는 문제에 대한 알고리즘 선택에 최소 시간, 최소 공간이 필요한 알고리즘을 선택해야 한다는 것을 알 것입니다. 하지만 보통 시간이 빠르면 메모리 공간을 많이 차지하고, 메모리 공간을 별로 차지하지 않으면 시간이 느립니다. 보통 프록래밍 대회에서 중요시 여기는 알고리즘의 기준은 공간보다 시간에 초점을 두고있습니다. 따라서 저희도 시간에 초점을 ..

안녕하세요 오늘은 overthewire 12level -> 13level을 풀어보겠습니다. 문제에서 써있는 것을 보면, hexdump에 있다는것과, 여러번 압축됐다는 것이 보이네요. 또, tmp파일 하위로 파일을 만들어서 data.txt를 복사해서 사용하라고 하니까 한 번 해보죠. tmp 파일 하위에 orth라는 파일을 만들고 data.txt를 복사해서 넣어줬습니다. 우선은 data.txt를 바이너리로 바꿔주겠습니다 바이너리로 바꿔준 다음, file 명령어를 사용하여 이 파일의 형식을 봤는데, gzip으로 압축돼있다는 것을 알았고, gunzip으로 압축해제해주겠습니다. 주의해야할 점은 확장자가 .gz여야하므로 mv ans ans.gz를 먼저 해주겠습니다. 압축해제 하고 나니 또 bzip2로 압축돼있으므로..