공부중의 블로그

한번에 같은 문자들을 전부 다른 문자로 바꾸는 동작을 할 수 있다.이 동작으로 한 문자열에서 다른 문자열로 바꾸는 것이 가능한지 확인하시오. 꼬리문제 : 바꾸는 것이 가능한 문자열이라 할때, 중간에 버퍼를 삽입해야만 바꿀 수 있는 경우가 있다. 이런 경우인지 확인해 보시오.

우선 DP로 풀이 가능할 듯. int countnumber(string &s, int curr, int it){if(curr==s.size()) return 0;// go throughint ret = 0;for(int i = curr ; i < s.size() ; i++){if(s[i]==it+'a'){ret += countnumber(s,i+1,it);}else if(it!=2&&s[i]==it+'a'+1){ret += countnumber(s,i+1,it+1);}}return ret;} " 매 위치의 것을 포함하는 " 갯수를 세기 때문에, 섭문제의 합이 중복을 가지지 않는다 !!!경우의 수를 DP로 셀때는 특히 현재 위치에서 아예 새로운 조합을 만들어내는지 잘 확인해야 한다. 시간 복잡도 : O(N..

곱셈과 덧셈의 교환법칙에 의해 유일함이 담보된다.아나그람을 체크할때, SUM,PRODUCT를 비교하면 O(M) 으로 만드는 시간만 걸리고 비교는 O(1) 이 걸린다.만약 26개짜리 벡터를 비교하면 O(26) 이어서 조금 더 느리다. 시간복잡도는 같다.

hello to the world >> elhloothtedrowl이 된다.이때 이걸 해독할 수 있을까? 단어는 전부 딕셔너리에 들어있다. 풀이 : 각 단어를 카운팅한다. 이제 문자열을 앞에서부터 순회하면서 카운트가 맞는 단어가 있는 경우에 찾아서 그걸 자르고, 빼고( 중복이 가능한가 ?? 여기서는 유일한 조합만 있다고 하자 ) 남은 문자열에서 같은 작업을 재귀해 준다. vector findoriginal(vector & data, string & s){// 벡터 키는 안되지만 된다고 가정. 비트 수준으로 숫자 조합을 모은 다음에 해시로 뭉개버리면 된다.unordered_map dict;for(int i = 0 ; i < data.size() ; i++){vector counter(26,0);for(in..

그래프 문제 같은데..?? abcdedrive a > b > c > d > ed > r > i > v > e 이런식으로 directed graph가 되고 근데 DAG는 아니라서 topological sort는 안될꺼같은데,이 방법은 아닌거같다. 중복되는 문자들이 계속 나올 수 있는데 구현이 쉽지 않고 큰 의미를 찾기 어렵다. 완탐 , DP?최적화?어 이거 그거 될꺼같은데 트라이 만들기 비슷하게 아니면 앞에서부터 하나씩 꺼내기 bcdeppleirplaneoytdrive abca 맨 앞의 원소들 중 가장 작은 원소부터 꺼낸다. 중복이 있으면 전부 같이 꺼낸다. multimap을 쓰는게 제일 간단하고 효율적이겠다. logN * M(길이) 가 복잡도다 !! 엄청난 알고리즘.. string makesmallest..

일치하는 subfix와 postfix의 최대 길이를 물어보는건가? bcacbcaabbc 나이브하게는 하나씩 더하면서 팰린드롬인지 확인.. ( 무생각 )..아아.. 왼쪽에서만 추가하니까.. 결국에는 오른쪽에 이상한게 있으면 전부 보충해줘야 한다.즉, 뒤집은 문자열을 하나 만들고(이게 상한이다) 겹치는 만큼 줄인다. abccd >> dccba abccdbazcbbczab >> 1개 겹치니까(뒤집은거의 앞에서부터) 4개 추가해서 bczabazcb로 만들 수 있다. int findminadd(string s){string t = s;reverse(t.begin(),t.end());int ret = 0;while(s[ret]==t[ret]){ret++;}return ret;} time complexity : O(..

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

딕셔너리에 주어진 스트링 중에서 목표 string까지 하나씩 바꾼 시퀀스를 구해야 한다.아래 내용물들이 딕셔너리에 주어진다고 가정할 떄,CAT -> DOG CAT -> COT -> DOT -> DOG 이다 ( 아무거나 구해도 된다 ) 솔루션 : 우선, 두 시퀀스 중 서로 다른 문자는 무조껀 바꿔야 한다. 그 갯수를 N/k개라고 하면, 서로 다른 가능한 조합의 갯수는 2^N/k 개이다. 근데 그 조합들을 순서대로 짠다고 하면 결국 몇 경우가 없을 것 이 아니라.. 오히려 N/k개를 선택하는 조합의 갯수는..!! O(N/k!) 무려 이렇게 된다능.. 조합의 갯수보다 더 많다 ㅋㅋ.. 근데 딕셔너리에 존재하는 것들의 갯수가 한정적이고, 한 경우만 찾으면 되니까,, 각 점에 대해 바꾸는 경우로 생각해 보면 DF..

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 이고..