목록Algorithm/Memo &Tips (25)
블로그 옮겼습니다
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(),..
12if(n == (n&-n)) printf("2의 거듭제곱!");else printf("2의 거듭제곱 아님!");cs 이유를 설명하자면 2의 거듭제곱은 어떤 한 비트만 켜져있을 것이다.n & -n 은 n에서 켜져있는 가장 아래의 비트만 켜진 수이다.그렇기 때문에 2개 이상이 켜져있다면 n & -n와는 절대 같아질 수 없는 것이다.그리고 n에 비트가 하나만 켜져있다면 n & -n 은 그 비트만 켜진 수가 되므로 같게되는것이다. +그리고 & 연산자보다 == 연산자가 더 우선순위가 높으므로 괄호를 감싸는것을 잊으면 큰일난다..
우선 N개의 원소를 가진 어떤 임의의 배열 X가 있고,이 안에 크기 M의 구간(subarray) A가 있다고 하자. 물론 값들은 정렬되지않은 상태이다. 이 때 A의 K번째 원소를 구하는 방법은 여러가지가 있다. 우선 내가 아는 K번째 원소를 찾는 방법들을 구체적으로 써보자면(사실 내가 파라메트릭서치라고 표현하는것도 역시 바이너리 서치인데, 구분을 위해 다르게씀)(그리고 값의 범위가 큰 경우에는 좌표압축은 이미 했다고 가정한다.)1. 벡터+sort2. k번째 원소 세그먼트트리3. k번째 원소 BIT4. BIT + 파라메트릭서치 + 바이너리서치5. 머지소트+세그먼트트리+파라메트릭서치+바이너리서치6. 2D 세그먼트트리 이것 이외에도 버킷으로 어찌저찌하는 것도있는것같은데 잘모르겠다. 이것들 중에서 쿼리가 들어와..
예를 들어vector v[3] 이 있고v[0] = {2, 5, 9, 3}v[1] = {0, 7, 4}v[2] = {1, 6, 8} 일때, 각각의 벡터를 정렬한 뒤 벡터들은 사전순으로 정렬 하려면그냥 sort(v, v+3) 을 하면 알아서 한꺼번에 정렬됨
홀수 Degree를 가진 노드의 수는 짝수개이다!짝수 Degree를 가진 노드에 대한 성질은 따로 없다.. 짝수개일 수도 홀수개일 수도 있음
1scanf("%*d%d",&y);cs 이런식으로 하면 %*d 는 정수하나 입력받아 무시하겠다는거고 그뒤에 y를 하나 입력받겠다는거다.
Union-find 다른 말로 Disjoint sets(상호 배타적 집합) 이란 여러개의 집합들에 대해,서로 다른 두 집합의 교집합이 공집합이며, 모든 집합들의 합집합이 전체 집합이 되는 집합들을 말한다.그런데 이게 유용한 이유는 이렇다. 1. 서로 다른 두 원소가 같은 집합 내에 속해 있는지, 아니면 서로 다른 집합에 속해있는 지를 빠른 시간내에 구할 수가 있다.2. 서로 다른 집합에 속해있는 두 노드가 속해있는 두 집합을 빠른시간에 합쳐 더 큰 하나의 집합으로 만들 수가 있다. 그렇기 때문에 크루스칼 알고리즘에서도 유용하며, dfs 대용으로도 쓸 수가 있으며 그 활용이 무궁무진하다.그런데 일반적인 방법으로는 집합을 한꺼번에 합치는 것은 가능하지만, 집합 내의 특정 한 원소 단위로는옮길 수가 없다. 하..
문제들 중에는 특정 조건을 가진 시간과 분을 hh:mm 의 포맷으로 출력하거나 리턴하기를 원하는 문제들이 있다.이럴때 괜히 쓸데없는곳에 시간과 노력을 낭비하지 않기 위해 좋은 방법이 있다.1sprintf(out, "%02d:%02d", h, m);cs 사실 너무 기초적인 것이지만 오랫동안 별로 쓸 일이 없었던 것이라 잊고있었다..이걸 모르면 이런 상황이 발생할 수가있다..123456string ret;if(h
1234memset(d,0,sizeof(d)); for (i=0;i