정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/3948 3948번: 홍준이의 친위대 문제 홍준 왕국의 국왕 홍준이는 자신을 호위하는 N명의 친위대 병사가 있다. 병사들의 키는 모두 다르다. 홍준이는 그들을 일렬로 세울 때, 키 순서대로 세우는 것보다 맨 끝 두 병사를 제외한 � www.acmicpc.net 1. 풀이 처음엔 1차원 dp 배열로 점화식을 세워보려고 했으나 실패했다. 탑다운으로 현재 위치에 서려는 사람 기준 남아있는 사람들 중에 이 사람보다 키가 작은 사람 / 큰 사람의 수와 함께 다음에는 이 사람보다 큰 사람이 와야 하는지 여부를 파라미터로 사용한다. 2. 풀이 코드 * 유의할 점 #include #define ll long long using namespace ..

0. 문제 주소 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 1. 풀이 플로이드 워셜 알고리즘을 이용해서 i번 도시에서 j번 도시로 가는 최단거리가, 중간에 k번 도시를 거쳐서 가는 거리보다 클 경우 불가능, 같을 경우 i번 ~ j번을 직접적으로 잇는 도로는 필요가 없기 때문에 이를 저장해두고 순회가 끝나면 남은 도로들의 가중치만 더해주면 된다. 2. 풀이 코드 * 유의할 점 #include using namespace std; int ..

0. 문제 주소 https://www.acmicpc.net/problem/7469 7469번: K번째 수 문제 현정이는 자료 구조 프로젝트를 하고 있다. 다른 학생들은 프로젝트 주제로 스택, 큐와 같은 기본 자료 구조를 구현하는 주제를 선택했다. 하지만, 현정이는 새로운 자료 구조를 만들었다. www.acmicpc.net 1. 풀이 merge sort tree + binary search 쿼리마다 각 구간에서 어떤 수 보다 작은 수의 개수가 k-1개 인 것 중 가장 큰 수를 이분 탐색으로 찾는다. 2. 풀이 코드 * 유의할 점 #include const int INF = 1e9+7; const int NMAX = 100005; const int MAX = 1 =1;i--){ vector &c = tree..

0. 문제 주소 https://www.acmicpc.net/problem/9345 9345번: 디지털 비디오 디스크(DVDs) 문제 최근 유튜브와 같은 온라인 비디오 스트리밍 서비스 때문에 DVD 대여점들이 자취를 감추고 있다. 이러한 어려운 상황 속에서, DVD 대여점 주인들은 실낱같은 희망을 잡고자 인기있는 N개의 DV www.acmicpc.net 1. 풀이 "선반 A번부터 선반 B번까지 A번 ~ B번 dvd가 순서에 상관없이 모두 꽂혀있는 경우" "선반 A번부터 선반 B번까지 가장 작은 dvd 번호가 A, 가장 큰 dvd 번호가 B인 경우" 2. 풀이 코드 * 유의할 점 #include const int INF = 1e9+7; const int NMAX = 100005; const int MAX =..

0. 문제 주소 https://www.acmicpc.net/problem/3392 3392번: 화성 지도 문제 2051년, 야심차게 발사한 화성탐사선 성화가 탐사한 곳의 화성 지도를 N개 보냈다. 화성탐사선의 성공에 의기양양해진 BaSA(Baekjoon Space Agency)는 야심찬 계획을 발표했다. 화성 전체 지도를 만� www.acmicpc.net 1. 풀이 스위핑 풀이는 쉽게 이해가 갔다. 문제는 지금까지 유효한 y 좌표를, 즉 0번 이상 덮여져 있는 y 좌표가 얼마나 있는지를 알아야 하는데 update도 구간으로 주어져서 처음에는 lazy propagation을 생각했었다. 이 경우 lazy 배열을 이용한 느린 전파 ~ 0보다 큰 좌표의 개수의 합 연산 사이에서 구현이 어려워졌다. 그래서 구글..

0. 문제 주소 https://www.acmicpc.net/problem/1701 1701번: Cubeditor 문제 Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고�� www.acmicpc.net 1. 풀이 KMP 알고리즘에서 사용하는 fail 함수를 이용하는 문제 2번 이상은 2번만 나와도 된다는 얘기고, 접두사와 접미사가 같다는 얘기는 동일한 부분 문자열이 2번 나온다는 것과 같다. 처음엔 가능한 모든 부분 문자열에 대해 fail 배열을 만들어서 최댓값을 찾게 했는데 TLE를 받았다. 당연히 N^3이라 터진다. 생각해보니까 양 ..

0. 문제 주소 https://www.acmicpc.net/problem/11495 11495번: 격자 0 만들기 문제 음수가 아닌 정수들의 격자가 주어진다. 당신은 이 격자에 다음 연산을 행할 수 있다. 1. 격자에서 가로 또는 세로로 인접한 정수 2개를 고른다. 2. 각 정수가 양수일 때 1 감소시킨다. 다음 그림은 총 4개의 연속한 연산을 2*2 격자에 가해서 모든 정수를 0으로 만든 과정을 보여준다. 위 예제에서는 모든 정수를 0으로 만들기 위해 4번의 연산을 행했다. 이보다 적은 횟수의 연산으로는 모든 정수를 0으로 만들 수 없다는 것을 쉽게 알 수 있다. www.acmicpc.net 1. 풀이 flow가 어려운 이유는 모델링이 문제 풀이의 90%를 넘게 차지하는데 그걸 하기가 어렵기 때문인 것..

0. 문제 주소 https://www.acmicpc.net/problem/11281 11281번: 2-SAT - 4 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 양수인 경우에는 각각 \(x_i\), \(x_j\)를 나타내고, 음수인 경우에는 \(\lnot x_{-i}\), \(\lnot x_{-j}\)를 나타낸다. www.acmicpc.net 1. 풀이 2-CNF(Conjunctive Normal Form)의 정의 : OR 연산만으로 연결된 괄호 단위(절, closure)들의 AND 연산만으로 이루어진 ..

0. 문제 주소 https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이다. 이때 방향은 A->B가 된다. www.acmicpc.net 1. 풀이 단절점 알고리즘과 매우 유사. dfs ordering을 하면서, 자신과 자신의 자손들이 갈 수 있는 가장 작은 order가 자신이라면, 그 점 + 그 점의 자손들은 하나의 SCC를 이룬다. 물론 모든 자..

0. 문제 주소 https://www.acmicpc.net/problem/10167 10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x,y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x,y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이익 또는 손해를 나타내는 정수 w(-109 ≤ w ≤ 109)가 주어진다. 금광의 좌표는 모두 서로 다르며 w > 0인 금광은 적어도 하나 존재한다. www.acmicpc.net 1. 풀이 1. 좌표의 범위때문에 좌표 압축을 해주어야 한다. 지금까지는 좌표 압축을 너무 원시적으로 했는데, 좋은 테크닉을 찾아서 주워왔다. x좌표, y좌표를 각각 따로 xco, yco 벡터에 저장해둔 ..