공부중의 블로그

아예 랜덤하게 하나씩 뽑는것도 재밌을 듯. 그리고 나오는게 현재 인덱스들과 어떻게 구성되는지 비교하고 맞출 수 있으면 리턴.아니면 앞에서부터 순회해야겠지. 현재 처음이야. 다음게 더 작아. 그럼 그걸 처음으로 잡아. 다음게 더 커. 그러면 그게 다음꺼야. 그리고 작은게 나오면 .. 이런식으로는 서로 떨어진 경우를 찾을 수 없다. 자명한 해는 소팅하는 방법.. O(NlogN) 랜덤하게 하나를 뽑는다. 5 9 이렇게 두개 뽑았는데 중간의 더 작은값이면 버리고.. 아 근데 이것도 결국에는 그걸 못찾고 지나치겠다. 해싱이 답인거같다 O(N) 뽑으려면해싱해가면서 수를 기록한다.아니면 프리프로세싱..!! 어 프리프로세싱 되겠다.오른쪽에 자신보다 큰게 있는가?왼쪽에 자신보다 작은게 있는가? == 왼쪽의 max가 자신..

스테이트가 정리가 안되서 결국 완전탐색 선에서 귀결되는 문제가 된다고 하네. DP 솔루션이 있을까? 근데 DP가 별거냐 그냥 완.탐에 범위상한 붙인거지.. int N, v[22], r[22], dp[ 1

ex) "cat", "catapult">> "CATapult", "CatApulT", "CAtapulT"답 : 3 솔루션 : 우선 바로 떠오르는 방법은 없으니 나이브에서 시작하자. DP로 비벼지는게 보인다 O(MN)으로. int findall(string & s, string & t, int scurr, int tcurr){if(tcurr==t.size()) return 1;// go through starting from scurrint ret = 0;for(int i = scurr ; i

ex)소수 : [2,3]N = 4표현 가능한 수 : [1,2,3,4,6,8,9,12...]답 : 4 풀이 : 수열이 각 소수의 곱셈에 따라 반복적으로 구성된다. 즉, 1 2 3 4 6 8 ..이 포함되면2 4 6 8 12 16 ..3 6 9 12 18 24 ..이 각각 포함된다. 따라서 1을 처음에 놓고, 다음 후보군은2,3 중 하나다. 작은 2를 뺴고, 2의 다음 후보 4를 놓는다.계속 가장 작은 것 하나를 빼고 진행한다. 이렇게 N 개 세면 된다. 타임 컴플렉시티는 O(N * logK), K는 소수의 갯수이다. BST를 이용해서 최대값을 바로바로 조회하고 I/O를 해 주면 된다.

두개의 동전을 던져서 1 앞, 2 뒤 면 true를 리턴하고 1 뒤 2 앞이면 false를 리턴한다. 둘이 같은게 나왔으면 그냥 다시 한번 굴린다. 그러면 앞뒤 뒤앞은 각각 p*(1-p) 로 확률이 같게 되서 출력되는 기대값은 0.5다!! while(true) { p1 = rand_bit_p(); p2 = rand_bit_p(); if(p1 && (!p2)) return true; // prob = p * (1-p) if((!p1) && p2) return false; // prob = (1-p) * p }

분수가 주어지는 경우, 소숫점 표현법으로 바꿔보자. 순환소수가 있는 경우 괄호를 출력한다.ex)1/3 = 0.(3)2/4 = 0.5(0)22/7 = 3.(142857) 솔루션: 분모를 소인수분해해서 2와 5로만 구성되 있으면 그냥 나눈걸 출력한다. 끝에 (0)을 붙인다.아니면 아래의 알고리즘을 쓴다. 정수로 나눈 값이 0이면 분자에 10을 곱한다. 정수로 나눈 값이 다음 자릿수다.0이 아니면 그걸 그냥 그대로 붙이고 넘어간다. 지금까지 나온 소숫점 아래 숫자가 다시 나왔으면 순환은 거기까지다. 근데 이 경우에 순환소수가 바로 시작하지 않는 경우와 순환소수 내의 숫자가 반복되는 경우 패턴 매칭이 상당히 어렵다. 다른 시도로는 순환소수 분수 형태로 주어진 분수를 고치는 방법이다.. 근데 경우의 수가 상당히 ..

제곧내. 세는 프로그램을 짤것. 생각해 보면 이건 모두 서로 연결된 완전 그래프이고, 찾는건 해밀토니안이다. 즉 갯수는 9! 가지.. 그냥 permutation을 찾으면 된다. void printpermutation(unordered_set buffer, vector maker){if(buffer.size()==){cout

10010 >> 다음 숫자 : 10100 앞 숫자 : 10001 풀이 : 오른쪽에 1이 있는 첫 0과 그 1을 스왑하면 (반대로 얘기하면 바로 옆이 비어있는 첫 1) 다음 숫자이다. ***오른쪽이 비어있는 첫 1을 그 오른쪽으로 밀면 바로 작은값왼쪽이 비어있는 첫 1을 그 왼쪽으로 밀면 바로 큰값01 >> 큰값10 >> 작은값 pair (int n){// base casesif(n==0) return pair(0,1);if(n==-1) return pair(-2,0);int m = 1;int bigger = 0;int smaller = 0;int preflag = m&n;m = m1));}if(preflag==0&&n&m!=0){// smaller foundsmaller = n^(m^(m>>1));}if..

ex ) aaaabbbb, k=2 >> aaaabbbbasdfrttt, k=3 >> frttt 나이브 솔루션 : 긴 섭스트링부터 안에 있는 원소의 수가 맞는지 본다. O(N^3) 알고리즘. 해시 테이블을 이용한 트래킹.헤드 테일을 곁들여서. 헤드를 늘려 가면서 맵에 원소의 수와 갯수를 체크한다.갯수가 K 일때 길이를 확인한다.K 보다 갯수가 많아지만 tail을 앞으로 보내면서 하나씩 뺀다.갯수가 K일때 길이를 확인한다.head를 K보다 갯수가 많아질때까지 계속 앞으로 보낸다.헤드가 끝에 닿으면 계산하고 끝낸다. O(N) 알고리즘 ..!!

job : 5,9,17in : 4,13,18google : 8,19,21 >> 17,18,19 ans : 3 처음부터 최솟값을 하나씩 들어올리면서 길이를 재계산한다. 모두 마지막에 닿을 때까지 O(NlogN^K) ( 힙으로 최솟값을 트래킹한다 ) 정당성 : 최솟값을 증가시키기 않고 다른 것을 증가시키면 최솟값이 그대로 남게 되어 결국 범위가 증가하거나 같게 된다. 최솟값이 존재한다고 가정하면 최솟값이 아닌 것을 ... 모르겠다 더 생각해 보자 이런 경우 우리는 "이 검색 방식이 최솟값을 지나치지 않는다" 를 확인하면 된다. 만약 우리가 i -> k가 최솟값이라고 결론내렸는데 사실 i->k'가 최적의 솔루션이라고 생각해 보자. 이때, i,k,k' 중에 k'가 최솟값이 아니므로 k'를 k로 옮기지 않은 상태..