'Programming Problems'에 해당되는 글 64건

Programming Problems/일기

라인 인턴 면접

오늘 라인 면접을 봤다. 면접관 분들이 깃을 사용하지 않느냐고 해서 사용하고, 사용했었다고 답했는데 cloud9을 사용하기 때문에 깃을 사용하지 않고 그냥 파일을 저장하면서 진행한다고 대답했다.


다시 생각해 보면 정말이지 개발자로써 하면 안될 대답이었던 것 같다. 물론 개인 프로젝트였으니까 밭을 갈든 삽질을 하든 내맘이긴 하지만 전문적인 개발자라면 문서화와 버전관리는 항상 습관처럼 해야하지 않았나 .. 싶다.


정말이지 맞는 말이어서 이제 모든 작고 큰, 그리고 숙제까지도 깃헙을 통해 브랜칭 및 버전관리를 진행하기로 했다. 뭐 좋은 습관이기도 하고 생각해 보면 커밋 되돌려 가면서 진행하는게 편하기도 하니까.


뭐 깃 항상 사용하고 있긴 하지만 이제 좀더 하드하게 사용하는걸로

'Programming Problems > 일기' 카테고리의 다른 글

라인 인턴 면접  (0) 2018.05.30
Programming Problems/Strings

string transform

한번에 같은 문자들을 전부 다른 문자로 바꾸는 동작을 할 수 있다.

이 동작으로 한 문자열에서 다른 문자열로 바꾸는 것이 가능한지 확인하시오.


꼬리문제 : 바꾸는 것이 가능한 문자열이라 할때, 중간에 버퍼를 삽입해야만 바꿀 수 있는 경우가 있다. 이런 경우인지 확인해 보시오.

Programming Problems/list, tree

두 BST의 내용물이 같은지 확인하기

1. 두개의 inorder 결과 벡터를 비교한다. O(N), O(N)

2. iterator을 만들어서 하나씩 넘기면서 비교한다. O(N) O(1)

Programming Problems/Strings

a,b,c의 조합으로 이루어진 문자열에서 aaa..bb...c.. 형태의 조합의 갯수

우선 DP로 풀이 가능할 듯.


int countnumber(string &s, int curr, int it){

if(curr==s.size()) return 0;

// go through

int 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^2)


다른 풀이법 ( 최적화된 선계산법 )


아예 "갯수를 세는" 과정 자체가 DP 가 하는건데, DP 자체를 선계산 해버릴 수 있다.


If current character is ‘a’, then there are following possibilities :
    a) Current character begins a new subsequence.
    b) Current character is part of aCount subsequences.
    c) Current character is not part of aCount subsequences.
    Therefore we do aCount = (1 + 2 * aCount);

    If current character is ‘b’, then there are following possibilities :
    a) Current character begins a new subsequence of b’s with aCount subsequences.
    b) Current character is part of bCount subsequences.
    c) Current character is not part of bCount subsequences.
    Therefore we do bCount = (aCount + 2 * bCount);

    If current character is ‘c’, then there are following possibilities :
    a) Current character begins a new subsequence of c’s with bCount subsequences.
    b) Current character is part of cCount subsequences.
    c) Current character is not part of cCount subsequences.
    Therefore we do cCount = (bCount + 2 * cCount);


O(N) 이란다. ㅋㅋ 그냥 경우의 수 계산을 손으로 한 풀이인듯

Programming Problems/Arrays

부분배열 내의 최대값-최소값이 2와 같거나 작은 인덱스 조합의 수

head-tail을 쓰면 되지 않을까?


아니면 minmax preprocessing 쓰던가.


 3 5 7 6 3

th

 t h


응 됨.


^^%

Programming Problems/Digits

홀수와 짝수의 합이 같은 정수의 갯수 세기

제곧내. n  자릿수 보다 작은 홀수와 짝수의 합이 같은 정수의 갯수를 세보자.


DP를 사용해보자.


완전탐색에서 시작해 보자.


int countsame(int curr){

if(curr>n) return 0;

int ret = 0;

curr *= 10;

for(int i = 0 ; i < 9 ; i++){

if(isequal(curr+i)) ret = ret + 1 + countsame(curr+i);

else ret = countsame(curr+i);

}

return ret;

}


NlogN 알고리즘인듯. isequal이 logN짜리라서;


