블로그 옮겼습니다

1번째 방법12345678stringstream ss1(S);for(string str1; getline(ss1,str1,' ');){ stringstream ss2(str1); vector in; for(string str2; getline(ss2,str2,',');) in.push_back(stoi(str2)); int a,b,c; tie(a,b,c) = {in[0],in[1],in[2]};}Colored by Color Scriptercs 2번쨰 방법1234567// "a,b,c d,e,f h,i,j" 와 같은 형태의 문자열 파싱하기 stringstream ss1(S);for(string str1; getline(ss1,str1,' ');){ int a,b,c; sscanf(str1.c_str(),..

문제 링크 \(1\leq{N}\leq{30}\)\(0\leq{M}\leq{30}\)\(1\leq{K}\leq{8}\) 이 문제는 N개의 집이있을 때 집과 집을 잇는 M개의 양방향 도로를 설치 하는 문제이다.A번 집과 B번 집을 잇는 도로를 설치하기 위해서는 01); } ll& cache = dp[u][v][k][mask]; if(cache != -1) return cache; cache = 0; cache = (cache + go(u,v+1,k,mask)) % mod; int nextmask = mask^(1

문제 링크 \(2\leq{N}\leq{10^5}\)\(1\leq{K}\leq{200}\) 이 문제는 N개의 노드로 이루어진 트리가 주어진다. 각 노드에는 가중치가 있다.K가 주어지는데 최대 K번 가지를 칠 수 있다는 것이다. 어떤 노드 u를 가지친다는 말의 정의는노드 u를 루트로 하는 서브트리를 제거한다는 것이다. 최대 K번 가지를 쳐서 남아있는 트리의 모든 노드의가중치의 합을 최대로 하고싶을때 이 최대 가중치합을 구하는 문제이다. 우선 처음에 일반적인 트리dp 문제처럼 이렇게 풀어 보려고했었다.dp[u][v][k] : 현재 노드 u를 보고있고 v개의 자식을 이미 봐주었으며 앞으로 최대 k번 가지칠수있을 때 최대 가중치 합 이렇게 하면 부분문제의 수는 최대 N*K 개이다. 왜냐하면 (u,v) 의 쌍은 간..

문제 링크 이 문제는 N개의 물통이 있고 L리터의 물을 N개의 각 물통에 나눠서 채우려고 하는데,물통에는 상한과 하한이 있어서 각 물통에 채울 수 있는 물의 양은 이 상한과 하한 사이의 양이어야만 한다. 이 때 N개의 물통에 채운 물의 양 중에서 가장 많은 양과 가장 적은 양의 차이가 최소가 되도록 하고싶다.이 떄의 차이를 구하는 문제이다. 단, 들어오는 입력들은 항상 L리터를 상, 하한에 맞춰 분배할 수 있는 방법이적어도 하나는 있다고 가정한다. 일단 이 문제는 두가지의 풀이가 있다.첫번째 풀이는 라인 스위핑(+그리디)이다. 내가 대회 때 푼 방법이 이 라인 스위핑인데대회가 끝나고 보니 나 말고는 라인스위핑으로 푼사람을 찾을 수가 없었다.좋은건지 안좋은건지.. 사실 처음에 다른 풀이 방법을 떠올렸다가 ..

문제 링크 격자의 사이즈 N,M 이 주어진다. 각 판은 '.' 또는 '1'~'9' 의 숫자이다. 그리고 n,m 이 주어지는데 n,m이란 어떠한 격자칸에서부터 시작하는 연속된 칸에 있는 수들의 합이 홀수가되어야 한다는 제약 조건에 대한 변수이다. 칸에서 아래로 n칸의 합은 홀수여야하고,오른쪽으로 m칸의 합도 홀수여야한다는 것이다. 물론 열 인덱스가 M-m+1 인 칸 까지만 적용되며행 인덱스가 N-n+1 인 칸까지만 적용된다. 이 때 '.' 인 칸에 적절한 '1'~'9'의 수를 넣어주어 위에서 말한 조건을 만족하도록 하는 방법의 수를 구하는 문제이다.일단 각 수가 홀수인지 짝수인지만 중요하기 때문에 현재 적혀있는 수가 실제로 몇이던 상관없고 짝수인지 홀수인지만중요하기 때문에 먼저 짝수는 0, 홀수는 1이라고..

12if(n == (n&-n)) printf("2의 거듭제곱!");else printf("2의 거듭제곱 아님!");cs 이유를 설명하자면 2의 거듭제곱은 어떤 한 비트만 켜져있을 것이다.n & -n 은 n에서 켜져있는 가장 아래의 비트만 켜진 수이다.그렇기 때문에 2개 이상이 켜져있다면 n & -n와는 절대 같아질 수 없는 것이다.그리고 n에 비트가 하나만 켜져있다면 n & -n 은 그 비트만 켜진 수가 되므로 같게되는것이다. +그리고 & 연산자보다 == 연산자가 더 우선순위가 높으므로 괄호를 감싸는것을 잊으면 큰일난다..

문제링크 모든 자연수를 \(1+2+4+.....+2^{k-1}+r\) 로 분해할 수가 있는데M개의 수를 이 방식대로 분해하여 분해된 요소들을 모두 모아 정렬한 결과인 sequence를 A라고 해보자. \(1\leq{N}\leq{10^5}\)\(1\leq{a_i}\leq{10^{12}}\) sequence의 크기 N과 N개의 elements 로 이루어진 A의 원소들 ai 가 입력으로 들어온다. 이 A를 다시 분해하기 전의 원래의 수로 복원하려고하는데 복원하는 방법은 여러가지가 있을 것이다.복원의 결과로 나온 수가 K개일 때 K가 될 수 있는 수는 여러가지가있을 것이다. 이 때 이 가능한 K들을오름차순으로 모두 출력하는게 문제의 질문이다. 우선 k+1 개의 수를 \(1+2+4+.....+2^{k-1}\) 의..

\(1\leq{N}\leq{50}\)\(0\leq{K}\lt{2^N-1}\)괄호 문자열(correct parenthese sequence)의 정의는 이미 잘 알려져 있다.그리고 어떤 문자열 S가 '(' 와 ')' 로만 이루어져있는데 괄호 문자열이 아니라면 이것을 괄호ㄴㄴ문자열이라고 정의한다.N과 K가 주어진다. 길이가 N인 괄호ㄴㄴ문자열들을 사전순으로 정렬했을 때 K번째인 문자열을 찾는 문제이다.인덱스는 0부터 시작한다는 것에 주의하자. 우선 괄호 문자열의 개수를 구하는 방법을 알아보자.dp[i][j] : 이미 i개의 문자가 정해졌고 짝이 지어지지않은 열린 괄호의 수가 현재 j 개일 때 괄호 문자열의 수dp[i][j] = dp[i-1][j] + dp[i-1][j+1]왜냐하면 각각의 위치에서는 괄호를 열거..

우선 N개의 원소를 가진 어떤 임의의 배열 X가 있고,이 안에 크기 M의 구간(subarray) A가 있다고 하자. 물론 값들은 정렬되지않은 상태이다. 이 때 A의 K번째 원소를 구하는 방법은 여러가지가 있다. 우선 내가 아는 K번째 원소를 찾는 방법들을 구체적으로 써보자면(사실 내가 파라메트릭서치라고 표현하는것도 역시 바이너리 서치인데, 구분을 위해 다르게씀)(그리고 값의 범위가 큰 경우에는 좌표압축은 이미 했다고 가정한다.)1. 벡터+sort2. k번째 원소 세그먼트트리3. k번째 원소 BIT4. BIT + 파라메트릭서치 + 바이너리서치5. 머지소트+세그먼트트리+파라메트릭서치+바이너리서치6. 2D 세그먼트트리 이것 이외에도 버킷으로 어찌저찌하는 것도있는것같은데 잘모르겠다. 이것들 중에서 쿼리가 들어와..

boj.kr/9426 \(1\leq{N}\leq{250000}\) \(1\leq{K}\leq{5000}\) \(K\leq{N}\) \(0\leq{a_i}\leq{65535}\) 이 문제는 N개의 수와 구간의 길이 K가 주어졌을 때 N-K+1 개의 연속된 구간의 중앙값을 모두 더하여 출력하는 문제이다. 중앙값의 정의는 (K+1)/2 번째로 작은 수이다. naive 하게 생각해보면 O(N)개의 구간에 대해 정렬하여 가운데값을 구하는데 O(NlgN) 이므로 O(N^2lgN)이 든다. 근데 O(N^2)도 시간안에 돌아가기 힘들다. 어떻게할까? 펜윅트리에 수가 현재 길이 K의 구간안에 하나 들어갈 때마다 수 자체를 인덱스로 1업데이트하고 구간에서 사라지면 -1업데이트하는식으로 생각해보자. 그럼일단 0번째인덱스부터..