💚1933 스카이라인 N개의 직사각형 건물이 있을 때 스카이라인을 구하는 문제 스카이라인을 차례대로 left x, h, right x 우선순위에 대한 오름차순으로 정렬한다. 이래야만 추후 점들을 대체하는 작업이 순조롭게 이루어진다. 이 문제의 핵심은 두 개의 스카이라인이 교차할 때 높이를 어떻게 결정할 것인가이다. 정답은 교차 시 더 높은 h값을 선택해야 한다.(max 사용) 그리고 추가적으로 동일한 x일 때, 동일한 h일 때에 대한 경우도 고려해야 한다. 가장 어려웠던 점이 대체 후에 동일한 경우까지 따져야한다는 점이 어려웠다. #include #include #include #include using namespace std; using Result = vector; struct Building { ..

💚 1780 종이의 개수 solve(x, y, n) (x, y)부터 가로로 n개, 세로로 n개의 종이 개수를 확인하는 함수 m = n / 3이라고 했을 때 부분 문제로 나눠보면 0: solve(x, y, m) 1: solve(x, y + m, m) 2: solve(x, y + 2 * m, m) 3: sovle(x + m, y, m) ... cnt[x] = x - 1의 개수 x는 -1, 0, 1이 가능하기 때문 #include using namespace std; int a[3000][3000]; int cnt[3] = {0, }; // n * n 종이 내의 색이 모두 동일한지 확인 bool same(int x, int y, int n) { for(int i = x;i < x + n;i++) { for(i..

💚 1201 NMK - 가장 긴 증가하는 부분 수열의 문제는 대부분 다이나믹 프로그래밍이나 그리디의 형식으로 문제를 푼다. - 적어도 M개의 정수는 증가 수열에 포함되어야 하고 - 적어도 K개의 정수는 감소 수열에 포함되어야 한다. - 두 수열은 최대 정수 1개를 공유할 수 있기 때문에 - N >= M + k + 1이어야 한다. - 또 N은 MK를 넘을 수 없다. - N = MK + 1인 경우에 길이가 M + 1인 증가 수열이나 길이가 K + 1인 감소 수열을 반드시 만들 수 있따. - 비둘기집 원리로 증명할 수 있음 - Erdos-Szekeres Theorem 증가하는 수열을 뒤집으면 반드시 감소하는 수열이 된다. ex) 3478 ➡️ 8743 M + K - 1 n >> m >> k; vector a(..

💚 1541 잃어버린 괄호 - 식에 괄호를 적절히 쳐서 식의 값을 최소로 만드는 문제 - -가 나오면 항상 뒤의 +(더하기) 식을 모두 묶으면 가장 큰 값을 뺀다. - 어려운 부분: +와 숫자를 분리하는 부분 #include #include using namespace std; int main() { string s; cin >> s; vector num; vector sign; bool minus = false; int cur = 0; // 모든 숫자는 항상 양수이기 때문 sign.push_back(1); // 문자열에서 숫자와 부호 분리 for(auto c : s) { if(c == '+' || c == '-') { // +면 1, -면 -1 if(c == '+') { sign.push_back(1)..

다익스트라를 연습한 뒤에는 이전에 풀었던 최소 스패닝 트리 알고리즘을 복습하였다. https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 모든 섬을 최소한의 비용으로 연결한다는 점에서 MST(최소 스패닝 트리)에 관한 문제라는 점을 간파해야 한다. 최소 스패닝 트리의 경우 크루스칼 알고리즘이 편해서 적용했던 것 같다. 가중치가 적은 간선부터 정렬한 뒤, 사이클이 생기지 않는다면 그리디하게 간선을 가져오면 된다. 여기서는 벡터를 쓴 후 정렬했는데, 우선순위 큐를 써도 괜찮다. 그리고 사이클을 검사하는 것은 Union..

문제 https://www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net #include #include using namespace std; string p, s; vector pi((1e6) + 1); void make_pi(string p) { // i는 접두사, j는 접미사 인덱스 // pi 배열은 접두사와 접미사가 일치하는 최대 길이 long long i = 0, j = 1; long long p_len = p.length(); pi[0] = 0; while(j < p_len) {..