근데 저렇게 하면 중복이 있을꺼같다..


n자릿수 기준으로 만들어 보자


int countsame(int curr, int n , int odd, int even){

if(curr==n) return 0;

int ret = 0;

if(odd==even) ret++;

for(int i = 0 ; i < 10 ; i++){

if(curr%2==0){

ret += countsame(curr,n,odd+i,even);

}else{

ret += countsame(curr,n,odd,even+i);

}

}

return ret;

}


Programming Problems/Strings

ANAGRAM CHECKING

곱셈과 덧셈의 교환법칙에 의해 유일함이 담보된다.

아나그람을 체크할때, SUM,PRODUCT를 비교하면 O(M) 으로 만드는 시간만 걸리고 비교는 O(1) 이 걸린다.

만약 26개짜리 벡터를 비교하면 O(26) 이어서 조금 더 느리다.


시간복잡도는 같다.

Programming Problems/Strings

스크램블된 문자열을 dict를 이용해 해독해 보자.

hello to the world >> elhloothtedrowl이 된다.

이때 이걸 해독할 수 있을까? 단어는 전부 딕셔너리에 들어있다.


풀이 :


각 단어를 카운팅한다. 이제 문자열을 앞에서부터 순회하면서 카운트가 맞는 단어가 있는 경우에 찾아서 그걸 자르고, 빼고( 중복이 가능한가 ?? 여기서는 유일한 조합만 있다고 하자 ) 남은 문자열에서 같은 작업을 재귀해 준다.


vector<string> findoriginal(vector<string> & data, string & s){

// 벡터 키는 안되지만 된다고 가정. 비트 수준으로 숫자 조합을 모은 다음에 해시로 뭉개버리면 된다.

unordered_map<vector<int>,int> dict;

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

vector<int> counter(26,0);

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

counter[data[i][j]-'a']++;

}

dict.insert(pair<vector<int>,int>(counter,i));

}

return findoriginal(dict,s,curr);

}


vector<string> findoriginal(unordered_map<vector<int>,int> & dict, string & s, int curr){

if(curr==s.size()) return vector<string>():

// count map all words in dict


// 앞에서부터 순회하면서 카운트가 맞는 단어가 있으면 제시한다.

vector<string> ret = "";

vector<int> counter(26,0);

for(int i = curr; i < s.size() ; i++){

counter[s[i]-'a']++;

auto it = dict.find(counter);

if(it!=dict.end()){

vector<string> tmp = findoriginal(dict,s,i+1);

ret.insert(ret.end(),tmp.begin(),tmp.end()):

}

}

return ret;

}


재밌는건, dict에서 중복 사용이 가능하면 DP 가 가능해서 O(N^2) 알고리즘으로 캐핑이 가능하지만 만약 중복 사용이 불가능하면.. 디피가 안된다 .. ㅠㅠ 완전탐색이 되어버린다... 아닌가??

Programming Problems/Dynamic Programming

longest Chunked palindrome list

Examples : 

Input : VOLVO 
Output : 3 
Explanation : 
(VO)L(VO) 


Input : merchant 
Output : 1 

Explanation : No chunks possible. 

Input : 

ghiabcdefhelloadamhelloabcdefghi 

Output : 7 

Explanation : 

(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)


------------------

최악의 경우

(abcde) 1 개는 보장된다.

최선의 경우

abcba >> n개가 보장

azcba >> 3개

(a)(zcb)(a)

일단 팰린드롬인 애는 그대로 포장할 수 있다. 포장해도 되는 애를 안해서 얻는 이득이 있나?

팰린드롬인 단어를 포장하지 않는 경우 갯수가 무조건 감소하거나 같게 되므로 이득이 없다는 것을 안다. 만약 팰린드롬인 단어를 포함해야만 다른 곳의 아수라장을 피할 수 있다면?

a(c)za(c)z

안되면 더 큰걸 잡아야지 "안됨" 이 되는게 아니라서, 이런 그리디 솔루션은 어렵다.

이렇게 답이 막히면 완전탐색부터 시작해 보자. DP로 비벼질 지도?

acbac >> a c 달라서 안됨! ac는 됨! 이걸로 묶어서 그 안에껄 재귀하자. 오 이거 되겠네. 디피문제구나.

리얼 완전탐색을 생각하니 디피로 풀리는구나. 막히면 완전탐색!

