gubshig

한양대학교 알고리즘 동아리인 ALOHA에 들어가게 되었다. 고급반은 매주 셋 하나를 잡고 같이 도는 활동을 한다는 것 같다. 이번 셋은 gggkik의 셋인데, 특이사항으론 셋의 문제를 전부 본인이 출제한 문제로 냈다. -3문제를 가장 먼저 해결한 사람에겐 밥을 사준다는 상품이 걸려있었고, 참을 수 없었다. (A번) DKSH 찾기 https://www.acmicpc.net/problem/29766더보기문자열의 길이도 작고, DKSH도 작기에 나이브한 문자열 비교 알고리즘을 짜면 된다.(B번) 운동회 https://www.acmicpc.net/problem/25425더보기지문이 해석이 어려울 수 있는데, " 준혁이의 지금 가질 수 있는 등수는 (준혁의 팀을 제외한 남아있는 팀의 수 + 1)과 같다." 가 핵..

https://www.acmicpc.net/problem/8193한국어 지문에 사소한 오류가 있는데, 1번 정점과 2번 정점은 항상 연결되어있다는 조건이 빠져있다. 문제를 간단히 요약하면,가중치 없는 무향 그래프 $G = (V, E)$가 주어질 때, 간선을 최대한 많이 추가해야한다. 단 이때 1번 정점과 2번 정점 사이의 최단거리가 5 이상임이 유지되어야 한다. 보통 우리는 자료구조를 다룰 때 간선을 삭제하는 것 보다 추가하는 것이 쉽기에 이를 활용하는 경우가 많다. 그러나 이 문제의 경우엔 완전그래프에서 간선을 최소한으로 삭제하는 문제로 생각해주는 것이 편하다. 문제를 다음과 같이 환원하자. 완전그래프와 지워지면 안되는 간선의 집합이 주어졌을 때, 간선을 최소한으로 삭제하여 1번 정점과 2번 정점의 최..