목록공부/알고리즘 (26)
pizzaroot
혼자서 진행했다. b [내일 내용 추가]
오랜만에 Div. 4를 쳐보기로 했다. A 문제 읽고 푸는 시간보다 로딩시간이 더 길었다. /** * author: pizzaroot * created: 2024-03-28 23:45:00 **/ #include #define inf 0x3f3f3f3f #define linf 0x3f3f3f3f3f3f3f3f #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define pb push_back using namespace std; typedef long long ll; typedef vector vi; typedef pair pi; int main() { ios::sync_with_stdio(0); cin.tie..
\(\displaystyle i\)번째 공장에서 제공한 캔디 개수를 \(\displaystyle a_{i}\)라고 하자. 관찰 1: 추가해야하는 캔디 개수의 최솟값을 \(\displaystyle x\)라고 하면, \(\displaystyle x+\sum\limits _{i=1}^{n} a_{i}\)는 \(\displaystyle k\)의 배수가 되어야 한다. 관찰 2: \(\displaystyle a_{1} \geq a_{2} \geq a_{3} \geq \ \cdots \ \geq a_{n}\)이 되도록 재배치 해도 구하려는 값 \(\displaystyle x\)의 값은 변하지 않는다. 관찰 3: \(\displaystyle a_{k+1} ,\ a_{k+2} ,\cdots ,\ a_{n}\) 중에서 서..
26등이라는 성과를 냈다. 여러가지 생각이 들었다. 문제가 쉬웠나? 만약 문제가 쉬웠다면 다른 팀들도 많이 풀었을 것이다. 잘하는 팀들이 많이 빠졌나? 잘 모르겠다 실력이 늘었나? 는것은 맞지만 이렇게 까지 등수가 오른것은 이상하다. 운이 좋았나? 푼 문제중에서 어렵게 느껴진 문제는 없었다. 누군가가 설계한 몰래카메라에 당한 것인가? 그럴지도 모른다. 어쨌든 CDGK를 매우 빠르게 내가 풀어서 다른 문제에 할당할 시간이 많았던 것 같다. I를 풀었고 J는 아쉽게 못풀었다. 흠.. J가 세제곱에 돈다는 소문이 있는데 벡터로 짜서 그런지 TLE가 났다.
정렬이란 무엇인가? 정렬은 집합 속 모든 원소들을 순서대로 나열하는 것이다. 정렬은 꼭 수를 정렬할 때만 쓰이는 것은 아니다. 영어 단어들은 알파벳 사전순으로 정렬할 수 있고 한국어 단어들은 가나다순으로 정렬할 수 있다. 정렬 알고리즘은 여러가지가 있다. 프로그래밍을 처음 입문하면서 배우는 버블 정렬, 선택 정렬, 삽입 정렬과 퀵 정렬, 합병 정렬, 힙 정렬 등 매우 많이 존재한다. 하지만 오늘은 이런 정렬 알고리즘에 대해 소개하지는 않을 것이다. 간단하게 언급만 하자면 정렬할 원소의 개수가 \(n\)일 때, 버블/선택/삽입 정렬은 \(O(n^2)\)의 시간복잡도를, 합병/힙 정렬은 \(O(n\log n)\)의 시간복잡도를 가진다. 퀵 정렬은 좀 더 생각해봐야 될 점이 있기 떄문에 여기서는 언급하지 않으..
PS에서 시간복잡도는 매우 중요하다. 시간복잡도는 보통 Big O notation으로 나타낸다. 그래서 시간복잡도가 무엇인가? PS에서 시간복잡도는 문제를 해결하는 데에 걸리는 시간을 입력 크기를 나타내는 변수(들)로 나타낸 함수이다. 하지만 우리가 관심을 가지는 것은 최악의 경우이다. Big O notation의 formal한 정의를 설명하자면 만약 모든 실수 \(x>x_0\)에 대하여 \(f(x)\leq cg(x)\)를 만족하는 실수 \(x_0\)와 양의 실수 \(c\)가 존재한다면, \(f(x)\in O(g(x))\)로 표현한다. 정확하게는 \(O(g(x))\)는 함수들의 집합이지만 다음과 같이 많이 나타낸다. \[f(x)=O(g(x))\] 다른 표기법도 존재하지만 Big O notation을 거의..
먼저 \(N\)이 \(10\,000\)까지 들어오는 것을 보아서 각 선풍기마다 시간 간격만큼씩 더해가며 시뮬레이션 하는 풀이는 통과하기 힘들것이라는 짐작이 벌써 든다. 각 선풍기 마다 \(O(1)\)만에 가격을 구하는 풀이도 존재할 것 같지만, 일단은 쉽게 구현한다는 생각이 들어서 이분탐색을 떠올리게 된다. 대충 구상을 했으니 이제 코드를 짜기 시작한다. 라고 생각하고 코드를 짜다보니 시간이 이미 주어지므로 이분탐색이 전혀 필요 없다는 사실을 깨닫게 된다. 그렇다면 총 몇번을 추가 결제 해야 하는가를 구할 때 \(\displaystyle\left\lfloor\frac{Q}{K}\right\rfloor\)번인지 \(\displaystyle\left\lceil\frac{Q}{K}\right\rceil\)번인..
D번: 중요한 #include #define INF 0x7fffffff #define SIZE 100001 using namespace std; int seg[SIZE > 1; i > 0; i >>= 1) seg[i][id] = min(seg[i >= 1) { if (l & 1) ret = min(ret, seg[l++][id]); if (~r & 1) ret = min(ret, seg[r--][id]); } return ret; } int pos(int val, int right) { right += SIZE; while (seg[right][0] > val) right = (right - 1) >> 1; while (right k; int v, w; ci..
\(O(n^2)\) #include #include #include int main() { int n, ans = 0; scanf("%d", &n); int *arr = (int *)malloc(n * sizeof(int)); assert(arr != NULL); for (int i = 0; i < n; i++) scanf("%d", arr + i); for (int i = 0; i < n; i++) { int good = 1; for (int j = 0; j < i; j++) { if (arr[j] == arr[i]) good = 0; } ans += good; } printf("%d\n", ans); return 0; } \(O(n\log n)\) #include #include #include vo..