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)\)). ..

Modular Arithmetic 정수 \(a, b, m\)에 대하여, \(m \ | \ (a-b)\) 일때, \(a\)는 법 \(m\)에 대하여 \(b\)와 합동이다(\(a\) is congruent to \(b\) modulo \(m\)). 이때, 기호로 \(a\equiv b\pmod m\)이라고 쓴다. 여기서 \(m\)을 합동의 법(modular)이라고 한다. 수학적인 정의는 이렇고, 간단하게 말하면 '\(a\)와 \(b\)를 \(m\)으로 나누었을 때, 그 둘의 나머지가 같다'라고 생각하면 된다. 모듈라 연산에서의 덧셈, 뺄셈, 곱셈은 다음과 같은 성질들이 성립한다. \((a+b) \pmod m \equiv ((a \pmod m) + (b \pmod m)) \pmod m\) \((a-b) \pmo..

n개의 원소들이 저장된 배열에서 특정 원소 x를 찾는다고 할때, 여러 가지 탐색(Search) 방법이 존재한다. Linear Search 배열의 첫 번째 원소부터 차례대로 하나씩 x와 같은지 비교하는 방식으로 가장 간단한다. 시간복잡도는 \(O(n)\) 이다. 구현int search(int arr[], int n, int x) { for (int i = 0; i < n; i++) { if (arr[i] == x) return i; } return -1; } Binary Search 일단 배열의 원소들을 정렬한다. 그 후 반복적으로 배열을 반으로 나누어 x가 위치한 곳을 좁혀나가는 방식이다. 상당히 유용하게 사용되는 탐색 방법이다. 정렬하는데 \(O(nlog_2n)\)의 시간이 걸리지만, 탐색하는데에는 \..

문제링크 - 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..

Counting Sort 계수 정렬(Counting Sort)은 총 \(n\)개의 원소가 1에서 \(k\)의 범위에 있을 때, 선형 시간복잡도 \(O(n+k)\)를 가지는 빠른 정렬 방법이다. \(O(nlog_2n)\)의 시간복잡도를 가지는 Merge Sort, Heap Sort, Quick-Sort 같은 정렬법보다도 빠르게 동작한다. 단, 원소의 범위가 1에서 \(n^2\)이라면 \(O(n^2)\)의 시간복잡도를 가지게 되는 제약이 있다. 구현#include using namespace std; void countSort(char arr[], int range) { char newArr[strlen(arr)]; int cnt[range + 1] = { 0 }; for (int i = 0; arr[i];..