오늘로 돌아오고 싶니 ?

ㅋㅋ

문제1. N개의 정수 배열에서 두개의 합이 target 이하인 모든 조합 찾기

// sort 후에 head tail 기법을 사용한다.

vector<pair<int,int>> findtwo(vector<int> & data, int target){

// sort

sort(data.begin(),data.end());

// go through array

int tail = 0;

vector<pair<int,int>> ret;

for(int i = 0 ; i < data.size() ; i++){

while(data[i]-data[tail]< target){

ret.push_back(pair<int,int>(data[tail],data[i]));

tail++;

}

}

return ret;

}

time complexity : O(NlogN), bucket sort 같은걸 사용 가능하면 O(N)..

문제 2. N개의 스트링을 받았을 때, 주어진 스트링을 섭시퀀스로 가지는 가장 렉시오그래피컬리 작은 스트링 찾기.

그래프 문제 같은데..?? 

abcde

drive

a > b > c > d > e

d > r > i > v > e

이런식으로 directed graph가 되고 근데 DAG는 아니라서 topological sort는 안될꺼같은데,

이 방법은 아닌거같다. 중복되는 문자들이 계속 나올 수 있는데 구현이 쉽지 않고 큰 의미를 찾기 어렵다.

완탐 , DP?

최적화?

어 이거 그거 될꺼같은데 트라이 만들기 비슷하게 아니면 앞에서부터 하나씩 꺼내기

bcde

pple

irplane

oy

t

drive

abca

맨 앞의 원소들 중 가장 작은 원소부터 꺼낸다. 중복이 있으면 전부 같이 꺼낸다.

multimap을 쓰는게 제일 간단하고 효율적이겠다. logN * M(길이) 가 복잡도다 !! 엄청난 알고리즘..

string makesmallest(vector<string> & data){

// make buffer

multimap<char,int> buffer;

vector<int> curr(data.size(),0);

for(int i = 0 ; i < data.size() ; i++){

buffer.insert(pair<char,int>(data[i][0],i));

}

// make result string by appending smallest element

int flag = 0;

string ret = "":

while(buffer.size()!=0){

auto it = buffer.equal_range(*buffer.begin());

ret.push_back(*buffer.begin());

for(auto run = it->first; run!=it->second; run++){

// remove and increase index

if(curr[run->second]!=data.size()-1){

curr[run->second]++;

buffer.insert(pair<char,int>(data[run->second][curr[run->second]], run->second));

}

auto tmp = --run;

buffer.erase(run);

run = tmp;

}

}

return ret;

}

time complexity : O(MNlogN)

space complexity : O(N)

문제 3. 모든 row와 column이 sorted 일때, K번쨰 작은 원소 찾기

저번에도 했었는데 자신보다 작으면서 가장 큰 n*(n-1)/2 를 찾는다. 그 다음 row에서 K-x 번째 원소를 찾는다.

time complexity : O(N) (!!!)

space complexity : O(1) (!!!)

구현하기 귀찮은데.. 내일이 면접이니 해볼까? 아니.. 후회할까? 글쎄.. 귀찮은데

코드를 짜면서 헤메면 보기 매우 안좋다. 코드는 정말 알고리즘 및 필요한 자료구조와 계산을 완벽히 정리한 후에

깃발 꽂는 용도로만 쓴다. 아주 구체적으로 알고리즘을 먼저 짜자.

int findKthelement(vector<vector<int>> & data, int K){

// find the matching diagonal index

int n = data.size();

int flag = 0;

// element to find in buffer

int tofind = 0;

K--;

int x,y;

if(K<=(n*(n+1)/2)){

y = (sqrt(1+8*K)-1/2);

x = 0;

tofind = K-y*(y+1)/2;

}else{

x = (sqrt(1+8*(n*n-K))-1/2);

tofind = x+1-(n*n-K-1-x*(x+1)/2);

y = data.size()-1;

}

vector<int> buffer;

while(x<data.size()&&y>=0){

buffer.push_back(data[x][y]);

x++;

y--;

}

return findKthpartition(buffer, tofind);

}

문제4. 숫자 n 이 주어졌을 때, 완전제곱수의 합으로 표현할수 있는 최소 갯수는?

