dh_0e

비트마스킹을 활용한 dp 문제, 근데 이제 큰 수 % k를 곁들인 .. 시행 착오 vector > dp[][]로 선언을 하여 dp[i][j] = i개의 원소를 합쳤을 때, 마지막 원소에 j번째 원소를 삽입한 pair(first = 지금까지 삽입한 원소들의 비트마스킹, second = k로 나눈 나머지)를 삽입하는 것으로 점화식을 짰다.이 후에 말도 안 되는 메모리 초과를 보여주며 전처리 및 메모리도 줄인 후 진행했는데 여전히 답이 안 보였다. 해결 방안갈아엎었다. 점화식부터 다시 구상하니 dp[i][j] = 지금까지 사용한 원소를 마스킹한 값이 i, 나머지가 j인 수열의 갯수 로 풀 수 있었다.전처리 및 dp에 각각 하나씩 사용한 경우의 수 저장ten_mod에 10^l 들을 k로 나눈 나머지를 모두 구해..

누적 합과 이분 탐색으로 쉽게 풀 수 있는 문제lower_bound, upper_bound 오랜만에 직접 구현해보다가 결국 귀찮아서 라이브러리에 있는 거 썼다.. 풀이 과정누적 합으로 A, B 배열의 부 배열의 합이 될 수 있는 경우의 수를 모두 vector에 저장해준다. (최대 500500 경우의 수)둘 중 하나를 sort 해준다.upper_bound - lower_bound로 target(t - vec_a[i])이 몇 개나 있는 지 구해서 dap에 더해준다.dap은 int 범위를 넘을 수 있으므로 long이나 long long으로 처리해준다.못 찾았을 경우 up, lo 모두 end() 저장소의 위치를 가르키므로 예외처리 안 해줘도 0을 더한다. #include#include#includeusing n..

1~$10^{12}$ 범위인 N과 서로수인 수의 개수를 구하는 문제 깡으로 하면 무조건 시간 초과이므로 오일러 피 함수의 성질을 이용해서 풀 수 있다.  시행 착오에라토스테네스의 체로 소수를 모두 구별하여 N을 소인수분해 한 뒤, 오일러 피 함수의 성질을 이용하여 답을 도출하는 식으로 구상했지만, $10^{12}$ 이하의 가장 큰 소수가 999999999989이므로 당연히 메모리 초과가 나왔다. 풀이 과정사실 2부터 시작해서 N의 값을 나눌 수 있을 때까지 나누면 소수를 따로 구할 필요없이 소수로만 나눌 수 있다.나눌 때마다 오일러 피 함수의 성질을 이용하여 변수를 지정해 곱해놓으면 답을 구할 수 있다. ※ N=99처럼 sqrt(N)보다 N의 약수(11)가 더 큰 경우가 있으므로 이 경우엔 N이 1까지 ..

데이터베이스(DB, database)서로 연관 있는 데이터의 모임을 의미컴퓨터에 데이터베이스가 저장되어 있으면, 이를 관리하는 소프트웨어가 필요이를 데이터베이스 관리 시스템(DBMS, database management sys-tem)이라 함DB, DBMS, DBS(database system, = DB + DBMS) 용어가 상호 대체적으로 사용됨 DBMSs의 advantagesData abstraction - 데이터 추상화 제공Easy accessing data - 데이터 접근의 용의성 제공Controlled data redundancy and inconsistency - 데이터 중복 및 불일치성에 대한 제어 용이불일치성 - 데이터 간에 값이 서로 일치하지 않은 현상file system 사용 시 데이터..

정렬과 priority queue만 적절히 사용할 줄 알면 쉽게 풀리는 문제  사람들의 집과 사무실의 위치는 바뀌어도 상관 없으므로 first 값이 작도록 설정한 뒤, second 값을 기준으로 오름차순 정렬해줌 (second 값이 같을 경우 first 값 오름차순으로)차례대로 우선순위 큐 top에 있는 사람을 기준으로 범위 안에 들어가는 지 확인O: 우선순위 큐에 i번째 사람 추가, 범위 안에 있는 사람 수가 max인 지 확인X: 범위 안에 들어갈 때까지 top에 있는 사람을 pop해줌 #include#include#includeusing namespace std;pair d[1000001];priority_queue > prique;bool cmp(const pair & a, const pair & ..