1학기 초등학생 대상으로 진행한 수업에 이어 같은 컨셉의 수업을 중, 고등학생 대상으로 개설해 운영해보았다. 첫 학교에서 사직하고 수학 강사하던 2018년 이후로 중, 고등학생 대상 수업이 처음이라 약간 긴장했으나, 그럴 필요가 없었다. 어차피 정규 교육과정에 존재하지도 않는 내용. 내 마음대로 해보면 되는 수업이었던 것... 1. 수업 준비초등학생을 대상으로 한 같은 수업을 이미 1학기 때 36차시 동안 진행했다. 초기 목표는 수업 후반부에는 최단경로, 최소스패닝트리 등의 다소 복잡한 알고리즘까지 다루어 보는 것이었다. 예상되는 문제들은 영타는 고사하고 키보드 입력 방식 자체가 익숙하지 않은 학생들을 대상으로 한다는 점과 초등학생의 수준을 한참 뛰어넘는 추상화 능력이 요구된다는 점이었다. 예상대로 이 ..

게임을 즐기다보면 금방 익숙해지는 흔히 '커맨드'라 불리는 것이 있다. WASD 또는 화살표키로 전후좌우 움직임을 조절하거나,shift키로 걷기/뛰기 전환 내지는 웅크리기가 된다던가,f키로 탈 것에 타거나 내리기가 되고,장애물 앞에서 space키를 누르면 장애물을 뛰어 넘거나 엄폐 동작을 취하기도 한다.그 밖에도 게임마다 필요한 행동의 커맨드들이 있다. 이런 커맨드는 어떤 조건에 따라 어떤 방법으로 제어되고 있을까? 또 게임을 계속 하다보면 특정 커맨드는 특정 조건이 만족되어야만 실행이 가능하며, 연계되는 커맨드가 있는 반면, 특정 커맨드를 통해 이전 동작을 중간에 취소(모션 캔슬)할 수도 있다. 1. 마구잡이 개발교육용 프로그래밍 언어 "엔트리"로 수업에 예제로 활용하기 위한 RPG를 개발하고 있다. ..

시간 제한메모리 제한1초1024MB문제코코는 초콜릿 공장을 운영하고 있다. 이 공장의 기계는 초콜릿을 3 * N 크기(가로 N, 세로 3)의 직사각형 덩어리로 생산한다. 코코는 이 덩어리를 floor(3N/2)개의 1 * 2 또는 2 * 1 크기의 초콜릿으로 나누어 판매하려고 한다. 어째서인지 N이 항상 홀수라서, 코코는 1 * 1 조각을 하나 골라서 잘라 먹고 남은 부분을 나누어 팔기로 했다. N의 값과 코코가 먹은 조각의 위치(R행 C열)가 주어졌을 때, 남은 초콜릿 덩어리를 나누는 방법의 수를 계산해보자. 입력첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스마다 N, R, C의 값이 한 줄에 주어진다.1 ≤ T ≤ 1e51 ≤ N ≤ 1e5, N은 홀수1≤ R ≤ 3, 1 ≤ C ≤..

1. 최대 유량(Network Flow) 문제최대 유량 문제는 유량이 시작되는 소스(source)와 유량이 도착하는 싱크(sink)가 존재하는 그래프에서 최대로 생성될 수 있는 유량을 찾는 문제입니다. 그래프의 간선들을 타고 유량이 흐르는데 보통 방향 그래프가 다뤄지는 경우가 많으나 방향이 없는 그래프가 주어지기도 합니다. 각 간선들은 흐를 수 있는 유량의 제한인 용량(capacity)이 있습니다. 이 문제를 해결할 수 있는 방법을 처음 제안한 두 사람의 이름을 딴 포드-풀커슨 알고리즘이 있습니다. 이 알고리즘은 방법론에 대한 내용이고 에드몬드-카프 알고리즘에서 O(VE^2)의 BFS를 통한 유량의 증가 경로 탐색 방법이 제시되었습니다. 이후 레벨 그래프를 활용해 O(V^2E)로 개선한 디닉(디니츠) 알..

1. 세포 자동자(Cellular Automata)세포 자동자(CA)란, 유한하게 정의된 상태를 가질 수 있는 셀을 규칙적으로 배치하여 서로 관련있는 셀들이 영향을 주고 받으며 변화하는 모형을 말합니다. 뭐라고 복잡한데 이런 문제가 있어요.백준 7569번 : 토마토"익은" 상태의 토마토가 인접한 "익지 않은" 상태의 토마토를 익게 하는 규칙입니다. "토마토가 없는" 상태의 칸은 영향을 받지 않습니다. 이 문제는 3차원으로 나열된 각 칸이 셀이 되고 토마토가 익었거나 익지 않았거나 없는 3가지 상태를 갖는 세포 자동자라고 볼 수 있습니다. 2. 생명 게임(Game of Life)존 콘웨이가 만든 게임입니다. 이 게임은 초기 상태만 정해주면 그 뒤는 규칙에 따라 알아서 흘러가는 감상 게임이에요. 존 콘웨이는..

https://www.acmicpc.net/problem/32721 시간 제한메모리 제한1초1024MB문제건덕이가 설립한 오리 왕국은 1부터 N까지 N개의 도시로 이루어져 있다. 각 도시는 다른 도시로 향하는 일방통행 도로를 단 한 개만 가지고 있다. 왕국을 다스리던 건덕이는 어떤 도시에서 도로를 이용해 도달할 수 없는 도시가 있음을 알아챘다. 건덕이는 어떤 도시에서 출발하더라도 모든 도시를 방문할 수 있도록 도로를 최소한으로 수정하기로 했다. 건덕이는 도로를 아래와 같은 방법으로 수정한다. 도시 A에서 출발하는 도로의 목적지를 수정한다. (1 ≤ A ≤ N ) 건덕이를 위해 어떤 도시에서 출발하더라도 모든 도시를 방문할 수 있도록 만드는 도로의 최소 수정 횟수를 구해주자! 입력첫째 줄에 도시의 개수 N..

import sysinput = sys.stdin.readlinet = [(-1, 0), (1, 0), (0, -1), (0, 1)]d = [(-2, 0), (2, 0), (0, -2), (0, 2)]def bin_check(): ret = 0 t = 1 for j in range(3, 6): if grid[0][j]: ret |= t t 여기에 찾았던 기록들 set으로 관리해주면 되는데 그 부분 커밋 안해서 사라짐

1. SCC문제1) SCC 구성하기백준 2150번 Strongly Connected Component백준 11097번 도시 계획 : 최소 간선으로 scc를 만족하는 그래프 만들기백준 25488번 토큰 : [★★★] scc별 빨간 카드, 파란 카드에 적힌 숫자의 수 비교하기백준 1506번 경찰서 : [★★] scc마다 최소 비용만 찾아서 다 더하기 2) a에서 b까지 가장 많은 정점을 방문하는 경로백준 1471번 사탕 돌리기 : [★★★] 모든 정점의 진출차수가 1인 그래프백준 19649번 미담 전하기 : 직접 전파자를 포함하지 않아야 하는 조건 처리가 까다로움백준 2152번 여행 계획 세우기 : [★★★] 같은 컴포넌트의 요소들은 크기만 알면 방문한 셈 칠 수 있음백준 4013번 ATM : [★★★★★]..