블로그 언저리인 무언가

문제 : 20041 Escaping 20041번: Escaping 첫 번째 줄에는 경찰의 수 N이 주어진다. 단, 1 ≤ N ≤ 500,000이다. 그 다음 N 개의 줄에는 각 경찰의 초기 위치의 좌표 (xi, yi)가 공백을 사이에 두고 주어진다. 다음 줄에는 도둑의 초기 위치의 좌 www.acmicpc.net 도둑의 좌표가 주어지고 경찰의 좌표가 주어졌을 때 도둑이 영원히 도망칠 수 있는지 확인하는 문제이다. 기본적인 아이디어로는 도둑이 도망치는게 가능하다고 할때 굳이 지그재그로 갈 필요없이 위, 아래, 오른쪽, 왼쪽 중에서 한방향을 정해 쭉 달리면 된다는것을 알수 있고 이를 이용해 위, 아래, 오른쪽, 왼쪽 모두에 경찰이 존재할때만 도망치는것이 불가능함을 알수있다. 여기에서 현재 경찰이 있는 점이 ..

문제 : 3321 가장 큰 직사각형 3321번: 가장 큰 직사각형 열의 순서를 적절히 바꿔, 2열, 4열, 5열이 서로 붙어있게 놓는다면, 크기가 21인 직사각형을 얻을 수 있다. (2행~8행 * 2,4,5열) www.acmicpc.net 기본적으로 1로 채워진 가장 큰 정사각형을 찾는 문제이지만 열의 순서를 바꿀 수 있으므로 결국 각 행에 대해서 열의 높이를 정렬하여 누적합을 이용하면 행의 길이를 1씩 늘려가면서 최대 넓이를 구할 수 있다. 이를 구현하게 되면 총 행의 개수 N번, 각 행을 정렬하는데 걸리는 시간이 퀵 정렬 사용 시 MlogM이므로 시간 복잡도가 O(NMlogM)이 되는데 시간제한이 0.6초이기 때문에 이를 O(NM)으로 줄여야 한다. 나 같은 경우에는 deque를 사용해 정렬 시간을 ..

문제 : 2573 빙산 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 빙산의 위치와 높이가 주어질 때, 2개 이상으로 나누어지는 시간을 구해 출력하는 문제이다. 매해 빙산이 녹는 높이를 카운트해서 줄여주면서 BFS를 통해 빙산의 개수를 구해 0이나 2 이상이 되는 순간을 출력하면 된다. Code #include #define ll long long using namespace std; typedef pair pll; ll N, M, ans, arr[305][305], cnt[305][305], visi..

La Piscine 일정은 어떻게 진행되나요? 라 피신은 총 4주에 걸쳐서 진행되며 원래는 전일제로 진행해 모든 날에 출석했지만 저 같은 경우에는 코로나로 인해서 격일제(1그룹 월-수-토/2그룹 화-목-일)로 진행했습니다. 기본적인 일정은 아래와 같습니다. 월~목요일 : 개인과제 금요일 : 시험 토~일요일 : 팀 프로젝트 시험과 팀 프로젝트 같은 경우는 할 수 있는 기한이 정해져 있고 개인과제는 자율적으로 공부해서 해결해나가면 됩니다. 마지막 주 금요일에는 final exam을 치게 되고 이를 마지막으로 La Piscine 과정이 종료됩니다. 주로 어떤것들을 배우나요? 해결해야 하는 과제가 주어지면 그에 맞는 것을 공부하고 해결하시면 됩니다. 기본적으로는 리눅스, C언어에 대해 전반적으로 배우며 중요하게..

문제 : 1916 최소비용 구하기 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 도시의 개수와 도시들 간에 운행하는 버스의 비용이 주어졌을 때 최소비용으로 이동하는 금액을 출력하는 문제이다. 다익스트라 알고리즘을 이용해서 해결하면 최소비용을 쉽게 구할 수 있다. Code #include #define ll long long #define INF 1e9+7 using namespace std; struct ABC{ ll idx, dst; ABC() {} ABC(ll idx, ..

문제 : 9375 패션왕 신혜빈 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 의상의 수와 이름이 주어졌을 때 맨몸이 아니도록 옷들의 조합의 수를 찾아서 출력하는 문제이다. 같은 의상의 종류를 센 후 +1씩 해서 곱해 전체 조합의 수를 세고 하나도 입지 않는 것은 불가능하므로 1을 빼서 출력하면 된다. Code #include #define ll long long using namespace std; ll N; ma..

문제 : 1080 행렬 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 행렬 A와 행렬 B가 주어질 때 3*3 크기의 모든 원소를 뒤집어서 행렬 A를 행렬 B로 만드는 최소 횟수를 구하는 문제이다. 그리디 하게 앞 원소부터 모두 뒤집어 본 후 불가능한 경우를 체크해주면 된다. Code #include #define ll long long using namespace std; ll N, M, ans; string x[55], y[55]; int main(){ ios::sync_with_stdio(0); cin.tie(0); ..