초등교사 김우일

인기 글

• 3. 알고리즘 공부 [421] 이분 탐색(Binary Search) 조건 분기 쉽게 이해하기(Lower Bound, Upper Bound) 1. 이분 탐색이란?정렬되어 있는 범위에서 원하는 값을 찾기 위해 반씩 줄여가며 탐색하는 알고리즘입니다.정렬만 되어 있다면, 선형적으로 다 탐색할 필요 없이 범위가 반씩 줄어들기 때문에 시간복잡도가 \(O(\log{n})\)으로 상당히 효율적인 알고리즘입니다.영어로 Binary Search입니다.Binary라는 단어가 한국어로 번역되면서 이진 탐색, 이진 검색 등으로 사용됩니다.하지만 탐색 과정을 살펴보면 범위를 반으로 쪼개며 진행되기 때문에 이분 탐색이라는 용어가 더 직관적인 것 같습니다. https://ko.wikipedia.org/wiki/이진_검색_알고리즘 이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 이진 검색 알고리즘(binary search algor..
• 2. 정보영재교육 수업 자료 [436] 피보나치 수열을 구하는 여러 가지 방법(파이썬 코드) 1. 피보나치 수열?다음 문제들을 살펴보고 공통점을 생각해봅시다. 한번에 한 칸 또는 두 칸의 계단을 올라갈 수 있습니다.이 때, n칸을 올라가는 경우의 수는 몇 가지일까요? n개의 육각형이 두 줄로 그림과 같이 배치되어 있습니다.인접한 칸으로 이동이 가능하고, 현재 칸보다 숫자가 더 큰 칸으로 이동할 수 있습니다.1에서 n까지 이동하는 경우의 수는 몇 가지일까요? 첫번째 달에는 어린 암수 토끼 한 쌍이 있습니다.어린 암수 토끼 한 쌍은 한 달이 지나면 다 큰 암수 토끼 한 쌍이 됩니다.다 큰 암수 토끼 한 쌍은 한 달이 지나면 어린 암수 토끼 한 쌍을 낳습니다.n번째 달에는 토끼가 몇 쌍일까요? 문제는 모두 다르지만, 모든 문제의 공통점은 n번째의 수가 (n-1)번째와 (n-2)번째를 더한 수가 된다는..
• 2. 정보영재교육 수업 자료 [59] 여러 명이 자리를 바꿔 앉는 경우의 수 - 완전 순열 1. 문제 상황갑자기 재밌는 문제가 떠올랐습니다.\(n\)명의 사람들이 자리를 바꿔 앉으려고 합니다. 이 때 모두가 자기의 자리에는 앉지 않으면서, 자리를 바꿔 앉는 경우의 수를 \(a_{n}\)이라고 할 때, \(a_{n}\)은 얼마일까요?2. 사람 수가 적을 때부터 생각해보기\(n\)이 \(\mathbf{1}\)이면 바꿔 앉을 의자가 없기 때문에 0가지 입니다. (\(a_{1}=0\))\(n\)이 \(\mathbf{2}\)이면 두 명이 서로 바꿔 앉는 방법 밖에 없기 때문에 1가지 입니다. (\(a_{2}=1\)) \(n\)이 \(\mathbf{3}\)일 때를 생각해봅시다. 일단 세 명이서 자리에 앉는 모든 경우를 생각해봅시다.\(\left\{1, 2, 3\right\}\), \(\left\{1, 3..
• 3. 알고리즘 공부 [248] 비트마스크 + 동적 프로그래밍(DP) 1. 비트마스크 비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말합니다. 이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 경우는 두 가지입니다. 보통 어떤 비트가 1이면 "켜져 있다"라고 말하며, 0이면 "꺼져 있다"라고 말합니다. https://ko.wikipedia.org/wiki/마스크_(컴퓨팅) 마스크 (컴퓨팅) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서 마스크(mask) 또는 비트마스크(bitmask)는 특히 비트 필드에서 비트 연산에 사용되는 데이터이다. 마스크를 사용하면 바이트, 니블, 워드 등의 다 ko.wikipedia.org 가. 비트 크기 ..
• 3. 알고리즘 공부 [429] 계수 정렬(Counting Sort) 1. 계수 정렬 개념배열에 존재하는 원소 중 최대값을 범위로 가지는 새로운 배열을 만들어, 각 원소의 개수를 기록해 놓음으로서 선형 시간 내에 정렬을 할 수 있습니다.계수 정렬을 안정적인 정렬로 이용하기 위해서 누적합을 계산하여 원소들의 위치를 지정합니다.기수 정렬과 마찬가지로 비교 기반 정렬 알고리즘이 아닙니다.원소의 범위가 넓을수록 원소의 개수를 관리할 배열의 크기가 커지므로, 원소의 범위가 좁은 특별한 상황에서 사용됩니다.2. 계수 정렬 예제4, 2, 2, 8, 3, 3, 1 을 정렬해봅시다.각 원소의 개수를 기록합니다.기록된 개수의 누적합을 계산합니다.누적합 결과는 각 원소의 정렬 후 위치가 될 것입니다.기존 배열의 뒤에서부터 원소를 새로운 자리에 위치시킵니다.새로운 자리의 위치는 누적합한 결과값..
• 3. 알고리즘 공부 [456] 색종이 3등분 접는 법 - 두 일차함수의 교점 1. 색종이 3등분 접는 법2. 왜 그럴까?색종이의 한 변의 길이를 1이라고 가정합니다.비스듬하게 접은 선을 함수의 그래프로 표현하면,\(y = -x + 1\), \(y = 2x\), \(y = \frac{1}{2} x\) 으로 나타낼 수 있습니다.이 함수의 그래프와 교점을 살펴보면 \( ( \frac{1}{3}, \; \frac{2}{3} ) \) 와 \( ( \frac{2}{3},\; \frac{1}{3} ) \) 입니다. 따라서 이 교점을 기준으로 접으면 3등분을 할 수 있습니다.