[비요뜨]

5분안에 마스터 하는것이기 때문에 아주 간결하고 핵심 요약만 말할것이다. 준비물 : hash에 대한 기본 지식, 이분탐색에 대한 기본 지식 1. 이분탐색을 돌린다. 길이가 i인 문자열이 반복으로 나온다면 그 아래는 볼 필요가 없다. 즉 이분탐색이 가능하다. 2. hash테이블을 이용하여 같은 문자열이 있는지 검사한다. hash테이블을 써서 길이 i인 것들중 같은것이 있는지 체크해준다. (hash에 대한 기본지식은 알고 있기 바란다.) 시간 복잡도는 O(NlogN) 이다 아래의 코드는 3033 번 문제이다. 바로 코드를 보겠다. #include using namespace std; const int mod = 100003; int f(long long x) { // x % mod 를 양수로 만들어주는 함수..

C++ 로 조합을 구현하는 방법을 알려주겠다. nCr = n-1Cr-1 + n-1Cr 라는 식을 이용하여 O(nr) 만에 구하는 방법도 있지만, n,r 이 10만정도 된다면 메모리도 시간도 펑펑 터질 것이다. 그래서 이번 글에는 조합을 빨리 구하는 방법을 알려주겠다. (와아앙아앙아아 짝짝짝짝) 순서는 STL내장함수인 next_permutation 을 사용해서 출력하면된다. (이 글은 나중에 추가될 예정이다) 조합을 구할려면 일단 식을 보자 이제 이 식을 직접 구하면 되는데 n! 을 구하고 r! 을 구하려고 하면 mod 값에 나눠버리는 경우가 있어서 매우 까다롭다. 예를 들어보자. mod = 7, 구하려고 하는 수는 5C3 이다. 그러면 5! 을 구하고 3! 을 구하고 2! 을 구하고 5! 구한것에서 3!..

이 문제는 영어로 이루어져 있으니 간략하게 한국어로 설명하겟다. 요뜨가 사다리를 타고 내려오고 있다. 사다리에서는 지렁이가 a[i]개씩 살고 있고 b[i]일이 지나면 그 가로 사다리는 갉아 먹혀서 없어진다. 요뜨는 사다리의 피해를 막기 위해 내려오면서 살충제를 뿌리려고 한다. 각 높이 에서는 최대 한번만 뿌릴 수 있다. 이때 갉아 먹히는 가로 사다리의 개수를 구하고, 무엇인지를 출력한다. 이런 문제다. 그래서 풀이는? 이 문제는 버블 소트로 풀수가 있다. 그래서 자세한 풀이는?? n이 매우 작은 탓에 안심하고 풀 수 가 있다. 그래서 어떻게 푸냐고?? 모두 함께 꿀다이아 문제를 풀어보도록 하자. 그래... 그러면 코드나 줘 코드를 첨부하겠다. #include using namespace std; int ..

알고리즘은 BCC를 사용한다. 모른다면 다른블로그를 참고하도록 하여라. 그래서 1. 리프 노드의 개수를 가지고 센트로이드 점을 잡는다. 2. BCC를 만든다. 3. 문제의 정답을 잘 출력한다. 이렇게 하면 된다. 풀이는 별로 필요 없고 코드가 중요하지 않는가. 코드를 보여주겠다. #include using namespace std; typedef long long ll; typedef pair pi; int n,m,k,co,root,d[100005],sz[100005],c[100005],inbcc[100005],it[100005]; vector tv[100005],v[100005],bridge[100005]; vector nobridge; vector bcc; stack S; set leaf[100005..

이 글에서는 적당한 존댓말과 적당한 반말을 섞은 말투를 할 거다. 일단 노답 문제다. 정해가 뭔진 모르겟지만 걍 노답 문제다. 섭테 2까지는 1에서는 'E', 나머지는 'O'를 출력하라고 하면 충분히 가능하다. ㅔ케헤케헤헤켘헤헤ㅔㅔ케ㅔ헤헿ㅎ헿ㅎ헤ㅣ히히헤힣키ㅣ헤히히킿히히히켛헿 이제부터가 시작이다. 저의 풀이의 경우에는 1. 1~10억까지 답을 구하라고 돌려놓는다. 2. 출력으로 E가 나오는 구간을 출력하라고 한다. 3. 그대로 배열에 박아 넣어서 숫자가 입력 받을때 마다 그 구간안에 포함되는지 보고 포함되면 'E', 아니면 'O'를 출력하도록 한다. 아 배고파 이제 코드를 보자. #include using namespace std; typedef long long ll; char in[55]; int nu..

