너와 나의 스토리

문제: https://www.acmicpc.net/problem/9250 Ries님의 블로그와 위키백과를 통해 공부하였습니다. insert(key + 1); } }; step 2. fail 함수 만들기 (BFS) 규칙 1. 루트에서 거리가 1인 것들(즉, root->next[i])의 fail은 root로 초기화한다. 규칙 2. 루트로부터 거리가 2 이상이면, 직전 노드의 fail을 따라가면서 자신과 같은 값을 만나면 그 노드를 fail로 설정 queue q; root->fail = root; q.push(root); while (!q.empty()) { trie* cur = q.front(); q.pop(); for (int i = 0; i next..

문제: https://www.acmicpc.net/problem/11279 소스코드: STL priority_queue 사용 ...더보기 #include #include #include #include using namespace std; int n; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; priority_queue pq; while (n--) { int x; cin >> x; if (x==0) { if (pq.empty()) { cout x; if (x==0) { pop(); } else push(x); } return 0; }

문제: https://www.acmicpc.net/problem/2252 문제 풀이: 위상정렬 알고리즘을 이용한다. 예제가 다음과 같을 때, 1->3 (indegree[3]++) 2->3 (indegree[3]++) 으로 보고 indegree가 0인 것들을 큐에 넣는다. 앞에서부터 하나씩 빼면서 그 노드가 가리키는 노드의 indegree를 감소시켜 0이 되면 큐에 넣어준다. 소스 코드: stl 사용 ...더보기 #include #include #include using namespace std; int n, m,indegree[32002]; vector v; queue q; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ..

문제: https://www.acmicpc.net/problem/4195 문제 풀이: map과 union find를 이용하여 쉽게 풀 수 있는 문제이다. 소스 코드: stl unordered_map사용 ...더보기 #include #include #include #include #include #include #include using namespace std; int p[200001],cnt[200001]; string name1,name2; int find(int n) { if (p[n]==n) return n; return p[n] = find(p[n]); } int merge(int a, int b) { a = find(a); b = find(b); if (a != b) { p[b] = a; cn..

문제: https://www.acmicpc.net/problem/5052 동적 할당 방식 #include using namespace std; const int TrieNode = 10; struct Trie { Trie *next[TrieNode]; bool finish; bool nextChild; Trie() { fill(next, next + TrieNode, nullptr); finish = nextChild = false; } ~Trie() { for (int i = 0; i < TrieNode; i++) { if (next[i]) delete next[i]; } } bool insert(const char* key) { if (*key == '\0') { finish = true; retur..

문제: https://www.acmicpc.net/problem/3878 소스 코드: #include #include #include #include #include #include #include using namespace std; typedef long double ll; typedef pair P; int startpoint, tc, n, m; ll ax, ay; vector black, white; vector v1,v2; bool cmp(const P a, const P b) { if ((ax - b.first) * (ay - a.second) == (ax - a.first) * (ay - b.second)) { if (a.second == b.second) return a.first < b...

푸아송 분포 확률론에서 단위 시간 안에 어떤 사건이 몇 번 발생할 것인지를 표현하는 이산 확률 분포 이산 확률 분포 이산 확률 변수가 가지는 확률 분포를 의미한다. 여기에서 확률변수가 이산 확률 변수라는 말은 확률 변수가 가질 수 있는 값의 개수가 가산 개 있다는 의미이다. 확률 질량 함수를 통하여 표현가능 이산 확률 분포 예 이산균등분포 푸아송 분포 베르누이 분포 기하 분포 초기하 분포 이항 분포 음의 이항 분포 다항 분포 연속 확률 분포 확률 밀도 함수를 이용해 분포를 표현할 수 있는 경우를 의미한다. 연속 확률 분포를 가지는 확률변수는 연속 확률 변수라고 부른다. 연속 확률 분포 예 정규 분포 연속균등분포 카이제곱 분포 감마 분포 이항 분포 연속된 n번의 독립적 시행에서 각 시행이 확률 p를 가질 ..

누랑 1박 2일로 강릉을 다녀왔다. 첫째 날 강릉 도착하자마자 초당 순두부 마을 가서 밥부터 먹음 줄이 너어어무 길어서 줄 제일 짧은 식당 찾아다니다가 그나마 '농촌 순두부' 집이 짧아서 거기 감 순두부 전골이라는걸 처음 먹어봤는데 맛있었당 가운데 하얀 음식은 아마 비지로 만든 음식인 것 같은데 처음 먹어보는 맛이고 JMT 밥 먹고 경포해변 근처에 숙소를 잡아서 물놀이를 하러 갔다. 와 파도가 너무 세서 무서워서 못 들어가고 파도 끝부분 맞으면서 첨벙첨벙 하면서 놀았다. 그리고 중앙시장(중앙성남전통시장)가서 저녁을 먹었다. 강릉은 감자지 하다가 감자전 먹고싶어서 감자바우라는 식당이 나와서 감 감자 옹심 처음 먹어봤는데신기한 맛이였다. 감자전을 기름에 부친게 아니라 국에 넣은 맛? 감자전 쫀득쫀득 이거 먹..