이모저모

해결방법벡터의 외적을 이용하여 선분의 교점을 판단하는 문제이다.1) 각 선분을 기울기가 작은 값으로 sort2) 레이저도 마찬가지로 기울기가 작은 값으로 sort3) 모든 선분에 대해서3-1) 선분 벡터에서 레이저의 위치를 구한다.(upper_bound)3-2) 위치 이하의 값들에(그 이상의 값에 대해서는 검사를 해봐야 해당사항 없고 다음 레이저가 수행한다.) 대해서 레이저와 외적을 구해

벡터를 이용해서 간단히 문제의 쿼리에 맞게 처리만 해주면 되는 문제이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_back#define mp make_pairtypedef long long ll;typedef unsigned long long ull;typedef pair pll;typedef pair pii; bool cmp(pii lhs, ..

해결방법1) 알고리즘 실력 기준으로 정렬한다.2) 순서대로 탐색2-1) d만큼 차이나는 위치를 찾는다.2-2) 해당 구간에서의 알고리즘 갯수를 카운팅한다.2-3) 효율성을 구한 뒤 최대 효율성을 구한다.시간 복잡도 O(NK)단순히 구간만큼의 갯수를 카운팅하면 O(N*N*K)가 될것이다.하지만 이미 구해진 구간을 재활용할 수 있다면. 시간복잡도를 줄일 수 있다.구간을 더하는 최대 갯수가 NK, 빼는 최대 갯수가 NK이므로 O(NK)가 나옴 아래는 소스코드이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#d..

버블소트의 성질이 이용하는 문제이다. 처음 LIS를 활용하여 길이 x일 때 n-x+1로 구할라고 했으나 반례가 있었던것 같다. 위 문제는 버블소트의 성질인 (원래 위치 - 정렬 후 위치) 값 이 가장 큰 값만큼 수행하면 정렬된다.왜냐하면 문제의 버블소트는 가장 큰 값을 끝부터 차곡차곡 쌓아가므로작은 값은 한번 루프를 돌 때 한칸 씩만 이동하기 때문에 차이가 가장 큰 값만큼 루프를 돌아야한다. 소스코드 #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2..