robustflame의 블로그

문제 보기출제자 해설문제 요약\(n\)개의 item 목록이 주어지는데, 각 item은 다음과 같은 값들을 가진다.\(t_i\): \(i\)번째 item을 구하는데 소요되는 시간\(d_i\): \(i\)번째 item의 가치가 유효한 시간, 즉 가치를 지켜내기 위해 구해내야만 하는 시간\(p_i\): \(i\)번째 item의 가치item들을 어떤 순서로 어떤 것들을 구하는지에 따라 얻을 수 있는 가치의 총합이 달라진다. 이때 가능한 가장 큰 가치의 합을 구하는 문제다.문제 풀이가장 단순한 방법은 가능한 모든 경우를 따져보는 것이다. 모든 경우를 다 따져볼 경우 각각의 item을 구할지 말지를 정해야 하고, 해당 item들을 어떤 순서로 구해야 하는지 따져봐야 하므로 시간복잡도는 \(O(2^n \times n..

문제링크 - http://codeforces.com/problemset/problem/785/E문제 풀이순열 \(a[ \ ] = \{1, 2, ..., n\} \ (1 \le n \le 200000)\) 에 대하여 특정 위치 \(l_i\) 과 \(r_i\) 의 값을 바꾸는 연산이 \(q \ (1 \le q \le 50000)\) 번 수행될 때, 매 연산 후 순열에 존재하는 역접(inversion)의 수를 세는 문제다. 역접의 수는 크기가 \(a[x] > a[y] \ (x a[r]\) 이면 역접의 수가 1 감소한다. 위의 내용들에서 서로 상쇄되는 것들을 제거하고, 통합하면 아래와 같이 간결하게 역접의 수 변화를 확인할 수 있다. \(a[l] < a[r]\) 이면, \((l 0) { ret += tree[p..

Square Root Decomposition 우리 말로는 평방 분할(Sqrt Decomposition)이라고 불리는 이 기술은 특정 구간에 대한 질문(query)에 빠르게 답하기 위한 최적화 기술(일종의 자료구조)이다. 먼저, 아래와 같은 문제에 대해 고민해보자. 원소의 개수가 \(n\) 개인 배열 arr[]이 있다. 이 배열에 대해서 \(q\) 개의 질문(query)이 하나씩 들어온다. 질문의 내용은 다음 2가지 중 하나이다.특정 구간 [\(l, \ r\)] 의 합을 구하라.특정 위치 \(idx\) 의 값을 \(val\) 로 변경하라. 위와 같은 문제는 단순하게 반복문을 이용하여 \(l\) 부터 \(r\) 까지 순회하면서 값을 더해나가면 구할 수 있다(시간복잡도: \(O(q \times n)\)). ..

문제링크 - http://codeforces.com/contest/777/problem/E문제 분류난이도 - 중태그 - dynamic programming, data structure, segment tree문제 풀이내부 반지름의 길이 \(a_i\), 외부 반지름의 길이 \(b_i\), 그리고 높이 \(h_i\)가 주어진 여러 개의 링들을 최대한 높게 쌓는 문제다. 일단 아래와 같이 2차원 평면으로 보면 (1) \(b_i\)가 증가하는 순으로, (2) \(b_i\)가 증가하는 순으로 정렬해야할 필요성을 느낄 수 있다. 완전 탐색을 할 경우 \(O(2^n)\)으로 문제를 해결할 수 있다. 너무 느리므로 동적계획법을 고민해보면 아래와 같은 점화식을 찾을 수 있다. \(dp[i]\): \(i\)번 링을 맨 밑..

문제링크 - http://codeforces.com/contest/777/problem/D문제 분류난이도 - 중태그 - greedy, strings문제 풀이주어진 문자열들의 접미사들을 최소한으로 없애서 모든 문자열들이 사전순으로 정렬되어 있도록 하는 문제다. 연속된 두 문자열이 사전 순서로 되어야만 하므로, 두 문자열이 순서가 올바르지 않을때 무언가 조치를 취해야 한다. 다음과 같이 두 문자열의 순서가 잘못되었다고 해보자. # a b d ..# a b c .. 접미사를 없애야 하는데, 두 번째 문자열의 접미사를 어떻게 없애더라도 사전상으로 올바르게 할 수 없다. 무조건 첫 번째를 없애야 한다. 연속적인 두 문자열에 대해서 이렇기 때문에 모든 문자열에 대해서 확장해보면 가장 마지막 문자열부터 바로 이전 문..

문제링크 - http://codeforces.com/problemset/problem/777/C문제 분류난이도 - 중태그 - dynamic programming문제 풀이2차원 배열 \(a[n][m] (0 \le n \cdot m \le 100,000)\)이 주어졌을때, 특정 행 구간 \([l, r]\)에 모든 원소가 non-decreasing order인 열이 하나라도 존재하는지 총 \(k (1 \le k \le 100,000)\)개의 구간에 대해 답을 계산해야 하는 문제다. dp[ i ][ j ]를 j 번 열에서 i 번 행 이후로 연속적으로 non-decreasing order가 되는 원소의 개수라고 하면, 다음과 같은 식을 얻을 수 있다. if ( a[ i ][ j ]

문제링크 - https://www.acmicpc.net/problem/1034문제 분류난이도 - 하태그 - 탐색문제 풀이이 문제는 조금 관찰력이 필요한 문제다. 어떤 열의 램프 상태가 서로 다른 두 행은 동시에 켜져있을 수 없다. 즉, 서로 다른 두 행이 동시에 켜져있으려면 최소한 그 열의 램프 상태는 같아야 한다. 모든 열에 대해서 확장하면 어느 두 행이 동시에 켜져있으려면 그 두 행의 램프 상태는 동일해야 한다. 이러한 사실을 깨닫게되면 스위치를 K번 눌러서 어떤 행이 켜질 수 있는지 확인하고, 이와 램프 상태가 동일한 램프들의 수를 세어서 이 문제를 해결할 수 있다. 소스 코드#include #include #include #include using namespace std; typedef long..

문제링크 - https://www.acmicpc.net/problem/5419문제 분류난이도 - 중태그 - 구간 트리문제 풀이각 점에 대해서 자신의 위치보다 \(x\) 값이 크거나 같으면서, \(y\)값은 작거나 같은 지점들을 모두 세면 되는 문제다. 그런데 \(n\)의 값을 보면 알겠지만, 단순하게 모두 다 해보는 \(O(N^2)\) 방식으로는 안된다. 구간 트리를 사용하면 이 정보를 빠르게 셀 수 있다. 먼저 좌표들을 (1) \(x\)값이 감소하는 방향으로, (2) \(y\) 값이 증가하는 방향으로 정렬한다. 그런 다음에 유일한 \(y\) 좌표들을 가지고 구간 트리를 구성한다. 이제 앞서 점들을 정렬한 순서대로 하나씩 자신보다 \(x\) 값이 크거나 같은 점들 중에서 \(y\) 값이 작거나 같은 좌표..

문제링크 - https://www.acmicpc.net/problem/3117문제 분류난이도 - 중태그 - 동적계획법문제 풀이경험이 없으면 풀기 까다로운 문제다. 단순하게 동영상을 순회하면서 풀고자 하면 당연히 시간초과가 발생한다. 동적계획법을 생각해봐도 \(M\)이 10억이라 딱히 감이 오지 않는다. 그런데 다음과 같은 점화식을 세울 수 있으면 문제가 해결된다. dp[i][j] = i 번 동영상에서 \(2^j\) 분 후, 시청할 동영상dp[i][j] = dp[ dp[i][j-1] ][j-1] 위의 점화식을 간단하게 설명하면 a번 동영상에서 2x분 후에 시청할 동영상은 a번 동영상에서 x분 후에 시청할 동영상 b를 구한 뒤, 다시 b번 동영상에서 x분 후에 시청할 동영상 c를 구하면 된다는 것이다. 단순..