알고리즘
-
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 ..
-
-
(이산수학-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)..
-
(이산수학-2차시) 시도예선 2013~2014 중고등부 문제 오답노트알고리즘/정올반 2016. 9. 12. 18:55
개요 : 총 문제 15문제 맞춘 문제 10문제 4. 1000개의 동전을 반씩 나누면서 올려놓으면 10번만 반복하면 모든 경우를 탐색할 수 있다. 이진탐색과 같다고 생각하면 된다. 7. '정'은 3등이 될 수 없음(2명이 지목) -> 따라서 경우의 수는 하나밖에 없다. 병이 3등, 을이 1등, 갑이 2등. 8. 1~199 : 111개, 2~~ : 111개, 3~~ : 111개, 4 40 401 402 403 404 405 406 407 408 409 41 410 411 412 413350번째는 413이 온다. 10. 두자리수 정수의 세제곱이므로 : (10a+3)^3 = ...+270a+27 => 끝자리가 7이어야 한다. a=5, 답 : 1953. 12. KOI수열의 점화식을 세워보면 : D[i] = D[i..
-
(이산수학-1차시) 2015~2016 시도예선 중고등부 문제 오답노트알고리즘/정올반 2016. 9. 4. 18:14
(문제는 https://www.digitalculture.or.kr/koi/selectOlymPiadDissentList.do 에서 다운받으실 수 있습니다.)개요: 총 문제 15문제 맞춘 문제 11문제 3. a,b,c,d 네 정수는 무조건 1 이상이어야 하므로 주어진 식을 이렇게 바꿀 수 있다.(a-1)+(b-1)+(c-1)+(d-1)=6 => A+B+C+D=6여기서 6이란 숫자를 6개의 공으로 생각하고, A,B,C,D를 구역으로 생각한다. 이 구역 각각에는 공이 안들어가도 상관 없다.구역 사이에 칸막이 'I'가 있다고 하면, 칸막이는 총 3개가 있는 셈이다.이세 9개의 칸에 공6개와 칸막이 3개를 자유롭게 배치하는 경우의 수를 구하면 된다.ex)00I0II000 => A구역에 공2개, B구역에 공1개,..
-
(1차시) 유전 알고리즘알고리즘/정올반 2016. 9. 4. 17:39
1차시 - 권욱제 선배님의 『유전 알고리즘을 이용한 자동 주행 시뮬레이션』 사용 언어, 엔진 : c++, cocos2d -유전 알고리즘 머신러닝의 알고리즘 중 하나. 다윈의 적자 생존 이론을 기본 개념으로 한다. 처음 무작위 유전자들을 세대를 거듭할수록 문제 해결에 가까워질 수 있도록 해준다.-용어 정리1. 염색체 : 유전정보를 담고 있는 데이터 집합2. 유전자 : 염색체를 구성하는 요소3. 초기화 : 문제 해결을 위해 임의로 염색체를 만드는 과정4. 선택 : 다음 세대를 생성하기 위한 염색체를 선택하는 과정5. 교차 : 선택된 유전자들을 이용해 다음 세대 염색체를 생성하는 과정6. 돌연변이 : 교차 과정에서 일정 확률로 유전자의 정보에 변형을 주는 과정 -학습 과정(1) 염색체 10개를 랜덤 생성.(1..