우선 "최소"를 물어본데다, 최적해가 없어 보이고(자료구조해도), 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<=n ; i++){

ret = min(ret, i+findmin(n-curr*i,curr-1,total));

}

return ret;

}

time complexity : 함수실행 N * sqrt(N), 실행당 대량 sqrt(N) 회 수행 >> O(N^2) 알고리즘 쯤 될듯..

문제 5. string 앞에다가 최소한의 문자를 더해서 palindrome 만들기. 최소 갯수는?

일치하는 subfix와 postfix의 최대 길이를 물어보는건가?

bcacbc

aabbc

나이브하게는 하나씩 더하면서 팰린드롬인지 확인.. ( 무생각 )..

아아.. 왼쪽에서만 추가하니까.. 결국에는 오른쪽에 이상한게 있으면 전부 보충해줘야 한다.

즉, 뒤집은 문자열을 하나 만들고(이게 상한이다) 겹치는 만큼 줄인다.

abccd >> dccba abccd

bazcb

bczab >> 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(N) ( 뒤집으니까 )

space complexity : O(N)

문제 6. 합이 같은 두 부분집합으로 배열을 쪼갤 수 있을까?

진짜 멍청한 조합탐색(정말 순서 없이는 절대 풀 수가 없어서 - 폭탄이 터진다던가 - 결국에는 순서를 전부 기록해야 결과 확인이 가능한 경우)

고른다. 마지막에서 계산한다. 확인한다.

여기에서 더 발전시킬 수 없을까? "마지막에 하는 작업을 분산시킬 수 있나"

마지막에 뭘 하는데? 합을 구한다. 그러면 합을 단계별로 구할 수 있잖아? 당연하지.

그러면 현재까지의 합을 인자로 넘겨가며 계산한다.

어 인자가 두개네, curr, sum >> DP capping이 가능해진다.

게다가, sum = total/2 면 자동으로 종료가능하다..!!

(참고로 이 문제는 knapsack와 유사한 DP다)

bool canfind(vector<int> & data, int curr, int total, int sum){

if(total>sum) return false;

if(total==sum) return true;

bool ret = canfind(data,curr+1,total,sum+data[curr]);

return ret | canfind(data,curr+1,total,sum);

}

... ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 아 진짜 DP 너무 좋아..

재귀DP짱짱

시간복잡도 : O(MN) maximum cap to total sum

사실 모든 int에 대해 counting sort를 하면 O(N) 아니냐 하는 것 만큼이나 눈가리고 아웅이긴 한데 ㅋㅋ;;;
사실 2^N 이 MN보다 작을 가능성도 충분하다. 아 그래도, 하드캡이 2^N 인지라 이것보다는 무조건 빠르다. 캐싱이 추가된거기 때문에 최악의 경우가 재귀가 된다. 적어도 조금은 낫다!!

문제 7. 증가하는 세개의 인덱스를 한번의 순회에 찾으라는데 ?

아예 랜덤하게 하나씩 뽑는것도 재밌을 듯. 그리고 나오는게 현재 인덱스들과 어떻게 구성되는지 비교하고 맞출 수 있으면 리턴.

아니면 앞에서부터 순회해야겠지.

현재 처음이야. 다음게 더 작아. 그럼 그걸 처음으로 잡아. 다음게 더 커. 그러면 그게 다음꺼야. 그리고 작은게 나오면 .. 이런식으로는 서로 떨어진 경우를 찾을 수 없다.

자명한 해는 소팅하는 방법.. O(NlogN)

랜덤하게 하나를 뽑는다. 

5 9 이렇게 두개 뽑았는데 중간의 더 작은값이면 버리고.. 아 근데 이것도 결국에는 그걸 못찾고 지나치겠다.

해싱이 답인거같다 O(N) 뽑으려면

해싱해가면서 수를 기록한다.

아니면 프리프로세싱..!!

어 프리프로세싱 되겠다.

오른쪽에 자신보다 큰게 있는가?

왼쪽에 자신보다 작은게 있는가?

 == 왼쪽의 max가 자신보다 큰가?

 == 오른쪽의 min이 자신보다 작은가?

3 2 5 4 1

x x o o x

o o o o x

oo인 점이 있으니 true. 아마 두번째 프로세싱 만들면서 바로 발견가능할듯 .. !!!