postfix = prefix 경우를 순회하면서 모두 찾는다. 각각의 경우에 대해 2 + 안쪽 재귀 결과값을 구해서 그 최솟값을 찾아준다.

아, 그리고 *** " 최솟값 " 이 나오면 DP 일 가능성이 매우 높다.


막히면 완전탐색..

막히면 완전탐색..

막히면 완전탐색..!!!!


!!!!!


int findminbrackets(string & s, index k){

// base case

if(k==s.size()/2) return 1;

string tmp(s.begin()+k,s.end()-k-1);

string cmp = tmp;

reverse(tmp.begin(),tmp.end());

if(cmp==tmp) return s.size()-2*k;

// general case, find postfix == prefix

int ret = 1;

for(int i = k+1 ; i <= s.size()-k; i++){

int j = i;

int l = k;

int flag = 0;

while(j<=s.size()-k){

if(s[l]==s[j]){

j++;

k++;

}else{

flag = 1;

break;

}

}

if(flag==1) continue;

// found a postfix==prefix

ret = max(ret,2+findminbrackets(s,s.size()-j+1));

}

return ret;

}


caching을 쓰면 결국에는 가능한 k의 값이 N개 뿐이고, 각 순회에 대해 O(N)의 행위를 하므로 O(N^2) 이다..!!

Programming Problems/Digits

주어진 숫자를 이어서 만들 수 있는 가장 큰 값은?

1 112 113 >> 1131121

9 918 917 >> 9918917


성질 탐구


대소관계가 정해진다.


3 34 어느게 먼저? 34.

3 32 어느게 먼저? 3


323 324 어느게 먼저? 324


32 324 어느게 먼저? 324


만약 긴쪽의 남은 부분에 더 큰게 하나라도 있으면 긴걸 먼저 쓴다. 물론 남기 전의 모든 값이 같을때 얘기다.

자릿수가 양쪽 다 있는 경우 큰게 먼저 나오는 쪽을 먼저 쓴다.


4 111 >> 4111

4 115 >> 4115

4 415 >> 4154 4415


32 323123


이거는 즉, 3123을 끝에 놓느냐 중간에 놓느냐로 비교를 해야겠다. 이때 반복되는 부분 32와 3123을 비교해야 한다.

그러면 32가 더 크다는 결론을 얻는다. 만약


32 323223 이었으면


>>32 32 3223


32 3223


>> 32 32 23


32 23


>> 32 > 23 (결과 나옴)


끔찍한 비교방법이 나왔다. 버린다.


그냥 두개를 비교하는 방법은 서로 앞뒤로 붙인걸 대소비교 하는 방법이다. 직접 안 붙이고 인덱스 순회로 가능할듯


그럼 대소비교가 O(M+N) 정도 되는데, 자릿수가 많이 다를 수 있으므로.. 퀵소트를 한다고 치면 비교 횟수는 대략 NlogN 회 정도이므로 O(LNlogN) 이 되겠다. (L은 평균 길이)


소트를 해서 쭉 이어버린다.


bool comparator(string s, string t){

int currs = 0;

int currt = 1000500;

// currs는 s에서 시작하고 currt는 t에서 시작한다.

while(currs<s.size()+t.size()){

if(currs>1000000 && currt>1000000 && s[currs-1000500]!=t[currt-1000500]){

return s[currs-1000500]>t[currs-1000500];

}else if(currs<=1000000 && currt>1000000 && s[currs]!=t[currt-1000500]){

return s[currs]>t[currt-1000500];

else if(currs>1000000 && currt<=1000000 && s[currs-1000500]!=t[currt]){
    return s[currs-1000500]>t[currt];

else if(currs<=1000000 && currt <= 1000000 && s[currs]!=t[currt]){

return s[currs]>t[currt];

}else{

if(currs==1000500+t.size()) currs = 0;

else if(currs==s.size()) currs = 1000500;

else currs++;

if(currt == 1000500+t.size()) currt = 0;

else if(currt==s.size()) currt = 1000500;

else currt++;

}

}

// completely same

return true;

}


string concatenate(vector<string> & data){

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

string ret = "";

for(string x : data) ret += x;

return ret;

}


말한 대로, 시간 복잡도는 O(LNlogN) 이다.

공간 복잡도는 뭐 O(LN) 정도? 출력해야 하니까..