본문 바로가기

알고리즘 관련

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,.. 더보기
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 .. 더보기
BOJ)5012 불만 정렬 문제: icpc.me/5012 iAk를 만족하는 경우의 수를 세는 문제이다. 우리는 j를 기준으로 생각해보자. 현재 j를 보고 있을 때 경우의 수에 해당할 수 있는 경우는 result = SUM [ (j보다 먼저 등장하고 Aj보다 큰 수) x (j보다 나중에 등장하고 Aj보다 작은 수) ] 으로 나타낼 수 있다. 따라서 우리는 쿼리를 다 받은 후 앞에서 부터 보면서 j보다 먼저 등장하면서 Aj보다 큰 수들을 먼저 기록 한 후 다시 한번 뒤에서부터 보면서 j보다 늦게 등장하면서 Aj보다 작은 수들을 기록해준 뒤 곱해주어 더한값을 출력하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #in.. 더보기
BOJ)3002 아날로그 다이얼 문제: icpc.me/3002 N개의 다이얼이 주어졌을 때 구간이 주어지면 구간의 합을 구한뒤 구간의 수를 전부 1씩 증가시켜주는 문제이다. 얼핏보면 구간에 대한 증가연산과 구간합을 출력하면 되니 레이지 프라퍼게이션을 이용한 구간합으로 바로 해결할 수 있을것 같지만 문제는 다이얼이기 때문에 9를 증가시키면 0이 된다는 것이다. 결국 0~8의 숫자는 증가시킬 경우 1씩증가하게 되지만 9는 증가시킬 경우 오히려 -9가 되버린다. 이래서 구간에 대한 합을 한번에 노드에 저장하고 있을 경우 증가연산이 애매해질 우려가 있다. 따라서 우리는 구간마다 노드를 10개씩 만들어 0~9까지의 개수를 저장하여 값을 증가시키는 경우 0~9 ->(0+x)%10~(9+x)%10까지로 쉬프트 시킬것이다. 물론 구간에 대한 증가가 .. 더보기
BOJ)1168 조세퍼스 문제2 문제: icpc.me/1168 N명의 사람이 원을 이루며 앉아있고 M번째 사람을 제거하면서 진행할 때 제거되는 순서에 따른 순열을 출력하는 문제이다. 세그먼트 트리를 이용하여 현재 위치에서 M번째 사람을 찾아내서 풀면 된다. 이때 주의 할 점은 환형이기 때문에 남아있는 사람수를 고려하여 모듈러 연산이 필요하다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #include #include using namespace std;int seg[400040];int n, m;vector ans;int update(int pos, int val, int node, .. 더보기

티스토리툴바