11차원이라고 겁먹지 말자. 그냥 [] 가 11개 있을 뿐이다. 이번글에서는 반말을 사용하겠다. ㅇㅋ? 자 보면 걍 부분합 배열 채워서 쓱-싹 하면 되는 문제잖아 그치? 근데 포함-배제의 원리를 사용하면 시간초과가 나! (아이고 안타까워라) 그래서 새로운 방법으로 부분합 배열을 채울꺼야! 2차원 배열이 있다고 생각해보면 위에서 아래로 부분합을 한번 하고 왼쪽에서 오른쪽으로 부분합을 한번해! 그러면 부분합 배열이 만들어 지거든? (와 개쩐다;;) 이제 그러면 포함-배제의 원리를 이용하여 부분합 배열을 채우면 O(2048N) 으로 시간초과가 나지만 이제 11차원(우엑;;)으로 늘려보면 11번의 뱡향으로 밀면 된다는 것을 알았다! 그래서 저 방법을 사용하면 O(11N) 으로 된다 이말이야! 짝짝짝짝짝 내가 코..

오프라인 다이나믹 커넥티비티 알고리즘을 알아보자. Offline Dynamic Connectivity 는 간선 추가, 삭제를 오프라인으로 처리하는 문제에 쓰인다. 대표적으로 BOJ의 16911 = 16912 = 15316 < 12876 < 15946 순으로 문제가 어렵다. (16911,16912,15316 이 3개중 하나만 풀어도 나머지 2개는 꽁짜..) 여러가지 방법이 있겠지만 저는 분할 정복을 사용했습니다. (사실 1가지임 ㅋ) 일단 간선의 라이프 타임을 저장해 둡니다. (나타난 시간 ~ 사라진 시간) 생기고 지워진 적이 없다면 맨 마지막 시간으로 해둡니다. (나타난 시간 ~ 마지막 시간) 이제 분할정복을 해줄텐데 solve(l,r,Edge set) l~r : 간선 라이프 타임이 l~r 이고 m = ..

아무거나 제출해도 다맞진 않는다. 인생...참 빠르네

알고리즘은 그리디 입니다. 일단 제일 가격이 낮은 숫자들로 최대한 채웁니다. 이때, 0 이 제일 싼 가격이면 그 다음으로 싼 가격의 숫자를 맨 앞에 놓고 그 뒤에 0을 쭉 붙입니다. 그러면 쓰고 남는 돈이 있는데 이 돈으로 최대한 큰 수로 바꿉니다. 각 숫자에 대해 몇개씩 살 수 있는지 나오는데 이 숫자들을 내림차순으로 나열하면 제일 큰 숫자를 만들 수 있습니다. 제가 쫌 코드를 드럽게 짜기 때문에 풀이 이해용으로만 보시기 바랍니다. (못 볼듯...) #include using namespace std; typedef long long ll; int n,pl,End; ll k,x,co[15],ch[15],tmp[15]; struct Money { ll cost; int num; }a[15]; bool c..

DP[n] : n번째 징검다리를 건널때 나올 수 있는 경우의 수 라고 잡아보면 DP[n] = DP[n-1]+DP[n-2]+...+DP[1] 이라는 식이 나오는데 DP[n-1] = DP[n-2]+DP[n-3]+...+DP[1] DP[n-2] = DP[n-3]+DP[n-4]+...+DP[1] . . . DP[1] = 1 이제 DP[1]부터 DP[n-1]을 DP[n]의 식에 대입해 보면 DP[n] = 2(DP[n-2]+DP[n-3]+...+DP[1]) = 2^2(DP[n-3]+DP[n-4]+...+DP[1]) = 2^3(DP[n-4]+DP[n-5]+...+DP[1])... =2^(n-2)DP[1] 가 나옵니다. DP[1] = 1 이기 때문에 답은 2^(n-2) 가 됩니다. 각 테스트 케이스마다 2^(n-2)를..