알고리즘 관련 썸네일형 리스트형 BOJ)10868 최소값 문제:icpc.me/10868 N개의 정수가 있을 때 a번째 부터 b번째 수 중에 가장 작은 수를 찾는 문제이다. 문제는 쿼리가 M(10만)개 이므로 O(N)의 시간에 최솟값을 찾으려고 할 경우 총 O(N*M)의 시간이 걸려 TL을 받을 것이다. 따라서 세그먼트 트리를 이용하여 O(logN)의 시간에 최솟값을 탐색해서 O(MlogN)의 시간에 문제를 해결해야 한다. 12345678910111213141516171819202122232425262728293031323334#include #include #define MAX_N 100000#define INF 1900000000using namespace std;int n, m, seg[4 * MAX_N], a, b;int update(int pos, in.. 더보기 BOJ)2357 최소값과 최대값 문제:icpc.me/2357 N(100000)개의 정수 중에서 a번째 수부터 b번째 수까지 중에서 최솟값과 최댓값을 출력하는 문제이다. 문제가 되는건 쿼리의 수가 M(10만)으로 최솟값과 최댓값을 O(N)의 방법으로 선형 탐색을 한다면 총 O(N*M)의 시간이 걸린다는 것이다. 그러므로 우리는 세그먼트 트리를 이용하여 최솟값과 최댓값을 O(log N)의 시간 복잡도에 해결하여 총 O(MlogN)의 시간에 문제를 해결 할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #define MAX_N 100000#define INF 1900000000us.. 더보기 BOJ)2042 구간 합 구하기 문제: icpc.me/2042 값의 갱신이 빈번하게 일어 날 때 구간 합을 구하는 문제이다. 구간에 대한 합은 파셜섬을 이용한다면 O(N)에 해결할 수 있지만 값의 갱신이 빈번하게 일어 난다면 갱신이 일어 날 때 마다 O(N)의 시간이 걸리므로 총 O(N*M)의 시간복잡도를 가지게 될 것이다. 문제에서 N이 100만 M이 만이므로 시간을 초과할 것이다. 따라서 문제를 해결하기 위하여 세그먼트 트리를 이용하여 갱신과 구간 합 출력을 O(logN)에 해결해줘서 O((M+K)logN)의 시간에 문제를 해결 할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637#include #include using namespace std;type.. 더보기 BOJ)1654 랜선 자르기 문제: icpc.me/1654 가지고 있는 랜선들을 동일한 크기로 잘라서 N개를 만드려고 할 때 최대 몇cm씩 잘라야 하는지 구하는 문제이다. 파라메트릭 서치를 통하여 N개만큼 랜선을 만들 수 있는지 여부를 확인해주면서 풀면 되는 문제이다. 1234567891011121314151617181920212223242526#include #include typedef long long ll;using namespace std;ll k, n;ll lo, hi;ll a[10010];int main() { scanf("%lld%lld", &k, &n); for (int i = 0; i 1; ll t = 0; for (int i = 0; i = n) lo = mid + 1; else hi = mid; } printf.. 더보기 BOJ)4627 뛰어라 도마뱀 문제: icpc.me/4627 도마뱀이 맨해튼 거리가 D이하인 거리를 이동 할 수 있을 때 탈출을 하지 못하는 도마뱀의 수를 정하면 된다. 문제를 잘 읽어보면 같은 시간에는 최대 하나의 도마뱀만 기둥에 서 있을 수 있고 기둥에는 최대 도약 횟수가 정해져 있다. 이를 이용하여 그래프를 모델링을 하면 소스->도마뱀들의 처음 위치 각 방-> 맨하탄 거리가 D이내인 방 외각->Destination 으로 모델링을 할 수 있다. 이 때 우리는 최대 도약 횟수를 생각해야 하므로 정점들을 분할하여 정점을 분할하는 간선의 가중치를 최대 도약횟수로 주고 최대유량을 구해주면 원하는 답을 얻을 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383.. 더보기 BOJ)13701 중복 제거 문제:icpc.me/13701 중복되서 입력 된 수를 제거하고 출력하면 되는 문제이다. 하지만 메모리 제한이 8MB밖에 안되기 때문에 수를 그냥 입력받아서 저장하기에는 무리가 있다. 그래서 비트마스킹을 이용하여 사용한 수에 해당하는 비트를 켜주고 수를 받았을 때 비트가 켜져 있는지 확인하고 출력하면 된다. 123456789101112131415161718#include #include using namespace std;int c[1 + (1 더보기 BOJ)1647 도시 분할 계획 문제: icpc.me/1647 최소 스패닝 트리를 구해주면 된다. 주의할 점은 하나인 마을을 두개로 나누고 싶다고 하고 있기 때문에 N-2개의 간선만 연결해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include using namespace std;vector vt;int n, m, a, b, c, r;int par[100010];int find(int x) { if (par[x] == x)return x; return par[x] = find(par[x]);}void merge(int x, int y,int z) { x = find(x); y = find(y); if (x ==.. 더보기 BOJ)4948 베르트랑 공준 문제: icpc.me/4948 n~2n 사이의 소수의 개수를 출력하면 되는 문제이다. 에라토스테네스의 체로 소수들을 구해 준 뒤 파셜섬의 차를 구해주면 된다. 12345678910111213141516171819202122232425#include #include using namespace std;bool p[270000];int s[270000];int n;int main() { p[0] = p[1] = true; for (int i = 2; i 더보기 BOJ)12842 튀김 소보루 문제: icpc.me/12842 m명의 사람이 튀김 소보루를 먹는 시간이 주어졌을 때 n번째 튀김 소보루를 누가 먹었는지 출력하는 문제이다. n과 m이 10만이고 개인이 소보루를 먹는 시간 t가 최대 1000이여서 시뮬레이션을 돌려도 시간내에 AC 받을 수 있었다. 123456789101112131415161718192021222324#include #include #include using namespace std;int n, s, m, x, r, t;int a[100010];int main() { scanf("%d%d%d", &n, &s, &m); for (int i = 1; i 더보기 BOJ)13505 두수 XOR 문제: icpc.me/13505 N개의 수 중에서 두 수를 정해 XOR한 값이 가장 크게 하는 문제이다. 두수가 XOR을 하여 가장 큰 수가 되려면 서로 다른 비트가 가장 많아야 할 것이다. 트라이를 이용하여 모든 수를 비트 순서대로 저장 한 후 이후 모든 수에 대해서 자기와 다른 비트를 따라가도록 하면 된다. 이때 가장 큰 수가 되야 하므로 비트는 높은 자리 수 부터 검사한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include #include #incl.. 더보기 이전 1 ··· 29 30 31 32 33 34 다음