넥슨 입사문제가 인터넷에 있어서 살짝 봤더니 전부 알고리즘 문제네.
대충 한 번 훓어보고 내린 결론은 다음과 같다.
1번 문제는 여러 가지 접근 방법이 있겠지만, 가장 간단한 방법은 해싱을 이용하여 one scan으로 풀 수 있을 듯하고, 메모리를 아껴야 한다면, two scan으로 풀 수 있을 것같다.
2번 문제는 Dynamic Programming 방법으로 풀어야 할 듯한데, 어떤 식으로 problem formulation을 해야 할까?
3번 문제는 bucket size 16인 optimal histogram을 구하는 문제로 풀면 되겠다. 연구실에서 2004년 vldb에 publish한 "REHIST: Relative Error Histogram Construction Algorithms" 논문을 참조하면 될 듯.
4번 문제는 컬럼 두 개를 조인하는 알고리즘이 필요하다. 4기가의 데이타가 전부 메모리에 올라가지 않으니, 가장 간단하게는 Nested-Loop Join을 쓰면 되고, 좀 더 효율적으로 하려면 Block Nested-Loop Join이나 External Sorting을 수행한 후에 Sort-Merge Join을 쓰면 될 것같다.
2번 문제의 경우에는 좀 더 생각을 해 봐야겠는데, 바빠서 우선은 이정도로~ ㅋㅋ 혹시 관심 생기면 풀어보고 코멘트 남겨 주시길...
댓글을 달아 주세요
올 초에 한국 학생 한명 들어왔는 데 넥슨에서 병특했다더만. 얘기 들어 보니 룰루 랄라 하면서 동아리 하는 그런 분위기에서 게임만들고 하면서 지내다 온 듯하네. (기계과 출신) 누군 열라 여기 저기 돌아다니면서 뺑이치고 오고 누군 그런 환경에서 딩가딩가 하다 오고 흐...
ㅋㅋ 세상은 언제나, 누구에게나 불공평한 것이지. 피라미드의 정점에는 누가 있을까?
근데, 겜 회사는 힘들지 않나? 열라 빡세게 일한다는 얘기를 얼핏 들었던거 같은데...ㅡ.ㅡ;;
걔는 동아리 분위기였다고 했던 거 같은데 뭐 팀마다 틀리지 않으까. 그래도 빡시긴 빡쌨겠지.
하긴... 빡신 동아리였었나보지 뭐~