본문 바로가기

분류 전체보기

BOJ)4195 친구 네트워크 문제 : icpc.me/4195 친구 관계가 생길 때 마다 가입한 두사람의 친구 네트워크에 몇명이 있는지 구하는 문제이다. 문제의 답은 union_find를 통하여 쉽게 구해줄 수 있지만 string으로 들어오는 입력 때문에 좌표 압축이나 map을 이용한 테크닉이 필요하다. -좌표압축 이용123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include #include #include #include #include #include using namespace std;int par[200010];int t, n;int num[200010];vect.. 더보기
BOJ)9345 디지털 비디오 디스크(DVDs) 문제:icpc.me/9345 번호 순서대로 있던 DVD를 쿼리에 따라서 바꿔줄 때 a번부터 b번까지 DVD를 가져왔을 때 a~b번까지 DVD가 모두 있나 확인하는 문제이다. a~b번까지 DVD가 모두 있나 확인할 수 있는 방법은 a~b까지의 최댓값과 최솟값을 구해주어 a와 b인지 확인해주는 작업을 해주면 된다. 이는 세그먼트 트리를 이용하여 구해줄 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include #include #define MAX_N 100000#define INF 987654321using namespace std;.. 더보기
BOJ)1321 군인 문제:icpc.me/1321 군인들이 번호 순서대로 각 부대에 배치되어 있을 때 i번째 군인이 몇번 부대에 배치되어 있는지 확인하는 문제이다. 이 때 부대별로 군인들의 수가 감원이 일어 날 경우 모든 군사들이 재배치를 받게 되므로 세그먼트 트리를 이용하여 갱신과 쿼리를 O(logN)시간에 해결 해 줘야 한다. 쿼리를 처리하는 방법은 노드에 구간 합을 저장하고 있을 때 내가 부대를 찾아야하는 군번을 가지고 왼쪽 자식 노드와 비교를 하여 왼쪽 자식 노드가 더 큰 값을 가지고 있을 경우 내가 찾고자 하는 부대는 왼쪽에 있는 것이므로 왼쪽 자식을 재귀 호출하고, 아닐 경우 오른쪽 자식을 재귀 호출 하는데 이 때 우리는 왼쪽 자식 수만큼을 제외하고 봐야 하므로 찾아야하는 군번에 왼쪽 자식의 수만큼 빼준 값으로 재.. 더보기
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 ==.. 더보기