호지

벡터는 방향성이 존재하므로 +,- 둘 다 가능한 것을 놓치면 안 된다. 처음에 벡터의 마이너스 경우는 생각하지 않았다가 헤맸다ㅜㅜ 벡터의 합은 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값에 더해..

처음엔 조합으로 접근하였으나 시간초과로 실패했다. n개의 나무 중에서 1, 2, .... n-1를 제거했을 때 울타리를 만들 수 있나 확인하도록 구현하였으나 n의 최대값은 40으로 당연히 시간초과가 나온다. 결과적으로 구현한 방법은 N^5 로 5중 for문을 통해 구현하였다. 직사각형을 만들 때, 그 직사각형의 꼭지점은 직사각형 내부 나무들 중 x와 y의 최소, 최대값을 4개의 꼭지점으로 해야 펜스 설치 시에 낭비되는 나무가 없을 것이다. n개의 나무가 주어졌을 때 만들 수 있는 직사각형의 모든 경우를 구하면 x값을 오름차순 정렬한 xsort와 y값을 오름차순한 ysort값을 4중 for문을 통해 구할 수 있다. 각 직사각형에서 해당 직사각형이 펜스를 만들 수 있는 지 확인하고 이 중 벤 나무가 최소인 ..

다이아몬드 형식의 위 특성을 활용해서 ld, rd배열에 각 위치에서 최대로 뻗을 수 있는 대각선의 크기를 저장한다. 이후 ld rd의 값이 둘 다 0이 아닐때, 2~ min(ld값, rd값)의 길이(n)을 갖는 다이아몬드가 생성 가능한지 확인 한다. 다이아몬드 생성가능 여부는 왼쪽 대각선을 내렸을때 좌표의 rd값이 n이상이면서, 오른쪽 대각선을 내렸을때 좌표의 ld값이 n이상인지 확인한다. (다이나믹 프로그래밍) #include using namespace std; int main(){ int r, c, res =0; cin >> r >> c; int ld[r][c], rd[r][c]; char input; for(int i=0; i input; if(input == '0'){ ld[i][j] = 0; ..