프로그래밍 자료정리

문제 링크 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 알고리즘 분류 구현 시뮬레이션 코멘트 문제만 잘 읽고 그대로 구현하면 된다. 먼지들이 한번에 확산된다는 점에 주의해야 한다. 소스코드 더보기 class Cleaner { private: vector mRoom; int mTopCleaner, mBotCleaner; int mRow, mCol; int dx[4] = { 0,1,0,-1 }; int dy[4] = { 1,0,-1,0 }; ..

문제 링크 https://www.acmicpc.net/problem/12854 12854번: 홍준이는 물리를 좋아해 첫째 줄에 정점의 개수를 나타내는 n과 간선의 개수를 나타내는 m이 주어집니다. 둘째 줄에 i번째 정점의 가중치를 나타내는 n개의 정수가 공백을 사이에 두고 주어집니다. 셋째 줄부터 간선의 www.acmicpc.net 알고리즘 분류 그리디 코멘트 풀이를 보고 항상 2개의 꼭짓점만을 포함하는 최적의 유도 부분그래프가 연결그래프 G 안에 존재함을 증명하는 문제임을 깨달았다. 문제를 풀 때 풀이의 증명의 중요성에 대해 깨달았다. 더보기 증명 모든 정점의 가중치가 최대값(1000000), 모든 간선의 가중치가 최소값(1)을 가진다고 할 때, 연결된 정점의 개수가 n이라면 $\lim_{n \to \..

class UnionFind { private: vector mParents; public: UnionFind(int n) { mParents = vector(n); for (int i = 0; i < n; i++) { mParents[i] = i; } } int GetParent(int x) { if (mParents[x] == x) { return x; } return mParents[x] = GetParent(mParents[x]); } void UnionParent(int a, int b) { a = GetParent(a); b = GetParent(b); if (a < b) { mParents[b] = a; } else { mParents[a] = b; } } bool CompareParents..

문제 링크 https://www.acmicpc.net/problem/15704 15704번: 백준 마라톤 대회 첫째 줄에 교차로의 수 N, 도로의 수 M, 예산 K가 주어진다. (2 ≤ N ≤ 100,000, N-1 ≤ M ≤ 100,000, 1 ≤ K ≤ 109) 둘째 줄부터 M개의 줄에는 도로의 정보가 주어진다. 도로의 정보는 네 정수 A, B, C, T (1 ≤ www.acmicpc.net 알고리즘 분류 이분탐색 다익스트라 코멘트 교차로 -> 정점, 양방향 도로 -> 간선으로 바꾸고 읽으면 이해하기 쉽다. "시작 교차로 V1은 항상 1번 교차로, 마지막 교차로 Vk는 항상 N번 교차로"에서 다익스트라, "참가할 수 있는 사람의 수의 최댓값"에서 이분탐색을 유추했다. 소스코드 더보기 typedef l..

C++17에서 추가된 문법으로 자료구조에 저장된 값들을 unpack해서 변수에 자동으로 할당하는 편의 문법이다. int arr[3] = {1,2,3}; auto [a,b,c] = arr; 배열 뿐만 아니라 pair, tuple등의 자료구조에서도 사용할 수 있다. std::map mp; for (auto &[k, v]: mp) { std::cout

문제 링크 https://www.acmicpc.net/problem/19235 19235번: 모노미노도미노 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 알고리즘 분류 - 구현 - 시뮬레이션 코멘트 블럭을 내릴 때 각 칸을 기준으로 내리면 안되고, 처음 놓은 그 블럭의 모양대로 내려야 한다. 또한 행, 열을 제거할 때 하나씩 제거하고 내리기를 반복하면 안되고 한번에 제거해야 한다. 소스코드 #include #include #include #include #include #include using namespace std; #def..