멀티탭 스케줄링 문제 링크 그리디 연습 겸 풀어봤다. 풀이 더보기 전기용품을 사용하려 할 때 다음의 두 가지 선택이 있다: 이미 플러그가 꽂혀 있어서 그대로 사용한다 기존의 플러그 중 하나를 뽑고 새 플러그를 꽂아 사용한다. 2번에서 어떤 플러그를 뽑을지 선택하는 것이 관건이다. 나중에 제일 적게 등장할 플러그를 뽑을 것인가? 아니다. 가장 나중에 등장할 플러그를 뽑을 것인가? 맞는 것 같다. 이는 가장 나중에 등장하지 않는 플러그를 뽑았다고 가정했을 때, 이 보다 가장 나중에 등장하는 플러그를 뽑는 것이 항상 유리하거나 같다는 발상을 통해 확인할 수 있다. #include using namespace std; using ii = pair; using ll = long long; #define rep(i..
학교 선생님께서 전용 Online Judge를 만들어 주셨다. CSL Hust OJ 기반이다. 선생님께 부탁드려서 admin 권한을 받고 문제를 추가 중이다. 대회 기능도 테스트 해보았다. 이 OJ는 불행히도 서브태스크 문제를 못 만들고, 문제에 달린 게시판도 없다. 그러나 Special Judge는 지원한다. 결국 Codeforces 기능 정도를 지원한다고 보면 되겠다. 사실 서브태스크 문제를 만들 정도로 학생들의 수요가 높지 않아서 별 상관은 없다. 그래도 나중에 여건이 된다면 선생님께 여쭤서 사이트를 수정해 보는 것도 괜찮을 것 같다. 디자인도 좀 개선하고. 좋은 점은 CSL이 정보 교사 협회인가 뭔가여서 코드업 기초 문제들이 자동으로 수록되어 있다. 덕분에 학생들이 나름 참여하고 있다. 데이터를 ..
내일 국민대 알고리즘 대회라서 장장 두 달만에 키보드를 잡아보았다. 사실 그 사이에 쇼미더코드 치느라 딱 하루 한 적이 있긴 하다. 문제집 문제 링크 위상정렬 + 순서 관계 없는 것들끼리는 번호순으로. 예전에 풀어봤던 문제라 거의 5분 컷 한 것 같다. 풀이 더보기 칸 알고리즘으로 구현해야 한다. 코사라주 알고리즘(역간선 활용)으로는 아마 방법이 없을 것이다. 기존의 칸 알고리즘의 큐 부분을 우선순위 큐로 바꾸어 풀어주면 된다. #include #define rep(i,a,b) for (auto i = (a); i sync_with_stdio(0); cin >> n >> m; rep(i,1,m) { int a, b; cin >> a >> b; adj[a].push_back(b); ind[b]++; } r..
프로베니우스의 동전 문제는, $a$원의 동전과 $b$원의 동전만으로 만들 수 없는 금액의 최댓값을 구하는 문제입니다. (이때, $a$, $b$는 자연수입니다.) 공식만 알고 있었는데, 정확한 적용 범위가 헷갈려서 아예 증명을 해봅니다. 잘못된 부분이 있다면 알려주세요 :) 표기 $\mathbb N_0:=\ $음이 아닌 정수 집합 $\mathbb N_+:=\ $양의 정수 집합 $\text{Theorem. }$ 서로소인 두 정수 $a,b\in \mathbb N_+$에 대해 $an+bm(n, m\in \mathbb N_0)$로 표현할 수 없는 최대의 정수는 $ab-a-b$이다. 보조정리 1과 보조정리 2가 참임을 보이면 theorem도 참이다. 보조정리 1. $an+bm=ab-a-b$인 $(n,m)$은 존재하..
구체수학과 koosaga님 블로그를 참고했습니다. 수학적 귀납법 정수 $n$에 관한 어떤 명제가 모든 $n\ge n_0$에 대해 참임을 증명하는 일반적인 방법이다. 이는 2가지 단계로 나뉜다. 기초(basis) 단계: $n_0$에 대한 증명 귀납(induction) 단계: $n_0,\cdots, n-1$에 대해 증명되었다는 가정 하에 $n>n_0$에 대해 증명 하노이탑 세 개의 탑에서 하노이탑 규칙에 따라 옮기는 최소 이동 횟수를 구하면 된다. 우선, 정의를 잘 하는 것이 중요하다. 책의 필자는 명명정복이라고 한다. $T_n:=$ 규칙 하에 다른 한 기둥으로 옮기는데 필요한 최소 이동 횟수 1번 기둥에서 2번 기둥으로 위쪽 $n-1$개의 원판을 옮기고, $n$번째 원판을 3번 기둥으로 옮긴 후 2번 기둥..
구체수학 일부 합을 공략할 때 유용한 일반 전략들. 일부는 점화식으로 일반항 구하는 데에도 사용 가능. 답을 추측하고 귀납법으로 증명한다 비약이 크기 때문에(우선 공식을 추측해야 하니까) 필자는 다른 안정적인 방식으로 닫힌 형식을 구하자고 이런 방법들을 소개한다. 합을 어지럽힌다 점화식으로 일반항을 구할 때 원래 "꼬리 자르기"라고 부르던 방식을, 책에서는 "섭동법"이라는 멋진 이름으로 소개한다. 등비수열의 합을 구할 떄 쓰는 방식이기도 한데, 등차수열의 합을 구할때는 잘 안 먹힌다. 그런데, 그림 가운데의 관찰을 바탕으로 한 차원 높게 잡고 구하면 구할 수 있다. 레퍼토리를 구축한다 $\square_n=\square_{n-1}+n^2;\; \square_0=0.$ $R_n=R_{n-1}+\beta+\g..
어떤 고수 분의 정올 필기 점수가 꽤 낮다는 정보를 보았다. 기존의 KOI 1차 풀이를 적는 블로거들이나 한컴 설명회에서 공통적으로 얘기하던 것은, 실기 문제를 돌리는 것이 곧 필기 대비이고 필기 점수는 상의 색깔 정도를 좌우할 뿐이라는 것이였다. 그런데 이번 필기를 보고 생각이 바뀌었다. 정올러들은 기본적으로 틀리면 다시 제출하고, 여러 테스트를 거칠 기회를 가진 채로 연습한다. 그래서 실수 한 번에 나락을 가는 수학 문제들에 취약할 것이라고 생각한다. 결론적으로, 필기에도 시간 투자를 꾸준히 해야 한다는 것이 내 생각이다. 조합, 대수 파트 공부를 다시 해야겠다.
글을 쓰는 시점은 6월 5일 오전 1시이다. solved.ac 시즌 2가 곧 오전 6시에 시작한다. 첫 시즌 공지 때에는 목표를 2주 정도 동안 Diamond 3로 잡았다. 그런데, 정올을 망친 뒤 슬럼프를 잠깐 가지고 해서 좀 더뎌졌다. 그래서 Diamond 4로 목표를 낮췄는데, 더 우선순위인 일이 생겨 티어를 높이는 것을 중단하였다. 그래서 아쉽게 5시간 남긴 상황에서 D4 - 32로, D4 달성은 무리라 판단하고 이만 자려고 한다. 한 2주 정도 더 레이팅 올리기에 여념을 쏟지 못할 것 같다. 아무튼 시즌 2 기대된다. +) PS 일지도 한동안 OI 문제 풀이에 쏟느라 안 하고 있었는데, 이제는 좀 적을지도? +) 저번에 Bitaro's Party에 알 수 없는 이유로 cin/cout을 억까 당한..
