kth990303의 코딩 블로그

건국대학교에서 교내 알고리즘 경진대회가 KUPC 2023이라는 이름으로 개최됐다! 나는 작년에 KUPC 2022를 개최하고 운영한 경험이 있다. 해당 경험에 대한 후기는 아래 블로그 포스팅으로 작성해놓았다. https://kth990303.tistory.com/400 [221203] KUPC 2022 출제 및 운영 후기 이 글은 문제에 대한 스포일러가 존재하지 않습니다. 단, 난이도 스포일러는 일부 존재합니다. 우리 학교 내에서 알고리즘 경진대회를 운영 및 출제해보았다! 그동안 알고리즘 대회를 주최하고 kth990303.tistory.com 하지만 2023년에는 PS 및 알고리즘 공부를 거의 하지 않고 백엔드 개발, 또는 회사일에 전념하곤 했다. 그래서 사실 이번 KUPC 2023은 참가할지 말지 고민을..

이 글은 문제에 대한 스포일러가 존재하지 않습니다. 단, 난이도 스포일러는 일부 존재합니다. 우리 학교 내에서 알고리즘 경진대회를 운영 및 출제해보았다! 그동안 알고리즘 대회를 주최하고 싶다고 생각해두고, 복학하게 되면 한번쯤은 대회를 열어봐야겠다고 생각하긴 했다. 다행히 riroan 형이 대회를 주최할 생각이 있다고 했고, 선뜻 나를 운영/출제진으로 초대해준 덕분에 휴학생 신분임에도 불구하고 대회에 출제 및 운영해볼 수 있었다! 대회 운영진은 UCPC를 같이 나간 riroan, aru0504와 함께, ICPC 멤버인 delena0702랑 다같이 진행하여 총 4명으로 구성됐다. riroan이 주로 주최 및 운영에 신경써주었고, 교수님 컨택도 적극적으로 해주었다. 대회 자체가 소모임 주최로 운영돼서 학교의..

이분매칭 (Bipartite Matching) Maximum Flow를 구하는 방법에는 Dinic Algorithm이 존재한다. 그런데, 모든 간선의 flow가 1이고, 이분 그래프 형태로만 존재한다면 bipartite Matching을 시도할 수 있다. (예를 들어 남녀가 미팅을 하며 각자가 원하는 짝을 1명씩 선택할 때, 최대 수로 성사시킬 수 있는 경우의 수는 이분 매칭으로 구할 수 있다.) 참고로 먼 옛적에는 Blossom Algorithm (1961)으로 최대 이분매칭 수를 O(EV^2)에 구했었다. 최악의 경우 O(V^4)까지 나올 수 있었던 셈. 원리가 궁금하다면 소멤 글을 참고해보자. https://www.secmem.org/blog/2020/04/18/Blossom/ 이분매칭의 시간복잡도..

그룹원 한분께서 요청해주신 문제를 해결하면서 degree sequence 라는 개념을 알게 됐다. Warming Up 요청해주셨던 문제는 아래와 같다. 한 번 풀어보도록 하자. (degree sequence 개념을 몰라도 해결이 가능하다.) https://www.acmicpc.net/problem/23578 23578번: 비 오는 날 피에스고등학교의 교장 이환이는 학교를 매우 사랑한다. 그래서 이환이는 매일 점심시간에 학교의 모든 건물을 돌아다닌다. 비가 오는 어느 날, 이환이는 학교 곳곳을 돌아다니고 싶었지만 비 www.acmicpc.net 불만을 최소화하기 위해서는 최소한의 다리로 건물을 연결해야 하며, 따라서 mst를 금방 떠올릴 수 있다. 그러나, 단순 mst 문제는 아니고, 차수에 따라 답이 달..

프로그래머스 월간 코드 챌린지 3번 문제를 풀지 못해 tree + dfs 연습을 좀 더 빡세게 해야겠다 싶어서 선정한 문제들 중 하나이다. 역시나...플레티넘 난이도 답게 굉장히 어려웠다. www.acmicpc.net/problem/20188 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net KOI 2020 2차대회 초등부 3번, 중등부 2번 문제이기도 한데, 이거 보면서 진짜 요즘 초등학생, 중학생들은... 정말 대단하다는 생각도 들고, 똑똑한 친구들은 다르구나 생각이 많이 들었다. 개인적으로 친구들이나 ..

프로그래머스에서 월간 코드 챌린지 시즌2를 4월, 5월에 걸쳐 진행한다길래 접수해서 응시한 챌린지이다! 4월 4문제, 5월 4문제가 출제되고, 두 번의 대회 중 4문제 이상 맞출 경우에 경품 이벤트 응모가 가능하대서 한번 재미삼아 응시한 챌린지이다. 다른 시즌(시즌3 9월) 후기는 아래 포스팅에서~ https://kth990303.tistory.com/m/132 [210909] 프로그래머스 월간 코드 챌린지 시즌3 9월 후기 프로그래머스에선 1년에 두번 꼴로 코드 챌린지가 개최된다. 이번 챌린지는 평일에 실시되긴 하지만, 다행히 개인정비시간 때 실시되기 때문에 응시를 할 수 있었다. https://programmers.co.kr/competitio kth990303.tistory.com 5월 후기는 아래..

1차대회 후기는 여기서 볼 수 있습니다. kth990303.tistory.com/18 [210320] SCOFE 스코페 2021 1차대회 후기 오늘 경험 삼아 실제 첫 코딩 대회를 치러봤다. 문제를 포스팅해도 될지 모르겠어서, 대회가 끝난 후 내가 작성한 코드만 포스팅해보고, 스코페 1차 후기 느낀 점 및 개인적인 난이도를 기록해보 kth990303.tistory.com 오늘 14시부터 18시까지 2차대회가 진행됐다. 14:00 ~ 14:08까지 캠 설정 및 화면녹화 설정이 되지 않아 계속 튕기는 오류가 발생했었고, 다행히 빠르게 해결됐다. 문제 수가 1차보다 적은 4문제인데, 시간은 똑같아서 이번에 진짜 어려울 것이라 예상하고 각오하고 시험을 응시해보았다. 1차는 시간을 남기고 올솔할 정도로 매우 쉽게..

오늘 경험 삼아 실제 첫 코딩 대회를 치러봤다. 문제를 포스팅해도 될지 모르겠어서, 대회가 끝난 후 내가 작성한 코드만 포스팅해보고, 스코페 1차 후기 느낀 점 및 개인적인 난이도를 기록해보려고 한다. 대회 도중 14:30 ~ 15:30 총 한 시간 가량, 제출에 실패했다는 문구가 계속 떴다. 문의팀에서도 16시경, 해결방안을 아예 모두에게 공지했으며, 나만 문제가 발생한 게 아닌, 응시자 모두에게 문제가 발생한 것으로 보아 서버가 터진 듯하다. 5번 문제 '시선 이동' 문제는 정답 처리를 받은 이후, 다시 메모리를 조금 아끼려고 수정 후 재제출했는데, 설마 제출 시각이 늦어져서 오히려 더 불리하게 작용되는 것은 아닐지 불안불안... 하다. 대회 자체가 크게 어렵지 않기도 했지만, 어쨌든 첫 대회였으므로..