하바나바나나

https://www.acmicpc.net/problem/25402 25402번: 트리와 쿼리 첫 번째 줄부터 $Q$개의 줄에 걸쳐, 각 질의에 대한 답을 출력한다. 이 중 $i$ ($1 ≤ i ≤ Q$)번째 줄에는 $i$번째 질의에서 주어진 $S$에 대하여, $S$의 연결 강도를 출력한다. www.acmicpc.net 매 쿼리마다 $S$가 주어졌을 때 $S$ 안의 정점들 주 연결되어 있는 정점 쌍의 개수를 찾는 문제입니다. 문제를 정리하면, $S$가 주어질 때 $S$안의 정점들이 몇 개의 컴포넌트로 나누어지는지, 그리고 각 컴포넌트에는 몇 개의 정점이 있는지 찾는 문제라고도 할 수 있습니다. 컴포넌트 내의 정점들은 모두 서로 연결되어 있다고 할 수 있으므로 매 컴포넌트마다 컴포넌트 안의 정점에서 두 개..

https://hanbyeol-moscow.havana.moe/ 한별~모스크바~ hanbyeol-moscow.havana.moe https://github.com/havana723/hanbyeol-moscow GitHub - havana723/hanbyeol-moscow: 한별이를 2021 월드 파이널 in 모스크바에 보내자! 한별이를 2021 월드 파이널 in 모스크바에 보내자! Contribute to havana723/hanbyeol-moscow development by creating an account on GitHub. github.com shiftpsh 님의 허락을 받아 한별이를 2021 ICPC 월드 파이널 in 모스크바에 보내는 미니 웹 비주얼노벨을 개발했습니다. 아직 개발 중으로, 현..

https://www.acmicpc.net/problem/23090 23090번: 난민 문제의 답을 공백으로 구분하여 \(N\)줄에 걸쳐 출력한다. \(i\)번째 줄에, \(1\)번째 부터 \(i\)번째까지 이주해온 난민들이 정수시설까지 이동하는 거리의 합이 최소가 되도록 하는 정수시설의 \(y\ www.acmicpc.net 블로그에 올렸던 쌀 창고 + 중앙값 구하기인 문제입니다. https://havana723.tistory.com/16 BOJ 5821 쌀 창고 https://www.acmicpc.net/problem/5821 5821번: 쌀 창고 쌀 창고 이 경우에는 창고의 위치에 대한 여러 개의 최적 위치가 있다: 10 이상 14 이하의 어느 정수 위치에든지 쌀 창고를 둘 수 있다. 위의 그림은 최..

https://www.acmicpc.net/problem/24456 24456번: 초콜릿 훔쳐 먹기 첫 번째 줄에는 세 정수 $N,\ M,\ K$가 공백으로 구분되어 입력된다. ($1 \le N,\ M \le 10\,000$, $0 \le K \le N \times M$) www.acmicpc.net 1부터 $NM$까지의 모든 수에 대해 해당 수를 두 수의 곱으로 표현하는 모든 경우를 구하는 문제라고도 생각할 수 있습니다. 단순히 모든 약수를 확인한다면 $\mathcal{O}({(NM)}^2)$의 시간이 걸릴 것이라고 생각했고 커팅하는데 시간이 걸렸습니다. 커팅은 소인수분해를 하듯이 하면 됩니다. $x$의 약수를 확인할 때 $\sqrt{x}$까지의 수로 나누어지는지만 확인하면 두 수의 곱으로 표현하는 모..

JUNCTION ASIA 2022 참가 후기 (1) JUNCTION ASIA 2022 참가 후기 (1) 어쩌다보니 정션 아시아 2022 해커톤에 참여하게 되었습니다. 사실 너무 귀찮아서 블로그 글을 쓰지 않으려고 했는데, 기억이 사라지기 전에 조금이나마 남겨보고자 글을 적게 되었습니다. 끝까 blog.havana.moe 그렇게 해커톤 전까지의 이야기가 모두 끝나고 8월 19일이 다가왔습니다. 조금 일찍 부산역에 도착하신 shiftpsh 님을 만나 조금 놀다가 5시 반 쯤 벡스코에 도착했습니다. 행사장으로 센텀 신세계에서 출발했는데, 막연히 벡스코면 벡스코 역으로 가야겠지 하고 한 정거장 거리를 지하철을 탔습니다. 근데 벡스코 역과 실제 행사장은 거리가 꽤 됐고... 걷다가 센텀 신세계가 보였습니다. 무얼..

