강의자료/이산수학문제풀이 10

[정보올림피아드대비]10. 약수,배수,최대공약수,최소공배수를 이용한 문제

1. 약수와 배수 a,b,c 는 자연수 이고 b ≠ 0 , a ÷ b = c , 즉 자연수 a 나누기 b 는 c 이고 나머지는 없다면 a를 b의 배수 라고 하고 b는 a의 약수라고 합니다. 예) 15 ÷ 3 = 5 에서 15는 3의 배수이고 3은 15의 약수입니다. 2. 소수와 합성수 한 수가 1과 그 수 자체를 제외하고 다른 약수가 없을때 그 수를 소수라고 합니다. 한 수가 1과 그 수 자체를 제외하고 다른 약수가 있을때 그 수를 합성수라고 합니다. ※ 단, 1은 소수도 합성수도 아닙니다. 3. 소수와 소인수 분해 만약 한 소수가 어떤 수의 약수이면 이 소수를 어떤 수의 소인수라고 합니다. 어떤 합성수를 소인수들의 곱으로 표시했을 때 이것을 소인수분해라고 합니다. 예) 30을 소인수 분해 하면 2 * ..

[정보올림피아드대비]9. 나누어 떨어짐을 이용하는 문제(배수판정법)

1. 수의 나누어 떨어지는 성질 성질1 : 만약 a,b,c 가 모두 c 에 의하여 나누어 떨어지면 그들의 합과 차도 모두 c에 의하여 나누어 떨어집니다. 즉 만약 c|a,c|b 이면 c|(a±b) 도 성립됩니다.(단, 여기서 c|a 의 의미는 a가 c로 나누어 떨어진다는 의미입니다.) 예) 2|10,2|6 이면 2|(10+6), 2|(10-6) 입니다. 성질2 : 만약 b와 c의 곱이 a를 나누어 떨어지게 하면 b와 c도 a를 나누어 떨어지게 할 수 있습니다. 즉 만약 bc|a 이면 b|a,c|a 도 성립합니다. 예) 2*5|30 이면 2|30,5|30 이 성립됩니다. 성질3 : 만약 b와 c가 모두 a를 나누어 떨어지게 하고 b와 c가 서로소이면, b와 c의 곱도 a를 나누어 떨어지게 합니다. 즉 b|..

[정보올림피아드대비]8.조합에관한문제

조합은 Combination 이라고 하며 순서를 생각하지 않고 나열하는 경우를 말한다. 즉 123 과 321 은 같은 경우로 생각하는 경우이다. 이러한 문제는 중고등부 유형이나 혹은 알고리즘 유형에서 나오는 문제이다. 다음의 문제를 풀어 보자. 문제풀이) 더보기 1) 남자 13명 중에서 3명을 뽑는 경우의 수는 첫번째 13명중에서 1명을 뽑는 13가지 두번째 첫번째 뽑힌 사람을 제외하고 12명 중에서 1명을 뽑는 12가지 세번째 는 남은 11명 중에서 1명을 뽑는 11가지 즉 13P3 = 1716 이다. 여기서 남자에게 번호를 1~13까지 번호를 붙여 본다면 1번,2번,3번을 선택한 경우는 123,132,213,231,312,321 과 같이 6가지이다. 하지만 이렇게 6가지의 경우는 동일하게 하나로 선택..

[정보올림피아드대비]7. 순열에 관한 문제(곱의법칙,합의법칙)

더보기 문제풀이) 더보기 2학년부터 4학년 학생중 학점이 3.0 이상인 학생은 2학년 - 22명 3학년 - 28명 4학년 - 18명 2학년 3.0 이상인 학생이 3학년 3.0 또는 4학년 3.0 이상인 학생과 중복 되는 경우가 없으므로 경우의 수는 22 + 28 + 18 = 68 가지 이다. [문제풀이] 더보기 문제풀이) 더보기 1) 한가지만 선택하는 경우이므로 한가지를 선택하면 다른 것을 선택 할 수 없다. 따라서 합의 법칙에 해당한다. 5+2+4+3 = 14 2) 각각 하나씩 선택을 해야 하므로 곱의 법칙에 해당한다. 5 * 2 * 4 * 3 = 120 문제풀이) 더보기 첫째자리에 4가지를 선택 할 수 있다. 둘째자리에 첫째자리에서 선택한 1가지를 제외한 3가지를 선택할 수 있다. 셋째 자리에 첫째자..

[정보올림피아드대비]6.숫자로 진 만들기(복면산연산)

숫자로 진을 만드는 것은 일정한 조건에 맞게 여러가지 도형으로 배열하는 문제입니다. 숫자진은 일종의 숫자 그림으로 숫자진 그림에 관한 문제의 종류는 다양하지만 여기서는 밀봉형 숫자진,부채꼴 숫자진,복합형 숫자진에 대해서 알아 보겠습니다. 1. 1~8의 8개의 자연수를 각각 아래 그림의 8개의 동그라미 안에 써 넣어 사각형 각 변 위의 3개의 숫자의 합이 모두 14가 되게 하고, 또한 숫자 1은 사각형의 한 꼭짓점 위에 있게 하려고 합니다. A의 위치에는 어떤 숫자가 들어가겠습니까?(숫자만 입력하세요.) 문제풀이) 더보기 왼쪽 상단 1 위치부터 시계 방향으로 a,b,c,A,d,e,f 로 그림을 그려 보면 1 + a + b = 14 --(1) b + c + A = 14 --(2) A + d + e = 14 ..

