2025년, 코딩은 선택이 아닌 필수!

2025년 모든 학교에서 코딩이 시작 됩니다. 먼저 준비하는 사람만이 기술을 선도해 갑니다~

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

[정보올림피아드 대비]23. 수학게임문제

수학게임 문제는 전략적인 상황에 대한 수학적인 모델로 활용이 되며 게임이론에 사용이 된다. 이러한 문제중 하나가 제로섬게임과 같은 문제가 있으며 이는 한 참가자가 승리하면 다른 참가자는 패배하게 되는 경우를 가르키는 수학적인 표현이다. 예를 들면 틱택토, 체스, 다양한 수.정수 게임 등이 있다. 수학게임 문제로는 두 사람이 경쟁적인 게임을 진행할때 먼저 시작한 사람이 승리하게 되는 수가 존재하는지를 묻는다. 결정트리) 알고리즘 문제로 풀어 나갈때 재귀적인 코드를 작성하여 게임의 결정트리, 혹은 게임 트리를 탐색하는 것이다. 만일 부분 문제가 중복되지 않는다면 모든 경우를 모두 방문해 보는 경우이다. 문제1) 유클리드 게임은 두명이서 하는게임이고 자연수 2개로 시작한다. 동혁이와 동규는 유클리드 게임을 하..

[정보올림피아드 대비]22. 암호화 관련 문제

1. 다음의 암호화된 문장을 해독하세요. KS VCDS HC USH CIF OGGSHG QFCGG HC RSGQSBROBHG. 생각해 보기) - 분수는 왜 유한소수 혹은 순환소수가 될까? 예) 3/10 = 0.3 7/20 = 0.35 2/125 = 0.016 1/7 = 0.142857..... 1/12 = 0.0833333... - 여기서 우리는 10진수 체계이므로 분모가 2와 5로 이루어진 경우는 유한소수이다. 증명) 7/20 = (7*5)/(20*5) = 35/100 과 같이 분모를 10의 거듭제곱으로 나타낼 수 있다. - 2와 5외의 수가 포함되면 순환소수이다. 증명) 1/7 = 10/70 = (10/7) / 10 = (1 + 3/7) / 10 = 1/10 + 3/70 3/70 = 30/700 = ..

[정보올림피아드 대비]21. 트리 활용한 문제

1. 트리의 개념 루트(root)라는 특별한 노드(Node)를 갖고 그래프를 구성하는 꼭짓점 u,v 간에 단순 경로가 존재하는 비순환 연결 그래프를 트리(Tree)라고 한다. 예) 오른쪽 트리(Tree) 를 기준으로 개념이해 루트(Root)노드 : 트리의 가장 높은 곳에 위치하는 시작 노드인 A 부모(Parent)노드 : 트리를 구성하는 임의의 노드의 한단계 상위노드 (예- B,C,D의 부모 노드는 A) 자식(Child)노드 : 트리를 구성하는 임의의 노드의 한단계 하위노드(예-B의 자식 노드는 E,F) 형제(Sibling)노드 : 트리를 구성하는 임의의 노드와 부모가 같은 노드(예-E의 형제는 F) 리프(Leaf)노드 : 트리를 구성하는 임의의 노드중 자식이 없는 노드(예-E,F,C,G) 중간(Inte..

[정보올림피아드 대비]20. 저울을 이용한 문제

저울 문제란? 일명 천칭문제라고도 불리우는 양팔저울 혹은 전자저울을 이용하여 문제를 풀어나가는 문제를 의미한다. 전자 저울은 무게를 수치로 정확하게 잴 수 있지만 대개 1번 등의 매우 적은 횟수로만 무게를 판별하라고 한다. 또 무게를 비교하는 용도로는 양팔 저울에 비해 약간의 응용이 필요한 문제들이 출제되고 있다. 양팔 저울은 무게를 수치로 정확하게 잴 수 없는 대신 횟수는 3번 정도는 주어지는 편이다. 무게의 상대적 가벼움과 무거움을 재는 데에는 유리하지만 수치적으로 나열하기는 어렵다는 특징이 있다. 저울 관련한 유형은 최적화의 개념이나 부등식의 성질을 이해하여 해결하는 문제로 교과나 경시에서 관련 문제가 자주 출제 된다. 문제1) 크기와 모양이 같은 공 11개가 있다. 이 공들 중 무게가 다른 공은 ..

[정보올림피아드 대비]19. 방정식을 활용한 문제

방정식이란? 기본적인 연산을 할 때 구체적인 수들을 볼 수 있어요. 가령 23 + 5 = 28 과 같이 계산이 되는 것을 볼 수 있습니다. 대수의 세계로 들어가면서 변수라는 개념을 다루게 됩니다. 변수란 바뀔 수 있는 값이나 식을 의미합니다. 예를 들어 x + 5 라고 쓴다고 하면 x 의 값에 따라 결과값은 달라 집니다. 이러한 것은 하나의 식이라고 합니다. 여기서 식과 방정식의 차이를 확인해 보겠습니다. 식은 단지 어떤 값을 나타내는 표현입니다. 예를들어 x + 5 라는 식은 x의 값에 따라 결과값이 바뀔것입니다. 방정식의 경우는 식이 서로 같다고 가정하고 시작합니다. 예를 들어 x + 5 = 10 이라고 하면 한개의 값을 모르는 상황에서 x의 값을 알아낼 수 있습니다. 이렇게 미지수가 포함된 식에서 ..

[정보올림피아드 대비]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시로 간다는 사실을 알고 있지만 앞의 차의 목적지만 볼 수 있습니다. 안내원은 이 몇 분의 기사들이 모두 총명할 것으로 생각하고 그들의 차가 어느 도시로 가야 하는지 목적지를 알려 주지 않고 그들에게 맞혀 보라고 하였습니다. 먼저 세번째 기사에게 자신의 목적지를 맞혀 보라고 하였더니 그는 앞의 두 차에 붙여 놓은 표시를 보고 말하기를 "모르겠습니다." ..