일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 이베이트미국
- 백준
- gallian
- self balancing binary search tree
- 이베이트
- ccw
- Ebate Korea
- persistent segment tree
- indexed tree
- 대한항공
- round 420
- subgroup
- 7469
- 알고리즘
- Codeforces
- Algorithm
- BOJ
- algebra
- 마일리지
- 아시아나
- 대수학
- finite group
- k번째 수
- round 424
- 이베이트코리아
- Algebraic Geometry
- Ebate USA
- 구간쿼리
- acmicpc
- persistent indexed tree
- Today
- Total
목록알고리즘 (14)
https://www.acmicpc.net/problem/14432 (머그컵 E번) 이 문제의 핵심은 문제 마지막문단에 있는 "(단, 임의의 마을 A에서 B까지 무조건 한 가지 경로가 존재한다.)" 이다. 다시말해 이 마을들간의 관계는 트리형태이고, 따라서 한점을잡아 root로 간주하여 DFS로 탐색하면서 값을 갱신해주면 정답을 도출해 낼 수 있다.
https://www.acmicpc.net/problem/14437 (머그컵 A번) DP로 접근하면 D[현재위치][남은횟수]를 가지고 풀이하면 O(N*S)에 풀 수 있을 것 처럼 보인다. 다른 방법으로는 중복조합과 포함배재의 원리를 이용해서 풀 수도 있다. 중복조합을 이용하면 속도도 빠를 뿐 아니라, combination 값을 구할 때 DP가 아닌 fermat little thm이용해서 풀면 배열을 잡을 필요가 없어진다. 즉 메모리에 구애받지 않는 풀이가 된다. 시간복잡도는 O(N+logP).
https://www.acmicpc.net/problem/1153 다양한 풀이방법이 있겠지만, Goldbach's Conjecture라 불리는 가설?을 이용하여 풀었다. 항상 소수관련문제는 정수론과 뗄레야 뗄 수 없는것 같기도하고.. Goldbach's Conjecture는 아직 증명이 되지않은 정수론 미해결문제중 하나로 "2보다 큰 모든 짝수는 두개의 소수의 합으로 나타낼 수 있다"는 가설이다. 물론 아직 반례를 찾지못해 미해결문제로 남아있다. 즉, 앵간히 큰 짝수(우리가 문제에서 접할 수 있는 수)까지는 다 성립한다는 뜻. #include int num[1000001] = { 0 };int N;void prime() { for (int i = 2; i*i
https://www.acmicpc.net/problem/1750 naive하게 생각하면 포함-배제의 원리를 생각하기 쉬우나 조금 생각해보면 TLE가 떨어질거라는 확신이 드는 문제이다. DP를 이용해 N개의 원소중 1~i번째 숫자들을 후보로 하여 최대공약수가 j인 갯수를 d[i][j]라고 놓으면 생각보다 쉽게 점화식을 세울 수 있다. #include #define MAX 10000003#define LL long longint num[101];__inline int min(int a, int b) { return a > 1]; while ..