[정보올림피아드대비]5. 기하문제-평면

1. 도형의 둘레 - 사각형의 둘레 구하기 사각형 둘레는 a + a + b + b 이므로 2 * (a+b) - 삼각형의 둘레 구하기 삼각형의 둘레는 a + b + c ※ 여기서 피타고라스 정리에 의해 직각 삼각형의 빗변 c의 제곱은 다른 두변 a,b의 제곱의 합과 같다 증명) 이렇게 연장선을 그려서 하나의 정사각형을 만들어 보자. CDFH 의 넓이 = 삼각형 ABC의 넓이 * 4 + 사각형 AEGB의 넓이 CDFH 의 넓이 = (a+b)^2 = a^2 + 2ab + b^2 사각형 AEGB의 넓이 = c * c 삼각형 ABC의 넓이 = a * b / 2 이므로 a^2 + 2ab + b^2 = c * c + 4 * a * b / 2 따라서 a^2 + b^2 = c^2 - 원의 둘레 원의 둘레는 원의 반지름과..

[정보올림피아드 대비]4. 기하 문제-선분

1. 다음의 도형에서 몇개의 선분이 있는지 세어 보세요.(숫자만 입력하세요.) 문제풀이 더보기 각 점의 위치에 1,2,3,4,5 의 번호를 붙여 줍니다. 1번에서 그릴수 있는 선분은 (1,2)(1,3)(1,4)(1,5) 4개입니다. 2번에서 그릴수 있는 선분은 (2,3)(2,4)(2,5) 3개 입니다. 3번에서 그릴수 있는 선분은(3,4)(3,5) 2개입니다. 4번에서 그릴 수 있는 선분은(4,5) 1개입니다. 따라서 1+2+3+4 = 10개입니다. 2. 아래 그림에서 각이 모두 몇개 있습니까? 문제풀이 더보기 각 점의 위치에 1,2,3,4,5 의 번호를 이용하면 1번에서 그릴수 있는 각은 (1,2)(1,3)(1,4)(1,5) 4개입니다. 2번에서 그릴수 있는 각은 (2,3)(2,4)(2,5) 3개 입니..

[정보올림피아드 대비]3. 속도와 거리 문제

거리,속도,시간 및 그들 사이의 관계를 연구하는 문제를 모두 거리에 관한 문제라고 합니다. 거리와 속도 관련해서는 여러분은 아빠가 시속 120km 로 운전을 하고 갈때 2시간 후에 가는 거리는 240km 라는 것을 알고 있는 것처럼 거리 = 속도(120/1시간) * 시간(2시간) 을 잘 알고 있습니다. 여기서는 이렇게 알고 있는 속도와 거리 문제를 풀어 보는 방법에 대해 알아 보겠습니다. 1. A,B 두사람은 각각 서로 30km 떨어져 있는 두 지점에서 동시에 출발하여 서로 마주보고 걸어 오는데 A는 6km/h로 걷고 B는 4km/h 로 걷습니다. 두 사람은 몇시간이 지나면 서로 만납니까?(숫자만 입력하세요.) 문제풀이) 더보기 처음 30km 떨어져 있는데 두사람은 1시간에 10km 씩 좁혀져 옵니다. ..

[정보올림피아드 대비]2. 수열을 응용한 문제(등차수열,등비수열 외)

목표 정보올림피아드 1차 예선 문제중 50%에 해당하는 200점이 이산수학 + 비버챌린지 유형으로 제출 됩니다. 실기문제 2문제를 모두 만점을 맞는 것도 중요하지만 실기문제도 수학적인 기반을 갖추고 있는 것이 유용합니다. 특히나 실기문제 유형들 중에서 수열을 응용한 문제들이 다양하게 출제되고 있습니다. 오늘은 수열을 응용한 문제들을 연습하면서 1차예선과 실기문제등을 모두 대비해 봅니다. 문제 등차수열이란 앞과 뒤의 두 항의 차이가 일정한 수열을 말합니다. 1,2,3,4,5,6,7... (1) 은 두 항의 차이가 1로 일정한 등차수열입니다. 11,14,17,20,23,.... (2) 은 두 항의 차이가 3으로 일정한 등차수열입니다. 이렇게 두 항의 차이가 같은 등차수열에서 두 항의 차이를 공차 라고 하며 ..

[정보올림피아드 대비]1. 새로운 연산정의하는 문제

목표 정보올림피아드 1차 유형에서 나오는 수학 문제에서 우리가 알고있는 사칙연산(+,-,*,/) 외에 새로운 유형의 연산자를 정의해서 문제를 풀어 보는 연산정의하는 유형의 문제를 풀어 보고 익히면서 생각하는 힘을 키워봅니다. 문제 a ※ b = a * b - ( a + b) 입니다. 1. 5 ※ 7 의 연산값을 숫자만 입력하시오. 문제풀이) 더보기 5 ※ 7 = 5 * 7 - ( 5 + 7 ) 입니다. 따라서 35 - 12 = 23 2. 7 ※ 5 의 연산값을 숫자만 입력하시오. 문제풀이) 더보기 7 ※ 5 = 5 * 7 - ( 7 + 5 ) 입니다. 따라서 35 - 12 = 23 3. 12 ※ ( 3 ※ 4) 의 연산값을 숫자만 입력하시오. 문제풀이) 더보기 12 ※ ( 3 ※ 4) = 12 ※ ( 3..