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

[정보올림피아드 대비]18.그래프 관련 문제(한붓그리기외)

1. 그래프란? 그래프 : G=(V,E) 여기서 V는 정점(Node 라고도 하며 꼭짓점이라고도 한다.), E는 엣지( Vi~Vj 를 연결하는 모서리)라고 하며 그래프는 정점과 모서리의 집합으로 구성된 구조를 의미한다. 예) 위와 같은 형태가 그래프이다. 2. 그래프 인접(Adjacent),근접(Incident),루프(Loop) - 인접(Adjacent),근접(Incident) 그래프 G=(V,E)에서 꼭짓점 a와 b를 연결한 모서리 ab가 있을 때 꼭짓점 a와 b는 서로 인접하고 모서리 ab는 꼭짓점 a와 b에 근접한다. - 루프(Loop) 인접하는 꼭짓점이 하나인 모서리 e 3. 방향그래프 화살표로 모서리를 표현해 인접하는 꼭짓점 간의 순서를 알 수 있는 그래프 G = 로 표현하며 인접하는 꼭짓점 사이..

[정보올림피아드 대비]17.진수를 활용한문제(2진수,10진수,16진수등)

1. n진법 n진법이란 0과 n-1 사이의 숫자들을 이용해 수를 표현하는 방식입니다. 즉 우리가 사용하는 10진법은 0~9까지의 수를 사용하며 컴퓨터가 사용하는 2진법은 0~1 까지의 수를 사용합니다. n진법을 사용한다면 n을 기수(Base Number) 라고 합니다. 기수표기 예) 10진수 1234 : 1234(10) 2진수 1010 : 1010(2) 2. 10진수(Decimal Number) 10진수는 기수를 10으로 하는 수 체계이며 0과 9 사이의 숫자를 이용해 수를 표현합니다. 또한 10진수는 정수 1234 에 대해 다음과 같이 표현 할 수 있습니다. 1234(10) = 1*103 + 2*102 + 3*101 + 4*100 즉 오른쪽 부터 왼쪽으로 기수의 0승 , 기수의 1승 ,기수의 2승 자리..

[정보올림피아드 대비]16. 점화식(재귀 포함)을 이용한 문제

점화식이란 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타내는 관계식이다. 즉, 수열 { an }의 각 항 an 이 함수 f를 이용해서 f(an) = an+1 과 같이 귀납적으로 정의 될때 f를 수열 {an}의 점화식이라고 하며 또한 수열 {an}은 점화식 f로 정의 된다고 한다. 예) 하노이의 탑 유명한 하노이이탑 문제는 n개의 원판을 이동하는 회수를 수열 an으로 정의 하면 n개의 원판을 이동시키기 위해서는 그 위쪽 n-1개의 원판을 다른 막대로 이동한 후, 맨 아래쪽 원판을 이동하고 다시 n-1개의 원판을 이동해야 하므로 다음과 같은 점화식이 성립함을 알수 있다. f(n) = f(n-1) + 1 + f(n-1) = 2*f(n-1) + 1 = 2^n - 1 (단, f(1)=1) 예) 피보나치..

[정보올림피아드 대비]15. 집합의 성질을 이용한 문제

