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

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

강의자료 343

[알고리즘 수학] 카드 맞히기 마술

어느 마술사가 한 관객에게 1부터 27까지 쓰여진 27장의 카드 중에서 한 장을 고른 후 그 카드를 마술사에게 보여주지 않은 채 다시 카드 무더기 안에 집어 넣으라고 시켰다. 마술사는 카드를 다시 섞은 다음 한 번에 한 장씩 앞면이 보이도록 세 무더기로 나누기 시작했다.(예 1~27 까지의 카드가 순서대로 있었다면 1,4,7...,25 / 2,5,8 ...,26/3,6,9 ...,27 와 같이 순서대로 하나씩 3 그룹으로 분리한다.) 그런 후 카드를 선택했던 관객에게 아까 골랐던 카드가 어느 무더기에 들어갔는지 물어본다. 관객이 고른 무더기를 다른 두 무더기 사이에 집어 넣은 다음 카드를 섞지 않은 채 아까처럼 세 무더기로 나눠 놓는다.(예를 들어 첫번째 그룹에 들어 있었다면 2,5,8,...26/1,4..

[알고리즘 수학] 막대자르기

길이가 100인 막대를 잘라 길이가 1인 조각 100개를 만들어야 한다. 여러 조각을 한꺼번에 자를 수 있다고 가정할 때 자르는 최소 횟수는 몇번인가? 막대의 길이가 n일때 최소 횟수만에 자르는 알고리즘을 설명하라. 문제출처) 길벗 - 알고리즘 퍼즐 문제풀이) 이 문제는 정보올림피아드 예선 문제에 자주 출제되는 유형으로 다음과 같이 절반씩 잘라 가는 유형으로 생각하면 됩니다. 100 = 50 * 2 50 = 25 * 2 25 = 13 + 12 (여기서 13 크기를 기준으로 생각함) 13 = 7 + 6 (여기서 7 크기를 기준으로 생각함) 7 = 4 + 3 (여기서 4 크기를 기준으로 생각함) 4 = 2*2 2 = 1*1 즉 7번이면 100인 막대를 1 크기로 모두 자를 수 있습니다. 여기서 아이디어는 절..

[알고리즘 수학] 살아있기 좋은 날

세계 과학의 역사라는 책을 준비 중인 편집자가 주요 과학자가 가장 많이 살아 있던 시기를 알아 보려고 한다. 여기서 주요 과학자는 그 책에 출생연도와 사망연도가 모두 기록된 과학자로 정의한다.(그 책에 살아 있는 과학자는 수록되어 있지 않다) 책의 색인을 입력 받아 이 작업을 처리해보자. 만약 A가 사망한 해에 B가 새로 태어났다면 A의 사망시점이 B의 출생 시점보다 앞선다고 가정하자. 문제 출처)길벗출판사- 알고리즘 퍼즐 문제풀이) 이 문제는 자료구조의 count배열을 사용하여 해결이 가능하다. 예를 들어 다음과 같이 (태어난 해,사망한해)의 형태로 데이터가 입력 되었다고 가정해 보자. A(1,9),B(4,7),C(2,10),D(7,11),E(3,12) 태어난 해에는 +1,사망한 해에는 -1로 표기를 ..

[기초수학] 수열과 점화식

1. 수열이란 수열은 수를 나열한 것을 의미한다. 즉 1,2,3,4... 와 같이 수를 나열하고 첫번째항은 1항,두번째 항은 2항,.... n번째 항은 n항이라고 한다. 바로 위의 수열에서 1항은 1,2항은 2 의 값을 갖는다. 신경망의 수열은 유한개 항 수를 갖는 수열이다. 이렇게 유한개 항 수를 갖는 수열을 유한수열이라고 하며 마지막 항은 말항(final term) 또는 끝항 이라고 한다. 만약 1,4,7,10 과 같은 수열이 있다면 말항은 10이다. 2. 수열의 일반항 일반항이란 수열에서 n번째 항을 의미한다. n은 자연수로 수열의 모든 항을 n에 대한 식으로 나타낸 것이다. 따라서 일반항은 n에 대한 함수의 성격을 가진다. 예를 들어 2,4,6,8... 과 같은 수열의 n번째 항은 2*n의 값을 ..

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

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

