호지

문제를 보자마자 dp를 적용해서 풀어야겠다고 느꼈으나 아직 dp로 푸는건 너무 오래걸리는 것 같다. 분발하자. dp 테이블의 [i ,j]의 원소 값은 i에서 j까지 분할을 했을 때 펠린드롬 분할이 가능하면 true, 불가능하면 false이다. (따라서 테이블에서 i> s; for(int i=0; i

반으로 나누지 않으면 시간 초과가 된다. 수열을 반으로 나눠 계산한다. 왼쪽의 경우 가능한 모든 부분 수열의 합을 key로 하여 map에 개수를 저장한다. 오른쪽의 경우 가능한 모든 부분 수열의 합을 s에서 뺀 경우 map에 해당 key가 있다면 결과에 해당 개수를 더한다. 공집합인 경우에도 포함하여 계산되었으므로, s가 0이라면 res를 1감소시킨다. #include #include #include #include #include using namespace std; vector list; int n,s; long long res; map m; void right(int pos, int sum){ if(pos == n){ m[sum] ++; } else{ right(pos+1, sum); right(p..

pos> n >> k; vector jw(n); int m,v; for(int i=0; i> m >> v; jw[i] = make_pair(m,v); } vector c(k); for(int i=0; i> c[i]; } sort(c.begin(), c.end()); sort(jw.begin(), jw.end()); priority_queue q; long long answer = 0; int pos = 0; for(int i=0; i

최소 스패닝 트리 문제를 크루스칼 알고리즘을 적용하여 풀었다. find_root는 연결된 최상위 노드를 찾는 함수이다. union_root는 연결할 2개의 노드가 최상위노드가 다르면 같게 바꿔주는 함수이다. 간선과 가중치에 대한 정보를 edge vector에 저장하고 가중치 기준으로 sort한 후, edge벡터를 탐색함으로 가중치가 최소인 최소스패닝트리를 구할 수 있다.(그리디 알고리즘) #include #include #include using namespace std; vector edge; vector parent; int find_root(int x){ if(parent[x] == x) return x; else return parent[x] = find_root(parent[x]); } void..

벡터는 방향성이 존재하므로 +,- 둘 다 가능한 것을 놓치면 안 된다. 처음에 벡터의 마이너스 경우는 생각하지 않았다가 헤맸다ㅜㅜ 벡터의 합은 V1 + V2 = V이고, 점 N개에 대해서 벡터의 개수는 N/2이므로, 시작점 N/2개와 끝점 N/2개를 갖는다. 따라서 N개중에서 N/2개를 뽑는 조합을 DFS로 구현하고, 벡터의 합이 Va과 Vb일 때 Va가 시작점이고 Vb가 끝점일 때의 벡터의 길이와 Va가 끝점이고 Vb가 끝점일 때의 벡터의 길이 중에서 최솟값을 구해서 출력한다. *벡터의 길이는 sqrt(x*x +y*y) *소수점은 double형, 출력시 printf로도 가능하고 c++에서 precision도 사용 가능하다. #include #include #include #include using na..

2차원 벡터 d의 i번째 원소에 i번 건물보다 선행되어야할 건물의 정보를 저장했다. time벡터에는 선행작업이 없는 건물을 찾아 delay[i]를, 나머지 time에는 -1를 저장했다. 그 이후 time[w]의 결과를 찾을 때까지 1~n까지를 반복하며 선행될 건물의 time값이 모두 구해진 경우에 해당 위치의 time값을 구했다. (다이나믹 프로그래밍) +처음 제출 시 시간이 높게 나와서 c++에서 알고리즘 문제 풀이 시 cin,cout사용시 속도를 줄일 수 있는 ios_base::sync_with_stdio(false); cin.tie(null); cout.tie(null); 를 알게 되었다. 대신 getchar등 c에서 사용하는 입출력함수를 같이 사용하면 안 된다. +cout > n >> k; for..

소수를 구하는 에스토스테네스의 체를 기반으로 한 알고리즘 풀이이다. list에 min-max의 최대인 1000001을 할당한다. 2부터 제곱이 max보다 작거나 같을 때까지 모든 수의 제곱의 배수를 탐색한다. 제곱의 배수의 시작점은 값이 min보다 크거나 같을때이다. 따라서 x=min/i*i로 배수의 시작점을 구할 수 있고, i의제곱이 min일 확인하기 위해 min%(i*i)=0이면 x를 1감소한다. list에서 제곱의 배수가 되는 위치는 true로 저장하여 list에서 false인 경우에 제곱 ㄴㄴ수이므로 해당 값을 카운트하여 출력한다. #include #include using ll = long long; using namespace std; bool list[1000001]; int main(){ ..

long long 변수형을 써야되는데서 삽질을 했다.. 역시 변수의 최대범위는 잘 확인해야... 숫자들은 최대 길이가 50이상이므로 string 자료구조로 받아 처리해야 된다. ten_mod_k에 1%k, 10%k, .. 10^50%k값을 구한다 mod_k에 각 원소의 %k 값을 구하고, dp값을채운다 dp[a][b]에서 a는 비트마스크로 해당위치의 원소가 쓰였는지 확인하고, b는 0~k-1값으로, 비트마스크로 확인한 원소로 숫자를 만들었을때 나머지가 b인 개수이다. ex) n = 3, [1, 2, 3] k=2 d[1][0]=0, d[1][1] = 1, d[2][0] = 1, d[2][1] = 0, d[4][0] = 0, d[4][1] = 1 ten_mod_k와 mod_k, d배열을 통해 0 ~ (1>>..

a[i]+1 이 a[i+1]이 아닌 정렬 중 사전 순이 가장 빠른 결과를 출력하는 문제이다. 사전 순이 가장 빨라야 하므로 오름차순 정렬을 진행한다. v[i]+1이 v[i+1]일 때, 2가지의 경우를 확인하면 된다. 1. v[i+1] 값과 v[n-1] 값이 같은 경우, v[i]값을 가지는 원소 중 가장 작은 index를 가지는 값과 v[i+1]를 swap한다. (두 원소의 값 차이는 1이므로 v[start+1] ++, v[i+1] --로 swap을 진행함) ex) 111222-> 211122 -> 221112 -> 222111 2. v[i+1]값과 다른 값은 가지는 원소중 가장 작은 index를 가지는 값과 v[i+1]를 swap한다. ex) 1233334... -> 1243333.... #include..

각 재료의 비용을 map구조를 이용해 'cost[재료명] = 비용'이 되도록 저장하였다. m개의 식이 주어질 때, find함수를 활용하여 처음은 구분자 '=' 이후에는 구분자 '+'로 문자열을 파싱하였다. 처음보는 재료명이 나오면 cost[재료명] = -1로 저장하였고, 벡터v에 식에 대한 내용을 S와 벡터 _v(n1 s1, n2 s2....)형식으로 저장하였다. vector v v[i].first = S, v[i].second = ({n1, s2}, {n2, s2}....) 입력을 다 받고 나면 물약의 식을 저장한 v벡터를 탐색 함으로 결과를 구할 수 있다. i for문 : 0~v.size() 모든 물약의 식 탐색 j for문 : 0~v[i].second.size() Nj * Sj 값을 sum값에 더해..