목록공부 (33)
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을 거의..