1.집합(Set)이란? 명확한 기준에 의해 분류되어 공통된 성질을 가지며 중복되지 않는 원소(Element,Member)의 모임 2. 집합의 표기 방식 1. 원소나열법 : 집합에 포함되는 원소들을 일일이 나열하는 방법 예) A = {1,2,3,4,5} 2. 조건제시법 : 집합에 포함되는 원소들이 공통적인 성질을 조건식으로 제시하는 방법 예) A = {x | 0< x

[정보올림피아드 대비]14. 논리.추론문제

논리 추론 문제는 어떤 문제를 해결할 때에는 우선 주어진 조건에서 각 부분간의 관계를 잘 해석한 다음 분석하고 추리하여 불가능한 경우는 버리고 점차적으로 귀납하여 정확한 답을 찾는 문제이다. 1. 도로에 5대의 큰 버스가 차례로 세워져 있는데 각 차의 뒤에 모두 차의 목적지가 적혀져 있습니다. 기사들은 이 5대 차 중 2대는 A시로 가고, 나머지 3대는 B시로 간다는 사실을 알고 있지만 앞의 차의 목적지만 볼 수 있습니다. 안내원은 이 몇 분의 기사들이 모두 총명할 것으로 생각하고 그들의 차가 어느 도시로 가야 하는지 목적지를 알려 주지 않고 그들에게 맞혀 보라고 하였습니다. 먼저 세번째 기사에게 자신의 목적지를 맞혀 보라고 하였더니 그는 앞의 두 차에 붙여 놓은 표시를 보고 말하기를 "모르겠습니다." ..

[정보올림피아드대비]13. 시계문제

시계문제는 시계의 시침과 분침을 연구하는 문제입니다. 시계의 둘레를 60칸으로 나누면 분침이 60칸 움직일때 시침은 5칸 움직입니다. 그러므로 시침의 속도는 분침의 5 / 60 = 1/12 입니다. 따라서 분침과 시침이 현재 만나 있는 상태에서 다음에 만나는 시간은 분침이 이동하는 시간 x = 60 + x * 1/12 이 됩니다. 따라서 x * 11/12 = 60 이므로 x = 60 * 12/11 = 65 와 5/11 분 후에 만나게 됩니다. 시계문제는 다양하고 또 많은 지식도 들어가 있습니다. 여기서 기본 공식을 소개하면 처음 시각에 따라잡아야 할 칸 수 / (1-1/12) = 따라잡는 격시간(분) 이고 그 중 (1-1/2)는 매분 분침이 시침보다 더 간 칸수입니다. 1. 현재 시각은 3시입니다. 분침..

[정보올림피아드 대비]12. 비둘기집의 원리를 이용한 문제

비둘기집의 원리는 다음과 같습니다. 비둘기집은 2개이고 비둘기는 3마리입니다. 비둘기가 저녁에 잠을 자기 위해 들어가야 되는데~ 그렇다면 반드시 한개의 비둘기 집에는 비둘기가 2마리 이상 존재하게 된다는 원립니다. 이러한 원리를 다음과 같이 정의 됩니다. n개의 배둘기집과 n+1마리의 비둘기가 있다고 가정한다. 만약 각 비둘기집에 한마리 이하의 비둘기만 들어 있다면, 전체 비둘기집에는 많아야 n마리의 비둘기가 존재한다. 그런데 비둘기는 모두 n+1마리 이므로 이것은 모순이다. 따라서 어느 비둘기집에는 두마리 이상의 비둘기가 있다. 이것을 일반화된 원리로 정의를 하면 다음과 같이 정의 된다. n개의 별개의 사물을 m개의 용기에 담으면 적어도 한개의 용기는 n/m 이상의 사물을 담고 있어야 한다. 1. 어느..

[정보올림피아드대비]11.소가 풀을 먹는 문제

목장에 같은 속도로 자라는 풀밭이 있는데 27마리 소가 6주 또는 23마리 소가 9주 동안 먹을 수 있습니다. 그러면 21마리 소가 몇주 먹을 수 있습니까? 이런 유형의 문제를 소가 풀을 먹는 문제라고 합니다. 이러한 문제를 푸는데 중요한 것은 풀의 총량이 변하고 매일, 매주마다 같은 속도로 자라며 시간이 많이 지날수록 풀의 총량도 많아지는 것입니다. 풀의 총량은 두개 부분입니다. 1) x시간 전에 풀밭에 있는 풀의 양 2) x시간 후에 풀밭에 매일(매주) 새로 자라는 풀의 양입니다. 그렇다면 위의 문제를 분석해 봅시다. 27마리 소가 6주동안 먹은 풀 : 원래의 풀 + 6주간 자라는 풀 23마리 소가 9주동안 먹은 풀 : 원래의 풀 + 9주간 자라는 풀 따라서 27마리 소가 6주동안 먹은 풀의 양은 1..

[정보올림피아드대비]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|..