본문 바로가기

2. 정보영재교육 수업 자료

 (13)
[448] 약수 학습하기 1. 개념 소개여러분, 약수라는 말을 들어본 적이 있나요? 약수란 어떤 수를 나누어떨어지게 만드는 숫자입니다. 쉽게 말하면, 어떤 수를 나누었을 때 나머지가 0이 되면, 그 숫자는 약수라고 할 수 있습니다. 예를 들어, 12라는 숫자를 생각해 보겠습니다. • 1로 나누면 12 ÷ 1 = 12 (나머지 0, 약수입니다!) • 2로 나누면 12 ÷ 2 = 6 (나머지 0, 약수입니다!) • 3로 나누면 12 ÷ 3 = 4 (나머지 0, 약수입니다!) • 4로 나누면 12 ÷ 4 = 3 (나머지 0, 약수입니다!) 이렇게 12를 나누었을 때 나머지가 0이 되는 숫자들은 모두 12의 약수입니다.2. 실생활 예제 약수는 우리 일상에서도 쉽게 찾아볼 수 있습니다. 예를 들어, 초콜릿 12개가 들어 있는 상자가 있다..
[447] 메르센 수, 메르센 소수 1. 메르센 수\(2^n-1\) 의 꼴의 수를 메르센 수라고 합니다.메르센 수를 이진수로 나타내면 모든 자리가 1인 수입니다.2. 하노이의 탑\(n\)층의 하노이의 탑을 옮기는 횟수를 \(f(n)\)이라고 했을 때, 1층인 하노이의 탑을 옮기는 것은 1회이므로  \(f(1) = 1\)입니다.\(n\)층의 하노이의 탑을 옮기려면 다음과 같은 과정을 거칩니다.맨 밑의 한 개를 제외하고 \(n-1\)층을 일단 옮겨놓습니다. (\(f(n-1)\))맨 밑의 한 개를 옮깁니다. (\(f(1)\))다시 그 위에 \(n-1\)층을 옮겨놓으면 됩니다. (\(f(n-1)\))이 식을 정리하면 다음과 같습니다.\[\begin{aligned}f(n) &= f(n-1) \times 2 + 1 \\     &= \big(f(n-..
[444] 부동소수점의 오차 이야기 1. 부동소수점(浮動小數点)부동소수점 방식은 고정소수점 방식과 함께 컴퓨터로 소수(小數)를 나타내기 위한 방법입니다.부동소수점의 부는 不(아닐 부)가 아니라 浮(뜰 부)입니다.고정되어 있지 않고 움직인다는 뜻입니다.부동자세에서 부동은 움직이지 않는다는 뜻인데, 부동소수점의 부동은 움직인다는 뜻입니다.(연패처럼...) 십진수 \(14.2\)를 \(1.42 \times 10^1\) 처럼 나타내는 방식입니다.같은 방식으로 이진수 \(101.01\)를 부동소수점 방식으로 나타내면 \(1.0101 \times 2^2\)  입니다.https://ko.wikipedia.org/wiki/부동소수점 부동소수점 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 초기의 전기기계식 프로그래밍 가능한 컴퓨터..
[436] 피보나치 수열을 구하는 여러 가지 방법(파이썬 코드) 1. 피보나치 수열?다음 문제들을 살펴보고 공통점을 생각해봅시다. 한번에 한 칸 또는 두 칸의 계단을 올라갈 수 있습니다.이 때, n칸을 올라가는 경우의 수는 몇 가지일까요? n개의 육각형이 두 줄로 그림과 같이 배치되어 있습니다.인접한 칸으로 이동이 가능하고, 현재 칸보다 숫자가 더 큰 칸으로 이동할 수 있습니다.1에서 n까지 이동하는 경우의 수는 몇 가지일까요? 첫번째 달에는 어린 암수 토끼 한 쌍이 있습니다.어린 암수 토끼 한 쌍은 한 달이 지나면 다 큰 암수 토끼 한 쌍이 됩니다.다 큰 암수 토끼 한 쌍은 한 달이 지나면 어린 암수 토끼 한 쌍을 낳습니다.n번째 달에는 토끼가 몇 쌍일까요? 문제는 모두 다르지만, 모든 문제의 공통점은 n번째의 수가 (n-1)번째와 (n-2)번째를 더한 수가 된다는..
[435] 에라토스테네스의 체(소수 구하기) (파이썬 코드) 1. 에라토스테네스의 체(소수 구하기) (파이썬 코드)n = 50p = [True] * (n+1)p[0], p[1] = False, Falsefor i in range(2, int(n**0.5)+1): if p[i]: for j in range(i*2, n+1, i): p[j] = Falseprint([i for i in range(n+1) if p[i]])# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]풀어볼 문제: 소수 구하기(https://www.acmicpc.net/problem/1929)2. 소수(Prime Number)1 보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 말합니다.3. 소수 판..
[434] 유클리드 호제법(파이썬 코드) 1. 유클리드 호제법(파이썬 코드)a, b = 490, 350while b: a, b = b, a%bprint(a)# 70풀어볼 문제: 최대공약수와 최소공배수(https://www.acmicpc.net/problem/2609)2. 유클리드 호제법이란?유클리드 호제법은 두 수가 서로(互 서로 호) 0이 될 때까지 덜어내면(除 덜 제) 최대공약수를 찾을 수 있는 알고리즘입니다.기원전 3세기에 고대 그리스 수학자 유클리드가 집필한 에 명시되어 있습니다.이는 명시적으로 기술된 가장 오래된 알고리즘으로도 알려져 있습니다.3. 최대공약수를 구하는 과정 비교490과 350의 최대공약수를 구하는 과정을 코드로 작성해봅시다. 단순하게 1씩 증가시켜가며 두 수를 동시에 나눌 수 있는 수(공약수)의 최대값을 찾습니다...
[433] 8주차 재귀, 백트래킹 1. 재귀프로그래밍에서 재귀란 한 함수가 자신을 호출해 반복적으로 실행되는 것을 뜻합니다.이러한 함수를 재귀 함수라고 합니다. 예를 들어 다음과 같은 함수가 있다고 해봅시다.import timedef func(): print("바트가 호머가 들고 있는 그림을 보고 있어요.") print("호머가 들고 있는 그림 속에는...") time.sleep(1) func()func()# 바트가 호머가 들고 있는 그림을 보고 있어요.# 호머가 들고 있는 그림 속에는...# 바트가 호머가 들고 있는 그림을 보고 있어요.# 호머가 들고 있는 그림 속에는...# 바트가 호머가 들고 있는 그림을 보고 있어요.# 호머가 들고 있는 그림 속에는...# 바트가 호머가 들고 있는 그림을 보고 있어요.# 호머가..
[432] 7주차 동적 계획법, 누적합 1. 동적 계획법(동적 프로그래밍, Dynamic Programming; DP)가. 개요동적 계획법은 복잡한 큰 문제를 간단한 작은 문제 여러 개로 나누어 푸는 아이디어를 말합니다.분할 정복과 차이는 간단한 작은 문제가 반복되어 나타나므로 답을 저장해놓고 재사용하는 데 있습니다.동적 계획법은 구체적인 알고리즘이 아닌, 알고리즘을 설계하기 위한 접근 방법을 지칭하는 용어입니다.(ex. 분할 정복, 그리디, 백트래킹 등)나. 동적 계획법을 사용하기 위한 조건1) 최적 부분 구조(Optimal Substructure)큰 문제를 작은 여러 문제(부분 문제)로 나누어 풀기 위해서는 작은 문제의 답을 통해 큰 문제의 답을 찾을 수 있어야 합니다.예를 들어 위와 같은 지도에서 서울에서 부산까지 가는 최단 경로를 찾는..

티스토리툴바