공부중의 블로그

ex ) [2,1,1,4,3,6], sum = 8 이면 답은 [3,6]의 2이다. 만약 최소합을 구하는 문제였으면 psum을 구해서 전부 sum을 뺀 후에 정렬하고, 정렬된 것들 중에서 앞엣값 - 뒤엣값이면서 최소인 psum 차이를 구할 수 있을텐데 ( 앞뒤로 비교해 가면서 찾기 ) 최소 길이를 구하는 문제니 다르게 풀린다. 모든 부분수열의 갯수가 N^2 개이고 그 합을 구하는게 N 이므로 대략 노가다로 하면 O(N^3) 이 상한이겠고하한은 한번은 가봐야 아니까 O(N) 이겠다 우선 최선부터 접근해 보자. 만약에 sum 보다 큰 원소가 있으면 1을 리턴하고 종료한다.근데 여기서 확장이 불가능한게 2개짜리에 만약 존재하는데, (5,5) 우리가 최대값인 (1,6,1) 주변에서 안된다고 해서 없는게 아니니까...

ex ) 8799, K = 2 에서 ans = 9987 나이브하게는 모든 경우의 수를 만들어서 (N^2 ^ K) 스왑하고, 그 결과들 중에서 가장 큰 것을 찾는다 ( & data ) 이렇게 만들어서 한번에 하나씩 비교할 수 있을 듯. 그렇게 하면 비교가 N 시간이 걸리므로 O(N * N^2 ^ K) 시간이 걸리겠다. 여기서 더 가려면 규칙성을 찾는 그리디 알고리즘이나, 동적 계획법으로 풀게 되겠다. 자료구조를 이용한 해법은 없는 것 같다. 동적 계획법이 생각난다. 아니 그리디 솔루션인가.. 그리디 솔루션을 살펴보자. 매 단계에서 자신이 할 수 있는 최선을 다하면 최대 결과가 만들어질까? 모든 숫자가 역순으로 정렬된 것이 아닌 이상 최대 뒤집기를 찾을 수 있다.동적 계획법은 M이 n자리 10진법 수이기 때..

ex ) a?b?c >> a0b0c0 a0b0c1 ... 바로 코딩하겠읍니다.. void printallpermutations(string s, vector & ret, int curr){// general case// go through until ? metfor(int i = curr; i < s.size() ; i++){if(s[curr]=='?'){s[curr]='0';printallpermutations(s,ret,curr+1);s[curr]='1';printallpermutations(s,ret,curr+1);return;}}// base caseret.push_back(s);return;} 순회는 "모든" 재귀함수들에 걸쳐 처음 : 1 * a1, 두번째 2* a2 ... 2^N * an 이고..

ex) [2,7,5,5,2,7,0,8,1] >> [5,1,2,2,2,1,2,0,0] >> 최댓값 : 5 LIS와 비슷한 풀이법이 가능할지 한번 해보자. 안된다. 대소비교는 본인 기준으로 상대적이기 때문이고, 숫자를 세는 데에 중복이 존재한다. 그러면 결국에는 갯수 세는 BST를 만들면서 진행하는 것 밖에 없을 듯 하다. int findmax(vector & data){struct node {node * right;node * left;int value;int rank;node(int v) : value(v), rank(1), left(NULL), right(NULL){}}int ret = 0;node * root = new node(data.back());for(int i = data.size()-1 ;..

연속된 숫자의 부분집합 중 최대를 구해보자. ex ) [1,6,10,4,7,9,5] >> {4,5,6,7} 나이브 : 정렬을 해서 순회하면 O(NlogN) 에 가능하다!! 좀 더 나은 방법이 없을까.. 방법은 순회하면서 군집을 만들어 나가는데, 해시맵에 각 군집의 전후를 기록해 둔다. 그리고 새로운 원소가 들어오면 군집을 필요에 따라 합치고 최대 길이를 확인한다!! vector consecutivesequence(vector & data){// make a hashmap for start and end pointsunordered_map buffer; // go through dataint currmax = 0;int curri = 0;for(int i = 0 ; i < data.size() ; i++)..

제곧내.. node * findKthfromend(node * head, int K){int count = 0;node * runner = head;while(count!=K){head = head->next;// if whole list is smaller than Kif(head==NULL) return NULL;count++;}node * walker = head;while(runner!=NULL){runner = runner->next;walker = walker ->next;}return walker;}

검색기록을 확인하는 프로그램을 작성하자. 같은 페이지를 방문하면 최근으로 다시 갱신된다.ex ) GABCAY >> YACBG 최근 기록을 리스트로 관리한다. 해시 테이블에 현재 존재하는 값들을 저장한다.새로운 값이 이미 존재했던 값이면 리스트 포인터를 맨 앞으로 옮긴다. 없던 값이면 리스트 끝을 드랍하고 새로운 값을 넣는다. string recents(string & s ){unordered_map hash;list recent;for(int i = 0 ; i second = recent.begin();}else{// new elementhash.erase(recent.back())..

주어진 패턴을 주어진 스트링이 따르는지 확인한다.패턴 : abba , 스트링 : redbluebluered >> 1패턴 : aaaa, 스트링 : asdasdasdasd >> 0 나이브 솔루션 :패턴 첫 글자를 매칭해서 맵에 넣는다(임의로 잘른 모든 경우에 대해). 그리고 남은 스트링과 패턴에 대해 같은 작업을 반복한다.남은 스트링이 없는데 패턴이 남으면 0 리턴, 다음 패턴이 이미 있는 패턴이면 그걸 적용해 보고 안되면 0. 스트링과 패턴이 전부 0이면 그때 1최악의 경우 O(N^N) 이런거 막 나올수 있겠다. 가능은 함. bool isMatch(string str, int iStr, string ptn, int iPtn, unordered_map &hmap){ if(iStr == str.size() &..

ex ) 1 2 7 8 9 의 최소합은 129+78 (순서 바꾸기 가능) 나이브 솔루션 : 그냥 두 집합으로 쪼갠 후에 합을 구해 최소를 찾는다 > 각 합을 만드는 시간 O(N), 갯수 : 2^NO(N2^N) 솔루션 성질을 더 이용해 보자. DP 하기에는 성질을 너무 많이 사용하고 앞의 값을 재활용하기 어렵다(?) 아닌데. 앞의 최소합이 있으면 새로운 원소가 들어오는 경우 둘 중 더 작은 값으로 가야하지 않나? 엌 greedy 방법이 여기잉네된다. greedy. 나머지가 이미 최소값인 조합으로 구성되어 있기 때문에, 새로운 숫자를 더 작은쪽에 붙이면 된다. 알고리즘뒤에서부터 숫자를 만들어 나간다. 그때그때 대소비교를 O(1)에 할 수 있도록 알고리즘을 짜면작은 쪽의 맨 앞에 숫자를 append 하면 된다..

string에서 repeating subsequence를 찾아보자.예)abab : sub "abab"가 반복하는 subs이다.abba : 없음azcaxc : "acac" 가 반복한다. 풀이 ) bool hasrepeat(string s){for(int i = 1 ; i