본문 바로가기

알고리즘 관련/BOJ

BOJ)6549 히스토그램에서 가장 큰 직사각형 문제: icpc.me/6549 히스토그램에서 가장 큰 직사각형을 구하는 문제이다. 세그먼트 트리를 이용한 분할 정복을 이용하여 풀 수 있는데 i,j까지의 구간의 직사각형 넓이는 i,j까지의 높이가 최솟값인 부분에 의하여 결정된다. 따라서 우리는 높이가 최솟값인 부분을 기준으로 양쪽을 분할 정복해 나갈 것이다. 이를 계산하기 위하여 높이가 최솟값인 지점을 세그먼트 트리에 저장을 해줘야 한다. 전체에서 넓이를 구하여 높이가 최솟값인 지점을 기준으로 양쪽의 넓이를 다시 구해주면서 최종적으로 높이의 최댓값을 구해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#.. 더보기
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.. 더보기

티스토리툴바