[알고리즘 수학] 쪽번호 붙이기

1부터 시작해 순차적으로 쪽번호를 어떤 책에 매기고 있다. 쪽 번호를 붙이는데 숫자를 1581개 썼다면 그 책은 몇쪽짜리 책인가? (예 123 페이지 쪽 번호를 붙였다면 숫자를 1,2,3 세개를 사용한 것이다.) [문제출처] 길벗 - 알고리즘퍼즐 문제풀이) 1~9 까지는 9개의 숫자를 사용한다.(총 9개 - 남은 갯수 1572) 10~99까지는 2개씩 90개의 수이므로 180개를 사용한다.(총 189개 - 남은 갯수 1392) 100~999 까지는 3개씩 900개의 수이므로 2700개를 사용한다. 100 부터 1392개를 사용한 경우이므로 1392를 3으로 나누면 464개가 된다. 100부터 464번째이므로 563 쪽이 된다.(100부터 1번째 쪽수는 100이므로 464번째는 563쪽이다.) 이것을 c언..

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

[기초수학] 지수함수

1. 지수함수란 a를 양의 상수, x를 모든 실수 값을 취하는 변수라고 할 때 y=ax 형태로 주어지는 함수를 의미한다. 상수 a는 지수함수의 밑(base) 라고 한다. 밑의 값으로 특히 중요한 것은 자연상수 e 이다. 자연상수 e 는 다음과 같은 근삿값을 갖는다. e=2.718281828.... y=ex 역시 그래프로 나타낼 수 있으며 실변수 x의 함수로서 그래프는 항상 양수이고 왼쪽에서 오른쪽으로 증가한다. 이 때 그래프는 x축과 만나지 않지만 x축에 점점 접근해 간다. 2. 지수함수를 사용하는 이유 미분은 그래프의 기울기값으로 생각할 수 있다. 만약 시간(x축)에서 이동하는 거리(y축)을 측정한 후 특정시간에서의 기울기를 구하게 되면 그 시간을 지나는 시점의 속도를 알 수 있다. 적분은 미분의 반대..

[알고리즘]다익스트라(Dijkstra) 알고리즘

다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘은 출발점이 있는 곳에서 모든 정점까지의 최단거리를 찾는 알고리즘이다. 경로에 음수가 포함되면 경로를 찾을 수 없다. 알고리즘 모든 정점의 최단거리를 구할 배열 d[]를 만들고 배열에 INF 값을 채워 넣는다.(INF 는 경로의 계산에서 나올 수 없는 매우 큰 값을 의미한다.) 출발하는 정점의 위치에 0을 채워 넣는다. 방문하지 않은 경로 중 현재까지의 값중에서 가장 짧은 거리의 정점을 선택한다.(만약 이 값이 INF 라면 갈 곳이 없다는 것이므로 더이상 진행하지 않아도 된다.) 선택된 정점은 방문한 정점으로 마킹을 한다. 선택된 정점에서 갈 수 있는 모든 경로를 가 보면서 자신까지 온 거리와 다음 정점까지 갈 수 있는 거리의 합이..

[기초수학] 제곱근

제곱근의 개념 - 제곱을 했을때 어떤 수가 되는 값을 그 어떤수에 대한 제곱근이라고 부른다. - 제곱근을 표현할때는 기호로 √(루트) 를 사용한다. 제곱근의 정의 어떤 수 a에 대해 a= b^2 을 만족하는 b가 있다면 이러한 b를 a의 제곱근이라고 한다. 실수에서는 양수에 대한 제곱근이 반드시 대개 존재한다. 제곱근의 공식 - √a^2 = a - a * √b = a√b - b√a + c√b=(b+c)√a - √a * √b = √ab - √a ÷ √b = √a/√b = √(a/b) - √(a^2 * b) = a√b 연습문제 1) 9의 제곱근을 구하시오 (3,-3) 2) 다음 문제를 계산하시오. 단 근호 안의 숫자가 최소가 되도록 표현하시오. √18 + √2 = √(3^2*2)+√2=3√2 3√6 * 2√..