사이냅소프트 2009년도 신입 및 경력사원 모집을 위한 퀴즈..~

우연히 KLDP에서 글을 보다가..
사이냅 소프트에서 개발자 채용 공고가 나왔다.. (이미 마감된것같다.. ㅋ)
http://kldp.org/node/104827

그런데 채용과정에서 면접 이전에 숙제를 내준다..~
궁금해서 봤더니.. 문제가 ACM-ICPC 스타일의 문제이다..~
나도 한번 풀어볼려고했다가.. 좌절.. ㅠ_ㅠ
문제는 다음과 같다..  

퀴즈.doc

문제 출처: (링크)

근래 들어서 IT기업들이 개발자를 뽑을때 이런 류의 퀴즈를 내는 경우가 많은 것 같다..
학부때 ACM 대회같은걸 준비한다면 도움이 될 것 같다..~


위의 문제중에 5개 이상 풀면 서류와 전화면접 자동 패스이다..
만약에 내가 저기있는 문제를 푼다면..?

1번) X
UVa에 같은 문제가 있다.. 그러나 여전히 못풀고있는 문제..
특별한 알고리즘은 없고 그냥 무식하게 풀면 될듯한데.. 흐미..
숫자를 좌표로 바꾸고.. 만들어지는 도형을 확인해야할것 같은데..

어떤식으로 구현해야할지..

2번) O
이건 왠지 쉬워보인다.. 뭔가 함정이 있는지 모르지만.. 그냥 시뮬레이션 하면 될듯..?

3번) O
0^2 도 포함 가능하므로 DP로 쉽게 해결 가능하다
"dp[n] = n 을 만들 수 있는 제곱수의 최소 개수" 라고 하면..

dp[i] = min(dp[i], dp[i-(j*j)] + 1) (1 <= j <= sqrt(i))
이런식으로 풀면 되겠다.. 근데.. path도 저장해야되네.. -_-;
이렇게 복잡하게(?) 풀어야하는 이유는..
예를들어 input 이 12일때 답은 (9, 1, 1, 1) 이 아닌 (4, 4, 4) 이기 때문이다..
참고: 2007년 ACM-ICPC 서울대회 온라인 예선 E번 문제(링크)와 해설(링크)

4번) O
UVa 11403 문제와 같다.. 구현이 짜증나지만.. 이미 푼 문제..

5번) O
x, y를 고정시키고 z를 binary search해서 찾으면 될것같은데..
그렇게 하면 O(n^2 log n) 이 된다.. 음.. 뭔가 더 좋은 방법이 없나..?

C++ 에 upper_bound()와 lower_bound()를 쓰면 좋을듯..

6번) X
UVa 307 문제인데.. 아주 극악의 accepted ratio를 자랑하는 문제이다..
왠지 DP스러운 문제인데.. 잘 생각이 안나고.. backtracking 말고는 방법이 없는것인가..
UVa에서는 극한의 인풋이 들어오는지 time limit을 pass하는게 여간 힘든게 아니다..
나도 여전히 못풀고있는 문제.. ㅠ_ㅠ

7번) X
이 문제는 멍미.. -_-
edit distance를 활용하면 될것같기도 하고.. 흐미..


켁.. 결국 4문제.. -_-;;



사이냅소프트는 내가 작년에 KLDP에 있는 구인글을 보고 지금 있는 회사를 지원했는데..
그와 비슷한 시기에 역시 KLDP에서 구인글을 보고 알게 된 회사이다..
그러다 알게된 충격적인 사실은..??

야근을 금지(?)하는 회사!!