공부중의 블로그

1 112 113 >> 11311219 918 917 >> 9918917 성질 탐구 대소관계가 정해진다. 3 34 어느게 먼저? 34.3 32 어느게 먼저? 3 323 324 어느게 먼저? 324 32 324 어느게 먼저? 324 만약 긴쪽의 남은 부분에 더 큰게 하나라도 있으면 긴걸 먼저 쓴다. 물론 남기 전의 모든 값이 같을때 얘기다.자릿수가 양쪽 다 있는 경우 큰게 먼저 나오는 쪽을 먼저 쓴다. 4 111 >> 41114 115 >> 41154 415 >> 4154 4415 32 323123 이거는 즉, 3123을 끝에 놓느냐 중간에 놓느냐로 비교를 해야겠다. 이때 반복되는 부분 32와 3123을 비교해야 한다.그러면 32가 더 크다는 결론을 얻는다. 만약 32 323223 이었으면 >>32 32 ..

[["quick","slow"],["brown","red"],["fox","dog"]] 의 모든 조합을 출력해 보자.예시) quick brown fox void printcombinations(vector & data, int curr, vector maker){if(curr == data.size()){for(string x : maker) cout

ㅋㅋ 문제1. N개의 정수 배열에서 두개의 합이 target 이하인 모든 조합 찾기 // sort 후에 head tail 기법을 사용한다. vector findtwo(vector & data, int target){// sortsort(data.begin(),data.end());// go through arrayint tail = 0;vector ret;for(int i = 0 ; i < data.size() ; i++){while(data[i]-data[tail]< target){ret.push_back(pair(data[tail],data[i]));tail++;}}return ret;} time complexity : O(NlogN), bucket sort 같은걸 사용 가능하면 O(N).. 문제 2..

// sort 후에 head tail 기법을 사용한다. vector findtwo(vector & data, int target){// sortsort(data.begin(),data.end());// go through arrayint tail = 0;vector ret;for(int i = 0 ; i < data.size() ; i++){while(data[i]-data[tail]< target){ret.push_back(pair(data[tail],data[i]));tail++;}}return ret;} time complexity : O(NlogN), bucket sort 같은걸 사용 가능하면 O(N)..

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

저번에도 했었는데 자신보다 작으면서 가장 큰 n*(n-1)/2 를 찾는다. 그 다음 row에서 K-x 번째 원소를 찾는다. time complexity : O(N) (!!!)space complexity : O(1) (!!!) 구현하기 귀찮은데.. 내일이 면접이니 해볼까? 아니.. 후회할까? 글쎄.. 귀찮은데코드를 짜면서 헤메면 보기 매우 안좋다. 코드는 정말 알고리즘 및 필요한 자료구조와 계산을 완벽히 정리한 후에깃발 꽂는 용도로만 쓴다. 아주 구체적으로 알고리즘을 먼저 짜자. int findKthelement(vector & data, int K){// find the matching diagonal indexint n = data.size();int flag = 0;// element to find..

우선 "최소"를 물어본데다, 최적해가 없어 보이고(자료구조해도), DP가 될 것 같아 보이니까 완전탐색에서 시작해서 DP로 캐핑해보자.그냥 완전탐색을 생각해 보면, 본인보다 작은 모든 완전제곱수를 1 ~ 최대 갯수만큼 채우면서 재귀를 돌려보자. int findmin(int n, int curr, int total){if(curr==0) return 0;int ret = INT_MAX;for(int i = 0 ; curr*i> O(N^2) 알고리즘 쯤 될듯.

일치하는 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(..

진짜 멍청한 조합탐색(정말 순서 없이는 절대 풀 수가 없어서 - 폭탄이 터진다던가 - 결국에는 순서를 전부 기록해야 결과 확인이 가능한 경우)고른다. 마지막에서 계산한다. 확인한다. 여기에서 더 발전시킬 수 없을까? "마지막에 하는 작업을 분산시킬 수 있나"마지막에 뭘 하는데? 합을 구한다. 그러면 합을 단계별로 구할 수 있잖아? 당연하지. 그러면 현재까지의 합을 인자로 넘겨가며 계산한다. 어 인자가 두개네, curr, sum >> DP capping이 가능해진다.게다가, sum = total/2 면 자동으로 종료가능하다..!! (참고로 이 문제는 knapsack와 유사한 DP다) bool canfind(vector & data, int curr, int total, int sum){if(total>su..