랄뚜기의 코딩일기

더보기 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에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 이..

https://www.acmicpc.net/problem/24461 24461번: 그래프의 줄기 그래프에서 사이클이란, 한 정점에서 같은 정점까지, 반복되는 간선이 없으며, 길이가 $0$이 아닌 경로이다. 사이클이 존재하지 않는 그래프가 주어진다. 우리는 이 그래프의 정점 중에서 연결된 www.acmicpc.net 문제 그래프에서 사이클이란, 한 정점에서 같은 정점까지, 반복되는 간선이 없으며, 길이가 0$0$이 아닌 경로이다. 사이클이 존재하지 않는 그래프가 주어진다. 우리는 이 그래프의 정점 중에서 연결된 간선이 하나인 정점을 가장자리 정점이라고 정의하자. 이 그래프의 가장자리 정점을 동시에 없애는 행동을 반복하면서, 그래프가 일직선의 모양이 되면 남아있는 정점의 집합을 그래프의 줄기라고 정의하자. ..

https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 문제 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료..