본문 바로가기

분류 전체보기

BOJ)5419 북서풍 문제: icpc.me/5419 북서풍을 타고 항해할 수 있는 섬의 쌍의 개수를 구하는 문제이다. 여기서 북서풍을 타고 항해할 수 있는 섬이란 어떤 섬 기준으로 x좌표가 해당하는 섬보다 크거나 같고 y좌표가 해당하는 섬보다 작거나 같은 섬들을 말한다. 결국 우리는 각 섬마다 x좌표가 작으면서 y좌표는 큰 섬들의 개수를 구한 뒤 그 합을 출력하면 된다. 우리는 x좌표가 작은 수를 우선적으로 정렬하되 x좌표가 같을 경우 y좌표가 큰 수를 우선적으로 정렬을 할 것이다. 이렇게 정렬을 했을 시에 먼저 등장하는 좌표뒤에 나오는 좌표들 중 북서풍을 타고 항해할 수 있는 섬이 없다는 것은 자명하다. 따라서 우리는 정렬을 해준 뒤 순서대로 봐주면 된다. x좌표 기준으로 정렬을 했으므로 우리는 먼저 등장했던 섬들 중에서 .. 더보기
BOJ)1849 순열 문제: icpc.me/1849 (A[i]=i보다 큰 수들의 개수)일 때 원래 수열을 구하는 프로그램을 작성하면 된다. 작은 수 부터 채워 나간다고 할 때 A[1]이 5 라면 1은 수열의 6번째 수가 될 것이다. 우리는 수열을 세그먼트 트리를 이용하여 구해보자. 먼저 리프에 해당하는 모든 노드를 1로 채워준 후 구간합을 업데이트 시켜준다. 이후 a[i]를 확인 할 때 a[i]+1번째에 해당하는 노드를 찾아준 뒤 수열의 해당하는 자리에 i를 저장해 준다. 이후 노드 i를 0으로 초기화 시켜준다. 이런 방식으로 나보다 큰 수들중에서만 내가 몇번째 위치에 있는지 확인 하여 수열을 채워 나간다. 1234567891011121314151617181920212223242526272829303132333435#incl.. 더보기
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.. 더보기

티스토리툴바