79brue의 PS 블로그

그리디 알고리즘은 그 발상에 따라 난이도가 천차만별이기로 유명하다. 회의실 배정과 같이 기초적인 그리디 문제는 실버에서 시작하는 반면, Scenery 같은 문제는 루비까지 올라가기도 한다. (사실 난 Scenery의 풀이를 잘 모르기 때문에 단순 그리디가 아닐 수도 있다.) 그리디 전략을 증명할 때 사용하는 방법 중 하나가 플로우를 이용하는 것이다. 플로우는 분명 OI 범위 밖이지만, 그리디 알고리즘은 OI 범위 안이고, 플로우를 이용한 증명은 플로우 없이도 할 수 있는 경우가 많아 OI에서 심심찮게 볼 수 있었다. 난 이러한 증명 방식에 대해 잘 몰랐기 때문에 이런 문제를 만날 때마다 힘들었는데, 이제는 공부해 볼 때가 되었다고 생각해 공부를 시작해 보았다. 이 글은 이해하는 데 초점을 맞추었기 때문에..

그리디 알고리즘은 그 발상에 따라 난이도가 천차만별이기로 유명하다. 회의실 배정과 같이 기초적인 그리디 문제는 실버에서 시작하는 반면, Scenery 같은 문제는 루비까지 올라가기도 한다. (사실 난 Scenery의 풀이를 잘 모르기 때문에 단순 그리디가 아닐 수도 있다.) 그리디 전략을 증명할 때 사용하는 방법 중 하나가 플로우를 이용하는 것이다. 플로우는 분명 OI 범위 밖이지만, 그리디 알고리즘은 OI 범위 안이고, 플로우를 이용한 증명은 플로우 없이도 할 수 있는 경우가 많아 OI에서 심심찮게 볼 수 있었다. 난 이러한 증명 방식에 대해 잘 몰랐기 때문에 이런 문제를 만날 때마다 힘들었는데, 이제는 공부해 볼 때가 되었다고 생각해 공부를 시작해 보았다. 이 글은 이해하는 데 초점을 맞추었기 때문에..

tl;dr 글이 너무 길어서 읽기 귀찮다면 결론만이라도 읽자. 개요 요즘 커뮤니티 대회에 관해 말이 많다. 최근 여러 대회에서 대회 이후에 문제 오류가 발견되는 상황이 있었고, 현재의 대회 검수 시스템에 대한 전반적인 재정비의 필요성이 시사된 바 있다. 나 역시 현재의 검수 시스템에 문제가 있음에 동감하는 바이지만, 이 글에서 이야기하고자 하는 바는 아니다. 이 글에서 이야기하고자 하는 것은 문제의 질에 관한 것이다. 조금 민감한 주제일 수 있다는 것을 인지하고 있고, 이 글에 적힌 건 어디까지나 내 의견일 뿐, 절대적인 것이 아님을 전제로 읽어주셨으면 한다. (비고: 글을 올리기 전 몇몇 사람들에게 피드백을 받은 결과, "좋은 문제"의 의미가 조금 모호하다는 이야기를 들었다. 내가 이 글에서 이야기하고..

제가 최근에 대회를 운영할 때 사용한 엑셀 시트를 공유합니다. Orange Cup 때 처음 사용하였고, SciOI 2022/2023, SciCom 2023 Qualification Test 등을 거치며 개선시켜 나갔습니다. 세팅 진행 상황 및 문제 검수 현황 체크, 난이도 투표, 문제 선정 등의 작업을 할 수 있습니다. 대회의 상황에 맞게 변형해서 사용하는 것도 가능합니다.