초등교사 김우일

인기 글

• 2. 정보영재교육 수업 자료 [436] 피보나치 수열을 구하는 여러 가지 방법(파이썬 코드) 1. 피보나치 수열?다음 문제들을 살펴보고 공통점을 생각해봅시다. 한번에 한 칸 또는 두 칸의 계단을 올라갈 수 있습니다.이 때, n칸을 올라가는 경우의 수는 몇 가지일까요? n개의 육각형이 두 줄로 그림과 같이 배치되어 있습니다.인접한 칸으로 이동이 가능하고, 현재 칸보다 숫자가 더 큰 칸으로 이동할 수 있습니다.1에서 n까지 이동하는 경우의 수는 몇 가지일까요? 첫번째 달에는 어린 암수 토끼 한 쌍이 있습니다.어린 암수 토끼 한 쌍은 한 달이 지나면 다 큰 암수 토끼 한 쌍이 됩니다.다 큰 암수 토끼 한 쌍은 한 달이 지나면 어린 암수 토끼 한 쌍을 낳습니다.n번째 달에는 토끼가 몇 쌍일까요? 문제는 모두 다르지만, 모든 문제의 공통점은 n번째의 수가 (n-1)번째와 (n-2)번째를 더한 수가 된다는..
• 3. 알고리즘 공부 [424] 삽입 정렬(Insertion Sort) 1. 삽입 정렬 개념이미 정렬되어 있는 배열에 새로운 수를 추가하는 것은 아주 간단합니다.이런 방법을 바탕으로 범위를 늘려가며, 다음 원소를 이미 정렬된 범위 안에 삽입하는 방식으로 정렬합니다.마치 손 안의 카드를 정렬하는 방법과 유사합니다.2. 삽입 정렬 예제삽입 위치를 찾기 위해 정렬되어 있는 부분을 탐색하는 과정을 위 그림을 통해 볼 수 있습니다.이 과정을 이분 탐색으로 \(O(\log{n})\)의 시간에 빠르게 찾을 수 있을 것 같습니다.하지만 선택한 원소를 해당 위치에 삽입하기 위해서는 뒤쪽의 모든 원소를 한 자리씩 옮겨야하므로 결국 \(O(n)\)만큼의 시간이 소요되어 의미가 없어집니다.3. 삽입 정렬 코드nums = [5, 3, 4, 1, 2]def insertion_sort(nums): ..
• 3. 알고리즘 공부 [474] 비재귀 세그먼트 트리(lazy propagation) 자료구조 측면의 핵심일반적인(재귀) 세그먼트 트리는 완전 이진 트리 - 리프 노드에 원소가 저장되지만, 높이 차가 있을 수 있다.비재귀 세그먼트 트리는 포화 이진 트리 - 일단 충분한 크기의 포화 이진 트리를 만들고, 리프 노드에 원소를 채운다. 1. 비재귀 세그먼트 트리 구현 코드(구간 합)arr = [1, 2, 3, 4, 5, 6, 7]length = 7h = (length-1).bit_length()N = 1 0: for i in (l>>s, r>>s): if lazy[i] != 0: apply(i 1: for i in (l>>1, r>>1): tree[i] = tree[i>= 1 r >>= 1 ..
• 3. 알고리즘 공부 [422] 버블 정렬(Bubble Sort) 1. 버블 정렬 개념맨 앞에서부터 맨 뒤까지 인접한 두 원소를 차례대로 비교합니다.비교한 결과 더 큰 원소가 앞에 있을 경우, 비교한 두 원소의 자리를 바꿔줍니다.(제자리 정렬)이 과정을 한 번 마치면 배열의 맨 뒤에는 가장 큰 원소가 위치합니다.따라서 이 과정을 범위를 한 칸씩 줄여가며 계속해서 반복합니다.2. 버블 정렬 예제3. 버블 정렬 코드nums = [5, 3, 4, 1, 2]def bubble_sort(nums): for i in range(1, len(nums)): for j in range(len(nums)-i): if nums[j] > nums[j+1]: nums[j], nums[j+1] = nums[j+1], nums[j]..
• 3. 알고리즘 공부 [421] 이분 탐색(Binary Search) 조건 분기 쉽게 이해하기(Lower Bound, Upper Bound) 1. 이분 탐색이란?정렬되어 있는 범위에서 원하는 값을 찾기 위해 반씩 줄여가며 탐색하는 알고리즘입니다.정렬만 되어 있다면, 선형적으로 다 탐색할 필요 없이 범위가 반씩 줄어들기 때문에 시간복잡도가 \(O(\log{n})\)으로 상당히 효율적인 알고리즘입니다.영어로 Binary Search입니다.Binary라는 단어가 한국어로 번역되면서 이진 탐색, 이진 검색 등으로 사용됩니다.하지만 탐색 과정을 살펴보면 범위를 반으로 쪼개며 진행되기 때문에 이분 탐색이라는 용어가 더 직관적인 것 같습니다. https://ko.wikipedia.org/wiki/이진_검색_알고리즘 이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 이진 검색 알고리즘(binary search algor..
• 2. 정보영재교육 수업 자료 [336] python 반올림(round) 주의사항 및 사사오입 구현하기 1. 반올림의 종류https://ko.wikipedia.org/wiki/반올림 반올림 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전.ko.wikipedia.org가. 사사오입우리가 흔히 알고 있는 반올림입니다.반올림하고자 하는 자릿수가 5일 경우 올립니다.예를 들어, 5.5와 6.5를 소수 첫째 자리에서 반올림하면 각각 6와 7이 됩니다.나. 오사오입통계학과 공학에서 사용하는 반올림입니다.반올림하고자 하는 자릿수가 5일 경우, 그 앞 자릿수가 짝수면 버리고, 홀수면 올립니다.즉, 반올림된 자릿수는 무조건 짝수가 됩니다.예를 들어, 5.5와 6.5를 소수 첫째 자리에서 반올림하면 둘 다 6이 됩니다.2. 파이썬의 round 함수파이썬의 round 함수는 오사오입의 반올림을 사용합니다.위..