이동식 저장소

요즘은 이분 매칭 문제를 풀고 있다. 1574번: 룩 어택 첫째 줄에 체스판의 크기 R과 C가 주어지고, 빈 칸의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 빈 칸의 좌표가 주어진다. 좌표는 (행, 열)의 형태로 주어지고, 가장 윗 행은 1번 행이고, 가장 왼�� www.acmicpc.net $R \times C$ 크기의 체스판에 룩을 최대한 많이 배치하는 문제이다. 이때 룩끼리 공격 가능해서는 안 된다. 룩은 자신이 위치한 행 또는 열의 모든 칸을 공격할 수 있다. 비슷한 문제로 N-Queen이 있다. 이 문제는 $N \times N$의 체스판 위에 퀸을 서로 공격할 수 없도록 최대한 많이 배치하는 문제이다. 퀸은 행과 열에 더하여 대각선까지 공격할 수 있기 때문에 특정한 형태로 모델링하기 까다롭다..

4시간동안 맞왜틀 해서 화나서 쓴다. 9577번: 토렌트 희원이가 사용하는 ACM토렌트는 하나의 파일을 공유받을 때 여러 조각으로 나누어, 조각을 지닌 시드가 접속하는 시간에 시드로 부터 일부 조각을 전송 받아 파일을 완성시키는 방법으로 파일이 www.acmicpc.net 회원들로부터 $n$개의 파일 조각을 다운로드하는 데 걸리는 최소의 시간을 구하는 문제이다. 어떤 파일 조각을 아무 회원으로부터 다운로드해도 되기 때문에, 회원에 대한 정보는 무시하고 파일 조각과 시간의 관계만 생각하자. 전형적인 이분 매칭 문제이다. 매칭하는 방향은 두 가지가 있는데, 나는 조각에 시간을 매칭했다. 각 조각을 다운로드할 시작 시각을 매칭하는데, 이때 시작 시간을 매칭하므로 그래프를 만들 때 $t_{2}$는 제외해야 한다..

11376번: 열혈강호 2 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고, � www.acmicpc.net 직원에게 할 일을 짝지어 주는 이분 매칭 문제이다. 단 직원이 최대 두 개의 일을 할 수 있다고 하는데, 당황할 필요는 없다. 이분 매칭을 다시 생각해 보자. 일반적인 이분 매칭에서는 한 사람당 최대 하나의 일만 짝지을 수 있다. 최대 두 개의 일을 짝지을 수 있다는 말은, 본질적으로 직원 $n$명의 분신(??)이 각각 존재하여 직원과 직원의 분신에 최대 하나의 일을 짝지을 수 있다는 말과 같다. 또는 $2n$명의 직원을 생각하되 두 직원을 하나로 ..

1학기 조별과제, 계절학기, 기타 등등 이런저런 사정으로 인해 거의 세 달 가까이 코포를 하지 못했다. 그래서 내 실력이 얼마나 늘었는지, 또는 늘기는 했는지 알아보기 위해 대회에 가상으로 참여해 보기로 했다. 코드포스의 대회에 Virtual Participation을 신청하면 실시간처럼 대회에 참여할 수 있다. 물론 이미 끝난 대회만 가능하다. 대회는 내가 가장 많이 참여했던 Div.3을 선택했다. Dashboard - Codeforces Round #656 (Div. 3) - Codeforces codeforces.com A. Three Pairwise Maximums $x, y, z$가 주어질 때, $x = max(a, ~b), ~y = max(a,~ c), ~z = max(b, ~c)$를 만족시키..

IntelliJ, PyCharm IDE와 Kotlin을 개발한 체코의 JetBrains에서 프로그래밍 학습 사이트 Hyperskill을 운영한다. 한달 이용료는 $24.9인데, 나는 초기 유저 특전으로 12개월 무료 이용권을 받아서 쓰고 있다. 그래도 퀄리티는 꽤 좋은 편이다. JetBrains Academy - Learn programming by building your own apps Get theory, practice coding and move beyond programming challenges to building your own working projects. hyperskill.org 구성 현재 Web, Java, Kotlin, Python 과정을 운영하고 있다. 이 중 Web과 Kot..