초등교사 김우일

인기 글

• 2. 정보영재교육 수업 자료 [436] 피보나치 수열을 구하는 여러 가지 방법(파이썬 코드) 1. 피보나치 수열?다음 문제들을 살펴보고 공통점을 생각해봅시다. 한번에 한 칸 또는 두 칸의 계단을 올라갈 수 있습니다.이 때, n칸을 올라가는 경우의 수는 몇 가지일까요? n개의 육각형이 두 줄로 그림과 같이 배치되어 있습니다.인접한 칸으로 이동이 가능하고, 현재 칸보다 숫자가 더 큰 칸으로 이동할 수 있습니다.1에서 n까지 이동하는 경우의 수는 몇 가지일까요? 첫번째 달에는 어린 암수 토끼 한 쌍이 있습니다.어린 암수 토끼 한 쌍은 한 달이 지나면 다 큰 암수 토끼 한 쌍이 됩니다.다 큰 암수 토끼 한 쌍은 한 달이 지나면 어린 암수 토끼 한 쌍을 낳습니다.n번째 달에는 토끼가 몇 쌍일까요? 문제는 모두 다르지만, 모든 문제의 공통점은 n번째의 수가 (n-1)번째와 (n-2)번째를 더한 수가 된다는..
• 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. 알고리즘 공부 [424] 삽입 정렬(Insertion Sort) 1. 삽입 정렬 개념이미 정렬되어 있는 배열에 새로운 수를 추가하는 것은 아주 간단합니다.이런 방법을 바탕으로 범위를 늘려가며, 다음 원소를 이미 정렬된 범위 안에 삽입하는 방식으로 정렬합니다.마치 손 안의 카드를 정렬하는 방법과 유사합니다.2. 삽입 정렬 예제삽입 위치를 찾기 위해 정렬되어 있는 부분을 탐색하는 과정을 위 그림을 통해 볼 수 있습니다.이 과정을 이분 탐색으로 \(O(\log{n})\)의 시간에 빠르게 찾을 수 있을 것 같습니다.하지만 선택한 원소를 해당 위치에 삽입하기 위해서는 뒤쪽의 모든 원소를 한 자리씩 옮겨야하므로 결국 \(O(n)\)만큼의 시간이 소요되어 의미가 없어집니다.3. 삽입 정렬 코드nums = [5, 3, 4, 1, 2]def insertion_sort(nums): ..
• 3. 알고리즘 공부 [458] 시간복잡도와 1초에 해결 가능한 입력의 크기 1. PS에서 1초 동안 가능한 연산 횟수프로그래밍 대회나 알고리즘 문제 풀이에서 시간 제한 1초는 약 1억 번 정도의 연산 수행 제한을 의미합니다.여기서 말하는 연산은 사칙 연산, 비교 연산, 대입 연산 등으로 이루어진 O(1) 시간에 수행되는 연산을 의미합니다.이 수치는 실제 CPU가 수행하는 연산 시간이 아니라, 온라인 저지 시스템에서 시간 초과(TLE)를 피하기 위한 기준선입니다.2. 시간 복잡도에 따른 해결 가능한 입력의 크기1초에 1억 번의 연산이 가능하다고 했을 때, 시간 복잡도에 따른 1초에 해결 가능한 입력의 크기는 다음과 같이 주먹구구식으로 계산할 수 있습니다.입력 N의 크기시간 복잡도최악의 경우 연산 횟수\(N \le 11\)\(O(N!)\)\(11! = 39,916,800\)\(N ..
• 3. 알고리즘 공부 [457] 백준 2225번 합분해 - 최단경로 경우의 수와 중복 조합 1. 문제https://www.acmicpc.net/problem/22252. 문제 이해0부터 N까지의 정수 중에 아무 수나 K개(중복 가능)를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제입니다.예를 들어 N이 5이고 K가 3이면,위 그림과 같이 21가지입니다.3. 해결 방법가. 동적 프로그래밍숫자가 K개가 될 때까지 하나씩 추가해가며 합이 N보다 작거나 같은 경우의 수를 관리해봅시다.먼저, 숫자를 1개만 사용하면 경우의 수는 각각 고른 숫자만큼 합이 되므로 경우는 모두 각각 1가지 입니다.다음으로 숫자를 2개 사용하는 경우에는 이전에 숫자 1개를 사용하여 만든 값을 활용하여 빠르게 계산할 수 있습니다.(DP)이렇게 표를 채워가면 3중 for문으로 채워지게 됩니다.(행, 열, 이전 행)그러나 굳이..
• 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등분을 할 수 있습니다.