대회 링크: https://www.acmicpc.net/contest/view/1556문제 링크: https://www.acmicpc.net/category/detail/4574 1. 개괄2025년 9월 27일에 진행된 "2025 Centroid Cup" Open Contest에 출전했습니다. 결과는 8솔브 726분으로 마무리했습니다.여러모로 재미있는 문제들이 많이 있었습니다. 문제 스타일이 다소 특이한 편이다 보니 더 그런 게 아닐까 싶기도 하네요.2. 대회 시작 ~ 33분A에서 AC를 받는 데 단 1분이면 충분했습니다. 보자마자 숫자를 조립하고 있었는데 생각보다는 어렵게 설계되지 않았던 듯 합니다.B도 사칙연산 문제여서 그랬는지, 대회 시작 5분 만에 AC를 띄우고 바로 넘겼습니다. 사실 B부터 N까..

대회 링크: https://www.acmicpc.net/contest/view/1564문제 링크: https://www.acmicpc.net/category/11321. 개괄2025년 9월 13일에 진행된 "2025 서울대학교 프로그래밍 경시대회"(SNUPC) Open Contest에 참가했습니다. 결과는 6솔브 507분으로 마무리했습니다.대회 공지를 통해 추정하건대 이번 Open은 Division 1과 Division 2의 문제들을 합한 뒤 섞어서 낸 거 같은데, 그러다 보니 문제 배치나 이런 부분에서 조금 재미있는 장면들이 연출되었던 것 같습니다. 2. 대회 시작 ~ 58분 (58분 ~ 83분)처음에는 A, B, C, D를 모두 깠는데, 그 이유는 Division 1의 경우 "처음 네 문제는 출제진이..

대회 링크: https://www.acmicpc.net/contest/view/1543문제 링크: https://www.acmicpc.net/category/11251. 개괄2025년 8월 21일에 진행된 "나는코더다 2025 반년대회" Open Contest에 참가했습니다.이전에 실제 대회는 몇 번 치루어 본 적이 있는데, Open Contest는 또 처음이더군요. 결과는 3솔브 350점 349분으로 마무리했습니다.사실 한동안 대회를 안 치르다가 너무 오랜만에 치르는 대회라 그런지, 아니면 이런 식의 올 서브태스크 대회가 안 익숙해서 그런지, 그것도 아니면 Open이 처음이라 그런지 몰라도여러 가지 면에서 익숙하지 않은 모습을 보였습니다.여기에 대한 이야기는 잠시 후에 하는 걸로 하죠. 2. 15분 ~..

대회 링크: https://www.acmicpc.net/contest/view/1437문제 링크: https://www.acmicpc.net/category/10781. 개괄2025년 1월 11일에 진행된 "2024 경인지역 대학 연합 프로그래밍 대회"(shake! 2024)에 경희대학교 대표 자격으로 출전했습니다.사실 2023년에 shake! 2023 경희대학교 대표 선발전에서 좋지 못한 결과를 받았기에 한 해가 지난 뒤에는 각성하여 문제를 풀었고, 결국 2024년에는 경희대학교 대표로 참가할 수 있었습니다. 결과는 #31 2솔브 174분으로 마무리했습니다.결과가 그리 좋지는 않은데, 대회를 처음 참가할 때는 이게 처음으로 출전하는 대회인 데다가 당시에는 PS를 본격적으로 판 지 얼마 안 된 시점이어서..

대회 링크: https://www.acmicpc.net/contest/view/1558문제 링크: https://www.acmicpc.net/category/detail/45491. 개괄2025년 9월 6일에 진행된 "LGCPC 2025 예선" Open Contest에 참가했습니다. 결과는 2솔브 200점 85분으로 마무리했습니다.딱히 뭐 진행 과정을 통틀어 할 말이 많은 대회는 아니긴 합니다만 그래도 진행 과정은 적어 두고자 합니다. 2. 대회 시작 ~ 85분A를 보자마자 이게 대체 뭘까 하는 생각이 들었습니다. 진지하게 약 5분 동안 아무 생각도 안 났던 것 같습니다. 그러다, 문득 생성 함수가 생각나서 문제를 재조립해 보니 그 아이디어가 맞음을 확인했습니다.그러고도 문제 풀이가 생각나지 않다가 DP..

