gubshig

https://justicehui.github.io/teach/gubshig/ 안녕하세요. 김준호입니다. 알고리즘 / 코딩테스트 과외 합니다.프로필소속선린인터넷고등학교 제117기 소프트웨어과 (2022/03/02 ~ 2025/02/07)한양대학교 25학번 산업공학과 (2025/02/25 ~ ) 온라인 저지 프로필https://www.acmicpc.net/user/gubshig - 1009 solvedhttps://solved.ac/profile/gubshig - Diamond II 2574https://codeforces.com/profile/cerise_bouquet - Rating (max. expert, 1726)https://atcoder.jp/users/revue - Rating (max. 16..

이 문제는 서브테스크를 긁고 최적화를 할 방법을 모르겠어서 풀이를 봤다. 풀이가 신기하고 좋은 문제라고 생각해서 풀이를 올려본다. https://www.acmicpc.net/problem/25402 25402번: 트리와 쿼리 첫 번째 줄부터 $Q$개의 줄에 걸쳐, 각 질의에 대한 답을 출력한다. 이 중 $i$ ($1 ≤ i ≤ Q$)번째 줄에는 $i$번째 질의에서 주어진 $S$에 대하여, $S$의 연결 강도를 출력한다. www.acmicpc.net 이 문제를 요악하자면 트리를 S라는 집합의 정점들로만 한정지었을때, 생기는 각 컴포넌트들의 연결 되어있는 노드의 개수를 구하면 된다. 연결 개수는 컴포넌트의 노드 개수를 n이라 했을때, nC2가 된다. 나이브하게 매 쿼리마다 dfs를 돌리며 컴포넌트의 개수를 ..

최근에 1차 대회 문제 몇개를 풀었는데, 문제 퀄리티가 좋다고 생각해서 풀이를 정리해볼까 한다. https://www.acmicpc.net/problem/25379 25379번: 피하자 음이 아닌 정수로 이루어진 길이 N의 배열 A = [A1, A2, · · · , AN]가 있다. 배열 A에서 인접한 두 수를 교환하는 시행을 원하는 만큼 할 수 있다. 이 때, 홀수와 짝수가 인접한 경우가 최대 1번 등장 www.acmicpc.net 처음 봤을땐 구현을 어떻게 해야하나 막막했는데, 차분히 생각해보니 구현이 어려운 문제는 아니었다. 결국 홀수와 짝수를 한쪽으로 밀어야하는데, 홀수를 밀든 짝수를 밀든 결국 횟수는 같다. mod 2를 해주고 왼쪽으로 밀어보고, 오른쪽으로도 밀어본 다음 최솟값을 출력하면 된다. ..