sunrin
-
03. 3차시 교육알고리즘/정올1차교육(17.7.12~17.8.14) 2017. 7. 18. 00:32
01.cpp - 버블소트(거품정렬)1234567891011121314151617181920212223242526272829#include #include using namespace std;//bubble sortint arr[100];void f(int n){ for(int i=0; iarr[i+1]){ swap(arr[i], arr[i+1]); } if(i==n-2){ i=-1; n-=1; continue; } }} int main(){ int n; scanf("%d", &n); for(int i=0; i
-
01. 1차시 교육알고리즘/정올1차교육(17.7.12~17.8.14) 2017. 7. 13. 01:30
01.cpp - 소수판별 1234567891011121314#include int is_prime(int n){ for(int i=2; i r = mk - nkq => r = (m-nq) * k // 아니? a에도 k가 들어있고 b에도 k가 들어있고 r에도 k가 들어있다구우~? 근데 아직 b와 r의 최대공약수가 k인지는 모른다! 공약수가 k일뿐!즉 n과 m-ng가 서로소임을 증명하면 된다는 말이죠!여기서 귀류법 사용! (귀류법이란 증명하고자 하는 명제가 거짓임을 참으로 두고 그 명제의 불합리성을 증명함으로써 결국 증명하고자 하는 명제가 참임을 증명하는 방식.)=> n과 m-nq가 서로소가 아니라고 가정한다.=> n과 m-nq의 공약수를 G(1 아님)라고 한다.-> n = xG, m-nq = yG=> n ..
-
-
(추가) 달팽이 배열예제/Layer7_20160323 2017. 3. 28. 01:47
2016 03 23 다차원 배열에서 마지막 문제인 달팽이 배열을 1년뒤에 다시 짜 보았습니다.최대한 이해가 쉽게 주석을 많이 달아놨습니다. 혹시라도 이해가 안되시면 댓글을 남겨주세요기본 메커니즘은 가로와 세로를 나누고, 각각 오른쪽,왼쪽/아래쪽,위쪽 으로 진행방향을 기준으로 나누었습니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include int main(){ int arr[100][100]={0,}; //값을 저장할 배열 int input; //입력값 int i, j; //for문 돌리려고 i..
-
-
[고급-8] 동적테이블 응용3강의 2017. 1. 11. 10:14
선물n개의 선물을 한명씩 적절하게 분배.조건 1 : 각자의 부피는 [길동>=길순>=길삼]을 만족하도록분배한다. 조건 2 : 다음의 d가 최소가 되도록 한다. d=(길동선물 부피의 합)-(길삼 선물의 부피 합)조건 3 : 같은 d가 되는 배분방법이 여럿일 경우에는 길동의 선물의 부피 합이 적은 방법을 선택한다. W=a+b+c1~k까지의 선물을 받았을 때, 길순이가 부피 b, 길삼이가 부피 c를 받을 상태는 존재하는가? a=W-(b+c)a값을 굳이 저장 안해도 구할 수 있다는 사실! 1234567891011121314151617181920212223242526272829#include int n, W, G[21], A, B, C, ans=987654321;bool DT[21][2001][2001];int m..
-
[고급-7] 동적테이블 응용2강의 2017. 1. 9. 00:04
색상환 : 미국의 화가 먼셀이 교육용으로 고안한 20색상환문제 : n개의 색에서 인접하지 않은 k개의 색을 구할 때, 경우의 수를 10억3으로 나눈 값을 출력하라! solve(a, b) = 현재 a번 색상에 대해 고려하는 상태, 규칙에 맞도록 b개의 색깔을 이미 선택한 상태.하지만 문제 발생!따라서 f(a,b,c)는 c가 참이면 마지막 색을 고를 수 없는 상태. f함수 설계:if(b==k) return 1; ==> 찾으면 리턴1if(a>=n-can) return 0; ==> a가 2단계로 건너뛰는 경우도 있기 때문에return (f(a+1,b,can)+f(a+2,b+1,can)) %MOD; ==> 두가지 상태의 합을 MOD로 나눈 값의 나머지 출력.하지만 시간이 너무 많이 걸려서if(DT[can][a][..
-
(이산수학-3차시) 시도예선 2011~2012 중고등부 문제 오답노트알고리즘/정올반 2016. 12. 19. 00:49
5. 나머지가 하나씩 모자라므로 2,3,4,5,6의 최소공배수를 구해서 -1 해주면 됩니다.. 9. n=2^3*3^7*5의 서로소 개수 : n*(1/2)*(2/3)*(4/5)문제에서는 : 105*(2/3)*(4/5)*(6/7) 12. 그 번호의 약수의 개수가 홀수여야 전구가 켜진다.1~100 전구는 제곱수가 켜진다.101~200 전구는 제곱수가 꺼진다.(제곱수가 아닌 수들이 켜진다.)=>10+96=106 13. 대각선을 포함하지 않은 직각삼각형(길이1) : 36대각선을 포함하지 않은 직각삼각형(길이2) : 16대각선을 포함하지 않은 직각삼각형(길이3) : 4대각선을 포함한 직각삼각형 (길이(루트)2) : 24대각선을 포함한 직각삼각형 (길이(루트)5) : 16합 : 96 14. D(n)=2*3^(n-2)..