본문 바로가기

분류 전체보기

BOJ)2022 사다리 문제: icpc.me/2022 극혐스러운 수학문제이다. 사실 그렇게 어려운 수식은 아니고 직선의 방정식 두개를 구하여 두 교점의 y좌표인 c를 알고 있으니 이때 구해야하는 밑면 m을 이분 탐색을 통하여 찾아 나가는 문제이다. 밑면m이 클수록 c는 낮아지므로 함수로 구한 값이 c보다 크다면 lo를 mid로 c보다 작다면 hi를 mid로 잡아주면 된다. 사실 이터레이터를 얼마나 돌려야되는지 감이 안와서 제출하면서 조절했는데 너무 많이 돌리면 TLE를 보게되고 너무 적게 돌리면 오차때문에 WA를 보게된다. 123456789101112131415161718192021222324252627#include #include using namespace std;double x, y, c, lo, hi;double fx.. 더보기
BOJ)2252 줄 세우기 문제: icpc.me/2252 N명이 학생이 주어지고 두 학생의 키를 비교한 M개의 정보가 주어질 때 줄을 세운 결과를 출력하는 문제이다. 우리는 두 학생의 우선관계를 방향 그래프를 이용하여 설정해준 뒤 topology를 구해주면 된다. 즉 DFS를 돌리면서 먼저 끝나는 순서대로 스택에 저장해준 뒤 하나씩 뽑으면서 출력해주면 답을 얻을 수 있다. 1234567891011121314151617181920212223242526272829303132333435#include #include #include #include #define MAX_N 32000using namespace std;vector vt;stack st;int n, m, x, y, visited[MAX_N + 1];void dfs(int .. 더보기
BOJ)1561 놀이 공원 문제:icpc.me/1561 M개의 놀이기구를 순서대로 타는데 각각의 놀이기구의 운행시간이 주어질 때 마지막 아이는 몇번째 놀이기구를 타게되는지 출력하는 문제이다. 우리는 파라메트릭 서치를 이용하여 N명의 인원이 놀이기구를 탑승하는데 걸리는 시간 T를 구할 수 있다. T를 구했다면 T-1초동안 놀이기구를 탄 아이 수를 쉽게 구할 수 있고 이를 K라 했을 때 우리는 O(M)만큼 탐색하여 앞으로 O(N-K)번째로 타게 될 놀이기구의 번호를 구하면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include using namespace std;typedef long long ll;ll n, m,.. 더보기
한문제를 풀면 4문제를 해결 가능 히스토그램에서 가장 큰 직사각형 문제는 매우 유명한 문제다. 근데 이 문제 한문제를 풀면 BOJ에서 무려 4문제를 약간의 수정을 통해 AC 받을수 있다. 히스토그램 Maximal Area 무서운 아르바이트 정말 꿀문제인거 같다 더보기
BOJ)1666 최대 증가 직사각형 집합 문제: icpc.me/1666 여러 직사각형이 주어졌을 때 이중 몇개의 직사각형을 골라서 집합을 만들것이다. 이때 집합의 조건은 집합의 임의의 두 원소를 선택했을 때 두 직사각형중 한 직사각형이 다른 한 직사각형보다 오른쪽 위에 있어야한다는 조건이다. 우선 각 원소를 왼쪽 아래 점의 x좌표 기준으로 스위핑하여 문제를 푸려고한다. 우리는 각 원소를 비교해나가며 쿼리를 처리하며 세그먼트 트리에 업데이트 할 것인데 이 때 비교는 왼쪽 아래 점과 하며 업데이트는 오른쪽 윗 점을 할것이다. x좌표 기준으로 정렬을 했기 때문에 우리는 세그먼트 트리에 y좌표의 위치에 업데이트 할 것이다. 이때 좌표압축을 사용해 노드를 줄인다. 하지만 우리는 비교는 왼쪽 아래 점 기준으로 하며 정렬도 왼쪽 아래 점 기준으로 하지만 업.. 더보기
BOJ)3392 화성 지도 문제: icpc.me/3392 지도가 주어졌을 때 전체 지도의 면적을 출력하는 문제이다. X,Y좌표가 최대 3만까지 들어오기 때문에 O(X*Y)완전 탐색으로 문제를 해결하기에는 무리가 있다. 우리는 지도의 세로축들을 쿼리로 관리하여 x좌표 ,y좌표1, y좌표2 그리고 끝나는 변인지 시작하는 변인지 변수로 관리를 해준다. 이제 쿼리들을 X좌표 기준으로 정렬을 해보자. 쿼리를 순서대로 볼건데 시작하는 변인 쿼리는 y1~y2구간을 1씩 증가시켜줄것이고 끝나는 변인 쿼리는 y1~y2구간을 1씩 감소시켜 줄것이다. 쿼리를 세그먼트 트리에 업데이트 해주기 전에 우리는 가장 최근에 처리한 쿼리의 x좌표와 현재 처리중인 x좌표의 차이를 dx라고 할때 현재 확인중인 x좌표까지의 면적을 dx*(업데이트 된 y좌표의 개수).. 더보기
BOJ)2336 굉장한 학생 문제:icpc.me/2336 N명이 학생이 세번의 시험을 치뤘을 때 A라는 학생이 B라는 학생보다 세번의 시험의 성적이 모두 좋다면 A가 B보다 '대단하다'고 한다. 어떤 학생 C가 자신보다 대단한 학생이 없을 경우 C는 '굉장하다'라고 한다. N명의 학생의 3번의 시험에서의 등수가 주어졌을 때 굉장한 학생의 수를 구하는 문제이다. 굉장한 학생을 다시 정의하자면 자기보다 세번의 시험을 전부 다 잘본 학생이 한명도 없는 경우이다. 우리는 굉장한 학생을 구하기 위해 첫번째 시험의 등수 기준으로 정렬을 할 것이다. 그리고 첫번째 시험을 잘 본 순서대로 쿼리를 처리할 것이다. 이러면 먼저 나온 학생이 적어도 그 뒤에 나온 학생들보다 1번째 시험을 잘봤다는 것은 자명한 사실이니 뒤에 나오는 학생들의 2,3번째 시.. 더보기
BOJ)1395 스위치 문제: icpc.me/1395 1~N번까지 스위치가 존재할 때 두가지 쿼리에 따른 일을 한다. 1. S~T까지 스위치를 반전 시키는 것2. S~T까지 켜져있는 스위치의 개수를 출력하는 것 우리는 세그먼트 트리의 구간합을 통하여 켜져있는 스위치의 개수를 쉽게 구할 수 있다. 하지만 1번 쿼리의 경우 구간에 대한 갱신이 일어나기 때문에 우리는 lazy propagation을 사용하여 업데이트를 시켜줘야만 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #define MAX_N 100000using namespace std;int n, m, seg[4 * MAX_N],.. 더보기
BOJ)10999 구간 합 구하기2 문제: icpc.me/10999 구간에 대한 합을 출력하는 문제이다. 그런데 쿼리중에 구간에 대한 갱신 연산을 하는 쿼리가 있다. 우리는 세그먼트 트리를 통해 구간에 대한 갱신과 합쿼리를 빠르게 처리 할 수 있지만 구간에 대한 갱신을 세그먼트 트리로만 하려고 한다면 갱신의 경우 최악의 시간복잡도는 O(NlogN)이 될것이다. 만약 쿼리가 전부 갱신만 들어온다면 시간 복잡도는 O(N(M+K)logN)로 당연히 시간초과를 보게 될 것이다. 그래서 우리는 lazy propagation을 이용하여 구간에 대한 갱신을 조금 더 빠르게 해주는 테크닉을 이용하여 문제를 풀어야만 한다. lazy propagation에 대한 설명은 여기에 친절하게 되어있다. 1234567891011121314151617181920212.. 더보기
BOJ)11505 구간 곱 구하기 문제:icpc.me/11505 구간에 대한 곱을 출력하는 문제이다. 값의 갱신이 빈번하게 일어나기 때문에 세그먼트 트리를 이용해주면 된다. 곱셈의 특성상 구간의 곱을 가지고 있으면 무수히 커질 수 있기 때문에 문제에서 모듈러연산을 요구한다. 이때 단순히 답에만 모듈러연산을 해준다면 노드가 가지고 있는 값이 오버플로우 될 수 있으므로 우리는 노드가 가진 값들을 업데이트 할 때 와 쿼리를 처리할 때도 모듈러연산을 해줘야 한다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #define MOD 1000000007#define MAX_N 1000000typedef long long .. 더보기