-
Acka1357's profile image
Acka1357
December 15, 2019
최대 이분 매칭에 관한 몇 가지 정리
이분 그래프(Bipartite Graph)에서의 최대 매칭(Maximum Matching)은 최대 유량(Maximum Flow)과 같습니다. 이 글에서는 위와 같이 최대 유량과 최대 이분 매칭에 관한 기본적인 문제를 해결 할 수 있는 분들을 위해 최대 이분 매칭에 관한 대표적인 정리를 예제와 함께 다룹니다. 구성은 아래와 같습니다. Minimum Vertex Cover - BOJ 1867 돌멩이 제거 Maximum Independent Set - BOJ 11014 컨닝 2 Minimum Path Cover - BOJ 1671 상어의 저녁식사 Maximum Anti-Chain - BOJ 13441 마법의 나무 Minimum Vertex Cover Vertex...
bipartite-matching minimum-vertex-cover maximum-independent-set minimum-path-cover maximum-antichain
-
Acka1357's profile image
Acka1357
October 19, 2019
알아두면 편리한 비트 연산 몇 가지
Bitwise Operation Problem Solving을 하다 보면, 혹은 최적화 등의 작업을 하다 보면 bit 단위의 연산을 하게 될 때가 있습니다. 일반적으로 논리/정수 자료형에서 많이 사용되기 때문에 본 포스팅의 설명은 해당 두 자료형에 한하며 이를 묶어 ‘정수’라고 표현하겠습니다. 간단한 비트 연산은 언어에서 제공하는 연산자를 통해 두 개의 정수를 and, or, xor 하거나 하나의 정수를 shift, not 등으로 변형할 수 있습니다. 이 포스팅에서는 앞에서 나온 기본 단위 연산자에 관한 내용은 따로 다루지 않고, 좀 더 나아가 하라면 하겠는데...
-
Acka1357's profile image
Acka1357
September 18, 2019
2019 아주대학교 프로그래밍 경시대회(APC) 풀이
2019 아주대학교 프로그래밍 경시대회 (APC) 2019년 5월 26일 제9회 아주대학교 프로그래밍 경시대회(APC, Ajou, Programming Contest)가 열렸습니다. APC는 아주대학교 학생들을 위한 교내대회로, 경인지역 6개대학 연합 프로그래밍 경시대회 shake!에 출전할 10명의 대표학생을 선발하는 선발전을 겸하고 있습니다. 추가로 2019 APC는 성균관대학교와 한국항공대학교의 2019 shake! 학교 대표 선발전 역시 겸하였습니다. 2019 APC는 정보통신대학 학생을 위한 Divison1과 비전공생 및 복수전공생 학생을 위한 Division2로 나누어 진행되었습니다. Division1의 경우 2019 APC는 Division1 8문제와 Division2 6문제로 구성되었으며 그중 4문제가 공통문제라 총 10문제로 이루어져...
-
Acka1357's profile image
Acka1357
July 21, 2019
프로그래밍 대회를 개최하기 위한 10가지
프로그래밍 대회를 개최하기 위한 10가지 이 글은 Ajou Programming Contest(2016-19 APC), 경인지역 6개대학 연합 프로그래밍 경시대회(2016-19 shake!), 전국 대학생 프로그래밍 대회 동아리 연합 여름 대회(2016 UCPC)를 운영했던 제 경험을 토대로 작성되었습니다. 프로그래밍 대회를 개최하려는 분들께 조금이나마 도움이 되었으면 하는 마음으로 대회를 맡으며 경험했던 시행착오를 모아 필요한 10가지를 정리해보았습니다. 어디까지나 제 개인의 경험에 기반한 내용으로 대회를 열기 위해서는 이래야 한다!가 아닌 아래 과정을 고려해보자는 의미로 읽어주시면 좋겠습니다. 일의 진행 순서로 나열하긴 했지만 모든 과정은 유기적입니다. 대회의...
problem-solving competitive-programming programming-contest director setter
-
Acka1357's profile image
Acka1357
May 17, 2019
문제 출제를 위한 플랫폼 - Polygon 사용하기
Polygon이란? Polygon이란 Codeforces에서 제공하는 Competitive Programming Contest를 위한 문제 출제를 위한 플랫폼입니다. 출제를 위해 필요한 과정 - 데이터 제작, 검증, 솔루션 검증 등에 굉장히 유용한 기능들이 많으며 그 과정을 다른 사람과 공유하며 협업할 수도 있습니다. 폴리곤에서의 작업은 각 문제 단위로 동작합니다. 문제를 등록하는 방법부터 완성된 문제를 패키지로 다운받는 방법까지, 필요한 기능들을 간략히 확인하고 언제 어떤 메뉴를 사용해야 하는지 문제 출제 단계에 따라 익혀봅시다. 아, 그 전에 회원가입은 다들 하셔야겠죠? 문제 등록하기 폴리곤에 로그인하면 아래와 같은...
Polygon Codeforces problem-solving competitive-programming programming-contest setter
-
Acka1357's profile image
Acka1357
April 10, 2019
기본적인 Git 사용법과 Pull Request를 통해 프로젝트 기여하기
VCS? Git? GitHub? Git이란 버전 관리 시스템(VCS, Version Control System)의 한 종류입니다. 그렇다면 여기서 말하는 버전 관리란 무엇이고, 왜 필요할까요? 버전 관리란 이름 그대로 여러 파일을 하나의 버전으로 묶어 관리합니다. A라는 소스코드의 묶음이 있을 때, 이를 버전1이라는 이름으로 저장해봅시다. 이후 버전1에서 파일을 추가하거나, 삭제하거나, 수정하는 등의 작업을 거쳐 버전2라는 이름으로 저장합니다. 마찬가지로 버전2에서 버전3를 만듭니다. 아차, 그런데 버전2에서 수정한 파일 때문인지 오류가 생겼습니다. 이때 우리는 이전에 저장해둔 버전1을 불러와 다시 작업할 수 있습니다. 만약 문제가...