정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 문제 N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다. 총 K개의 도시 쌍이 주어진다. 이때, 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B www.acmicpc.net 1. 풀이 N이 10만, 쿼리 개수가 10만이라 한 쿼리당 log N이 걸려야 한다. [PS/LCA] - [BOJ] ..

0. 문제 주소 https://www.acmicpc.net/problem/1626 1626번: 두 번째로 작은 스패닝 트리 첫째 줄에 그래프의 정점 수 V(1 ≤ V ≤ 50,000)와 에지 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 에지로 연결된 두 정점과 그 에지의 가중치가 주어진다. 음수 가중치는 없으며, 답은 int 범위를 넘지 않는다. 정점 번호는 1보다 크거나 같고, V보다 작거나 같은 자연수이다. www.acmicpc.net 1. 풀이 *** 첫 다이아 문제 *** 기본 아이디어는 다음과 같다. 0. 크루스칼 알고리즘을 이용해 MST를 만든다. 기존 그래프와 별도로 만들어줄 것이고, 사용하지 않은 간선들은 notused_PQ(min heap)에 따로 ..

0. 문제 주소 https://www.acmicpc.net/problem/2463 2463번: 비용 첫 번째 줄에 정점의 수 N (1

0. 문제 주소 https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. 이때에는 한 정수만 주어지며, B는 꺼낼 사탕의 순위를 의미한다. 이 경우 사탕상자에서 한 개의 사탕이 꺼내지게 된다. 또, A가 2인 경우는 사탕을 넣는 경우이다. 이때에는 두 정수가 주어지는데, B는 넣을 사탕의 맛을 나타내는 정수이고 www.acmicpc.net 1. 풀이 세그트리를 이용해서 맛의 좋고 나쁨을 나타내는 1부터 100만까지의 수에 대해서, 구간 합을 저장하는 세그트리..

0. 문제 주소 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 1. 풀이 인덱스 트리를 이용하여 풀어보려고도 했는데,,, 재귀로 하면 TLE가 난다. 비재귀 세그 트리를 써야 한다는데 나중에 알아봐야겠다. 도저히 모르겠어서 찾아본 결과 deque을 이용한 O(N) 풀이를 찾았다. 슬라이딩 윈도우 기법을 사용하되, 가지고 갈 필요가 없는 원소들은 바로바로 빼 줄 것이다. 0. pair를 이용하여 각 원소에 순서를..

0. 문제 주소 https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 문제 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다. 매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막 www.acmicpc.net 1. 풀이 알고리즘 분류가 "이분 탐색"이라고 되어 있는 것을 보고 처음에 생각난 풀이는 다음과 같다. 0. 집들과..

0. 문제 주소 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다. www.acmicpc.net 1. 풀이 먼저 A와 B 배열에 대해, 가능한 모든 부배열의 합을 구해 놓는다. 우리가 원하는 상황은, A의 부배열 합 + B의 부배열 합 = T가 되는 상황이다. A의 부배열 ..

0. 문제 주소 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시한 것이다. 각 정수는 1 이상 1,000,000,000 이하이다. 단, 참가한 선수들의 평소 실력은 모두 다르다. www.acmicpc.net 1. 풀이 inversion 개수를 구하는 문제. 강사님이 merge sort를 구현하면서 inversion을 구할 수 있다고 하셨고, 이해도 갔지만 구현이 어려울 것 같았다. 그래서 ICPC를 준비하며 봤던 내용으로 인덱스 트리 / 펜윅 트리를 이..

0. 문제 주소 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 1. 풀이 투 포인터 문제. 왼쪽과 오른쪽 포인터들을 각각 어느 조건에서 움직여야 하는지, 종결 조건은 무엇인지 순서가 항상 헷갈렸다. 생각해볼 점은 다음과 같다. 0. 왼쪽 포인터를 L, 오른쪽 포인터를 R이라 하자. 1. 주어진 배열의 수들은 모두 자연수이다. 2. 1.의 이유로 R을 오른쪽으로 옮기면, L과 R이 나타내는 구간합은 무조건 커진다. 3..

0. 문제 주소 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 1. 풀이 풀이 검색해보고 신세계였던 문제. 'level 별로 보는 BFS'라는데 이 말만 들으면 헷갈리니까 예시를 들어보자. 우선 문제에선 K번 바꾸는 동안의 최댓값이 아니라, 정확히 K번을 바꾼 후의 최댓값을 묻고 있다. A라는 숫자에서 i번째 swap을 통해 B를 얻었다고 하자. 앞으로 K-i번의 swap을 더 해야 한다. 앞으로 해야 할 K-i번의 swap의 모든 결과값들 중에, B가 나오면 안 될까? 그렇지 않다. 예를 들어, sample c..