https://www.acmicpc.net/problem/24914 24914번: Split the SSHS 첫째 줄에 세 정수 N, M, 그리고 Q가 공백으로 구분되어 주어진다. 둘째 줄부터 N째 줄까지 N - 1 개의 줄에 세 정수 ui, vi, wi가 공백으로 구분되어 주어지며, 색 wi로 칠해진 i 번 길이 ui 번 건물과 vi www.acmicpc.net 어떻게 맨 처음에 조각의 수를 셀 수 있을까 고민하다가 조각의 개수가 (각 정점에 연결되어 있는 색의 종류 - 1)을 모두 더한 다음 1을 더해준 값이라는 것을 발견했습니다. 트리 몇 개 그려보고 맞는 거 같아서 짜서 맞았습니다. 증명은 다음과 같습니다. 이 문제는 트리 하나가 $k$개의 트리(조각)으로 나누어질 때, $k$를 구하는 문제가 됩..

어쩌다보니 정션 아시아 2022 해커톤에 참여하게 되었습니다. 사실 너무 귀찮아서 블로그 글을 쓰지 않으려고 했는데, 기억이 사라지기 전에 조금이나마 남겨보고자 글을 적게 되었습니다. 끝까지 쓸 수 있겠죠? 발단 UCPC도 그렇고 모든 일들이 어쩌다가 일어나는 거 같은데, 제 인생의 모든 일들이 그렇게 일어나는 거 같습니다. 정션도 크게 다르지 않았습니다. UCPC도 끝나고 방학을 맞아 한없이 뒹굴뒹굴거리던 저는 JUNCTION ASIA 2022가 열린다는 글을 보게 됩니다. 어떤 글이었는지는 잘 기억이 나지 않지만, 2박 3일 동안 밥도 주고 숙소도 주는 최고의 기회라는 코멘트가 같이 적혀있었습니다. 밥과 호텔에 낚인 저는 생에 첫 해커톤을 나가기로 결정합니다. 해커톤을 나가고 싶다는 생각은 오래 전부..

https://www.acmicpc.net/problem/2647 2647번: 검은점과 하얀점 연결 2n개의 점이 x축의 좌표 1,2,...2n에 놓여 있다. 그 중 n개는 검은 점이고, n개는 하얀 점이다. 하나의 검은 점과 하나의 하얀 점을 연결하여 한 쌍을 만들면, 모두 n개의 쌍이 만들어진다. 한 쌍의 점 www.acmicpc.net 처음에 그리디로 한 네 번쯤 삽질하다가 다 예제에 막히고 포기했습니다. 태그 까고 나서 DP인걸 알고도 하루 종일 고민했는데 안 풀려서 cologne 님께 풀이를 들었습니다. $dp[l][r]$을 $l$부터 $r$까지의 구간에서 매칭했을 때의 최솟값으로 두면 됩니다. 역추적도 필요한데, 메모이제이션을 할 때 $l$이 어느 점과 이어졌는지를 기록하면 역추적을 할 수 있..

https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 교육적인 슬라이딩 윈도우 문제입니다. 원형으로 돌면서 $k$짜리 길이의 초밥들을 관리해주면 됩니다. 초밥이 추가될 때마다 visited 값을 늘려주고 초밥이 제거될 때마다 visited 값을 줄여주면 쉽게 구현할 수 있습니다. 쿠폰의 경우, 현재 가지고 있는 초밥 중 $c$번 초밥이 있는지 확인해주면 됩니다. 아래는 코드입니다. #include #def..

https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 백트래킹을 사용해 풀 수 있는 문제입니다. n-queen 문제와 비슷하게 비숍을 하나씩 놓는다고 생각하고, 하나의 비숍이 놓일 때 그 대각선에 있는 칸들은 전부 갈 수 없다고 표시해주면 됩니다. 다만 나이브하게 백트래킹을 돌리면 시간초과를 받게 되고, 체스칸의 흰색 영역과 검정색 영역을 나눠서 (비숍은 한 색으로만 이동할 수 있으므로) 풀면 풀 수 있습니다. 이 아이디어를 생각하는 것이 어려웠습니다. 아래..