랄뚜기의 코딩일기

https://www.acmicpc.net/problem/24545 24545번: Y 첫째 줄에 트리의 정점 개수를 의미하는 정수 $N$이 주어진다. ($2 \leq N \leq 100\,000$) 둘째 줄부터 $N-1$개 줄에 걸쳐 트리를 이루는 간선의 정보를 나타내는 두 정수 $u$, $v$가 주어진다. 이는 $u$번 정 www.acmicpc.net 문제 Y-트리는 아래 조건을 만족하는 트리이다. 4개 이상의 정점과 인접한 정점은 없다. 인접한 정점의 개수가 3개인 정점은 정확히 하나만 존재한다. 인접한 정점이 하나뿐인 정점은 정확히 세 개 존재한다. Y-트리의 크기는 해당 Y-트리를 이루는 정점의 개수와 같다. 1, 2, … N까지의 번호가 하나씩 매겨진 정점 N개로 이루어진 트리가 주어진다. 주어..

https://www.acmicpc.net/problem/22988 22988번: 재활용 캠페인 첫 번째 용기와 두 번째 용기를 가져가서 용량이 $\left(0+1+\frac{13}{2}\right)$㎖ $=$ $7.5$㎖ 남은 용기를, 세 번째 용기와 네 번째 용기를 가져가서 용량이 $\left(2+3+\frac{13}{2}\right)$㎖ $=$ $11.5$㎖ 남은 용 www.acmicpc.net 문제 고등학생 때였다. 친구의 손에 이끌려 처음으로 가게 된 화장품 가게는 문을 열자마자 은은한 향기가 코끝을 스치는 곳이었다. 친구를 따라가기에 급급했던 한별이의 발걸음은 이제 누가 말하지 않아도 무언가에 빨려 들어간 듯이 앞을 향했다. 파운데이션을 바르고, 블러셔를 두드리고. 거울을 본 한별이는 처음 보..

더보기 https://www.acmicpc.net/problem/24453 24453번: 디버깅 첫 줄에는 자동으로 작성된 코드 줄의 수 $N$과 오류가 있는 줄의 개수 $M$이 주어진다. $(1 \le N \le 2 \times 10^7$, $1 \le M \le \min(N,\ 5\times 10^5))$ 두 번째 줄에는 코드에서 오류가 있는 줄의 번호 $M$개가 www.acmicpc.net 문제 인규는 자동으로 코드를 생성해주는 프로그램을 이용해 코드를 작성하곤 한다. 하지만, AI는 완벽하지 않기 때문에 자동으로 생성된 코드에 오류가 있을 수도 있다. 따라서 인규는 코드를 자동으로 생성한 뒤, 코드를 한 줄씩 읽으면서 오류를 찾는 과정을 거친다. 인규가 쓰는 코드 에디터는 매우 똑똑해서 작성된 코..

https://www.acmicpc.net/problem/19580 19580번: 마스크가 필요해 첫 번째 줄에는 A도시의 시민 수인 N과 A도시의 상점 수인 M이 주어진다. (1 ≤ N, M ≤ 500,000) 두 번째 줄부터 N + 1번째 줄까지는 A도시의 각 시민이 마스크에 소비할 수 있는 돈의 범위인 Li, Ri가 www.acmicpc.net 문제 코로나19가 발생하고 나서 마스크의 필요성이 증가하기 시작했다. 마스크가 없으면 생활을 하는데 어려움이 있기 때문에 마스크를 항상 구비하고 있어야 한다. 마스크의 수요가 증가함에 따라 일정했던 마스크의 가격이 상점마다 달라지게 되었다. 마스크의 가격이 제각각이기 때문에 A도시의 시민들이 전부 마스크를 갖기가 어려워지기 시작했다. A도시의 공무원인 당신은..

https://www.acmicpc.net/problem/19582 19582번: 200년간 폐관수련했더니 PS 최강자가 된 건에 대하여 2220년에도 “2220 신촌지역 대학생 프로그래밍 대회 동아리 연합 수시 대회”가 성공적으로 개최된다. SUAPC은 이제 모든 학생이 즐길 수 있도록 다양한 난이도의 대회가 1년에 수시로 열리며, www.acmicpc.net 문제 2220년에도 “2220 신촌지역 대학생 프로그래밍 대회 동아리 연합 수시 대회”가 성공적으로 개최된다. SUAPC은 이제 모든 학생이 즐길 수 있도록 다양한 난이도의 대회가 1년에 수시로 열리며, 상금 규모는 억대가 되었다. 이런 미래를 예측한 연두는 냉동인간이 되어 폐관수련을 통해 알고리즘만 공부하였으며, 이제 모든 대회에서 반드시 1등..

https://www.acmicpc.net/problem/20947 20947번: 습격받은 도시 $N$개의 줄에 도시의 정보를 출력한다. 각 줄은 $N$개의 문자를 포함하며 $i$번째 줄 $j$번째 문자는 도시의 세로 $i$번째 가로 $j$번째 칸에 대한 정보이다. 빈칸일 경우 ., 건물일 경우 O, 건물 잔해 www.acmicpc.net 문제 극악무도한 테러리스트 주현이가 도시를 습격했다. 습격받은 도시는 세로 N$N$칸, 가로 N$N$칸으로 이뤄진 격자 모양이며, 각 칸은 빈칸이거나 건물이 존재한다. 주현이는 자신이 만든 수제 폭탄을 건물이 없는 곳에 설치한다. 폭탄은 터질 때 상하좌우 각 방향에 대해 충격파가 퍼져나가는데, 충격파가 닿은 건물은 파괴되어 건물 잔해가 된다. 충격파는 건물 또는 건물 ..

https://www.acmicpc.net/problem/20943 20943번: 카카오톡 카카오톡은 주식회사 카카오가 2010년 3월 18일 서비스를 시작한 글로벌 모바일 인스턴트 메신저로, 2020년 기준 $4\,000$만 명의 사용자가 등록돼 있고 시장 점유율이 $96$%로 사실상 거의 모든 국민 www.acmicpc.net 문제 카카오톡은 주식회사 카카오가 2010년 3월 18일 서비스를 시작한 글로벌 모바일 인스턴트 메신저로, 2020년 기준 4000$4\,000$만 명의 사용자가 등록돼 있고 시장 점유율이 96$96$%로 사실상 거의 모든 국민이 사용할 정도로 점유율이 매우 높다. 카카오의 지원하에 국렬이는 카카오톡의 특이한 오픈톡방에 대한 실험을 진행했다. 그에 대한 실험 내용은 다음과 같다..

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은..

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 문제 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 이..