onaeonae1

문제부터 빠르게 살펴보자 https://www.acmicpc.net/problem/31848 도토리가 빠지는 구멍들이 정렬이 안 되어 있어 이분 탐색에 어려워보인다. 하지만 시뮬레이션을 생각해보면, 어차피 큰 구멍 사이에 있는 작은 구멍은 의미가 없다. 이런 경우에는 기존에 더 큰 값으로 덮어씌워도 된다. 그러면 최대값을 갱신해가며 기록하면 된다. 즉 오름차순으로 배열이 생겨나게 된다. 여기서 lower_bound 를 깔끔하게 써주면 문제를 해결할 수 있다. 코드#include#includeusing namespace std;int N, M;vector minHoles;int main() { cin.tie(0); cin.sync_with_stdio(false); cin >> N; int maxV = 0;..

길이 N짜리 배열이 있을 때, 여기서 어떤 가운데 지점을 고르고, 그걸 기준으로 왼쪽과 오른쪽을 비교하고자 한다.  구현은 간단하다.1. 어떤 가운데 지점을 start 부터 시작해, end-1 까지로 잡는다.2. 해당 start 를 기준으로 + 쪽이 right, - 쪽이 left 라고 가정하고 (start, end) 사이에 있도록 해준채 무식하게 비교하면 된다 문제를 풀어보자https://www.acmicpc.net/problem/31846 #include#include#includeusing namespace std;int N, t;string s;vector items;int do_search(int start, int end) { int ans = 0; int m = start; for (int m..

얼마전에 코테를 봤는데 개털렸다 N 개 중에 M개를 못뽑는 바보가 여기있다. 결론부터 말하자면 재귀를 사용해서 구해주면 된다. https://www.acmicpc.net/problem/15686이 문제를 풀어보자 M개의 가게를 선택하고, 그 조합으로 계산을 해주면 되는 아주 간단한 문제이다. 근데 조합 못구하면 못품 #include#include#includeusing namespace std;struct store { int y; int x; bool checked;};vector> houses;vector stores;vector selected;int N, M;int ans = 1e9;void calculateDistance() { int total = 0; for (int i = 0; i dis..

요약CDC = Change Data CaptureCQRS 를 구현하기 위한 방법 중 하나로 접근하면 됨  배경)각자 DB를 가지고 있는 서비스들이 존재하는 MSA의 서비스를 생각해보자만약 이들로부터 통합된 어떤 View 를 제공해야 한다면 어떻게 해야할까? 목표)서비스 개발자들은 통합된 View 를 위해서 각 서비스의 코드에 어떤 변화도 할 필요가 없어야 한다.DB의 변화(테이블 변경이든 레코드 변경이든)를 최대한 자동으로 감지, 전달해야 한다. 방법1)어떤 BFF 를 두고 그 쪽에서 모든 서비스들로부터 물어와 주거나 Caching 을 극도로 활용하는 방법을 생각해볼 수 있다. 근데 이건 한계가 명확하다.1. 누군가 이 BFF와 Caching 을 맡아서 처리해야하고, -> 각 서비스에서 아무리 이벤트를 ..

어떤 숫자들의 입력이 계~속 주어진다. 들어온 입력들에 대해서 중앙값을 계속 반환해야 한다. 자 그럼 이걸 어떻게 해볼까? 들어온 입력을 계속 push 하고 정렬을 한다?-> N번 동안 N 크기의 배열을 정렬하므로 N^2logN  . 따라서 시간 초과가 될 수 밖에 없다. 우리가 원하는 건 "중앙값"이다. 구체적으로 전체가 어떻게 정렬되어 있는지는 관심이 없다.중앙값을 T 라고 했을 때, T는 정렬된 List 에서 가운데에 위치해야 한다. 하지만, 정렬을 다해주면 시간 초과. 그래서 정답 T에 대해 배열을 다음과 같이 나눠보자.1. 무조건 작은 쪽 -> LEFT2. 무조건 큰 쪽 -> RIGHT LEFT에 있는 모든 애들은 RIGHT 보다 반드시 작아야 한다. 그래서 LEFT를 최대힙으로 설정. RIGH..

우선순위 큐의 개념은 "우선순위"를 기반으로 큐에서 POP 하는 것을 의미한다그냥 큐는 "들어온 순서" 를 우선순위로 갖는 우선순위 큐라고 이해하는 편이 좋다. 암튼, 이 우선순위는 일종의 정렬된 상태를 유지한다고 이해해도 좋다e.g) 3개의 아이템들이 유지되는데, 여기서 제일 적은 놈을 뽑아서 값을 추가하며 나아감 https://www.acmicpc.net/problem/22254 이 문제가 정확히 이에 해당한다. N개의 공정을 가정하고, 그 공정이 우선순위 큐 안에 있는 아이템으로 취급한다.그리고 N개의 공정이 조건을 만족하냐? 만족 안하냐? 를 찾는 일종의 파라메트릭 서치라고 이해하면 될듯 하다. #include#include#includeusing namespace std;int N, M;vect..