대회 링크: https://www.acmicpc.net/contest/view/1539문제 링크: https://www.acmicpc.net/category/detail/4537 1. 개괄2025년 8월 30일에 진행된 '신촌지역 대학교 프로그래밍 동아리 연합 여름 대회'(SUAPC 2025 Summer) Open Contest에 참가했습니다.특이하게도 보통 본대회와 Open이 같이 진행되는 걸로 알고 있는데 본대회보다 Open이 1주 정도 늦더라고요.근데 최근에 치루어지는 대회들이 대게는 그렇게 진행되는 거 같아서... 뭐 딱히 상관은 없는 것 같긴 합니다. 결과는 6솔브 1120분으로 마무리했습니다. 슼보가 얼어붙은 시간 동안 2문제를 풀어서 상당 부분 유의미한 순위 향상이 있었는데막판 스퍼트를 이렇..

때는 2024년 11월 9일. 사실 이때까지는 경희대학교에 PS 공식 대회가 없었고, PS를 파는 사람들끼리의 커뮤니티도 잘 형성되어 있지 않았습니다.대신에 나름 PS 좀 친다, 하는 사람들은 그나마 경희대학교가 참가 가능한 '경인지역 대학 연합 프로그래밍 경시대회'(이하 shake!)에 참가하여 얼굴을 비치는 정도였죠.심지어, 경희대학교의 shake! 대표 선발 과정도 한양대 ERICA의 0-1 프로그래밍 경시대회를 상호 합의 하에 빌려와서 치르곤 했습니다. (적어도 2023, 2024에는 그랬었던 걸로 기억합니다. 이전에는 제가 대학생이 아니었기에...) 다시 돌아와서, 저 날짜에는 2024 shake!의 경희대학교 대표 선발전이 진행되었습니다.그리고 어이없게도 당시 별로 준비가 되어 있지 않았음에도..

1. 개괄"가장 작은" 스패닝 트리?스패닝 트리가 무엇인지에 대해서는, 일전에 DFS 스패닝 트리에 대해 다루면서 이미 언급한 바 있습니다. 그렇다면, 그중에서 "최소"의 무언가를 가지는 스패닝 트리는 대체 무엇을 최소로 가진다는 걸까요?생각해 보면, 노드의 개수나 간선의 개수는 이 척도가 절대로 될 수 없습니다. 애초에 모든 스패닝 트리의 노드의 개수와 간선의 개수는 동일해야 합니다. 그렇다면, 다른 수치가 최소라는 것이겠죠.최소 스패닝 트리(Mininum Spanning Tree)는 가중치 그래프에서 사용되는 개념이며, 가중치 그래프의 스패닝 트리들 중 간선 가중치의 합이 가장 작은 트리를 의미합니다. 즉, 가장 저렴한 스패닝 트리를 의미한다고 생각하면 됩니다.최소 스패닝 트리를 찾는 두 가지 방법최..

1. 개괄문자 그대로최단 경로 문제(Shortest Path Problem)은 문자 그대로, 주어진 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 알고리즘을 의미합니다.그래프 탐색과 함께, 그래프의 응용 문제 가운데 가장 많이 활용되는 알고리즘입니다. 특히 가중치가 없는 그래프의 경우 BFS를 활용하면 충분히 최단 경로를 구할 수 있지만, 만약 그래프에 가중치가 존재한다면 BFS를 대동한다고 해도 그래프의 최단 경로를 구할 수 없습니다. 그래서, 가중치가 있는 그래프를 다룰 때는 최단 경로 탐색 프로그램이 많이 활용됩니다. (물론 가중치가 없는 그래프에 대해서도 최단 경로를 활용할 수 있습니다.)이제 최단 경로에 대한 이야기를 시작해 봅시다. 그전에, 알아두어야 할 개념들과 몇 가지..

1. 개괄상호 배타적 집합이란?학교에서의 생활을 떠올려 봅시다. 물론 대학생이 되고 나서는 학급의 개념이 없다 보니 조금 까먹었을 감이 없잖아 있지만, 그래도 초등학교, 중학교, 고등학교 때는 여러 개의 학급으로 한 학년이 나누어지고, 여러분은 그 학급 중에서 하나에 속해 있었을 것입니다. 아니면 말고…모쪼록, 여러분들에게 한 가지 질문을 드리겠습니다. 1년 생활에서, 두 개 이상의 학급에 속한 적이 있나요? 또는 그런 사례를 본 적이 있나요? 아마 없었을 겁니다.집합론에서는, 이처럼 전체집합을 여러 개의 부분집합으로 나누었을 때, 어떤 부분집합을 골라도 그들의 교집합이 공집합인 경우를 상호 배타적 집합, 또는 분리 집합(Disjoint Set)이라고 합니다.분리 집합을 자료 구조로 나타내기위에서 언급한..