넥슨 입사 문제

출처를 알수 업지만 과거에 어디선가 구했던 '넥슨 입사문제'

이게 진짠지 신빙성은 없지만. 문제가 어려워서 한번 같이 풀어보고 싶어 올려봅니다.

***

아래 4문제를 풀어,12월09일(금) 오후 2시까지

nexojs@nexon.co.kr로 전달 해주시면 됩니다.

기한내 미 제출시, 자동으로 탈락처리 됩니다.

========================== 과제물================================================

 

다음 네 문제는 컴퓨터로 알고리즘을 작성하여 풀 수 있는 문제입니다.

(프로그래밍 언어는 C++ 또는 C를 사용하셔야 합니다.)

네 문제 모두 단답형이므로, 풀이 과정이나 설명을 적을 필요는 없고,

답을 적고 작성한 프로그램 소스 파일을 첨부해서 보내주시면 됩니다.

또, 넥슨에서 본 문제 메일을 발송한 시점에서 만 이틀이 지나기 전에

귀하의 답이 넥슨에 도착하지 않으면 불합격이며 보내주신 소스 파일은 채용 과정에서 검토됩니다.

 

문제의 설명과 예는 답을 구하기에 충분하므로, 추가적인 질문은 받지 않습니다.

 

 

1번 설명

 

어떤 자연수 n이 있을 때, d(n)을 n의 각 자릿수 숫자들과 n 자신을 더한 숫자라고 정의하자.
예를 들어 d(91) = 9 + 1 + 91 = 101
이 때, n을 d(n)의 제네레이터(generator)라고 한다. 위의 예에서 91은 101의 제네레이터이다.
어떤 숫자들은 하나 이상의 제네레이터를 가지고 있는데, 101의 제네레이터는 91 뿐 아니라 100도 있다.
그런데 반대로, 제네레이터가 없는 숫자들도 있으며, 이런 숫자를 인도의 수학자 Kaprekar가

셀프 넘버(self-number)라 이름 붙였다.
예를 들어 1,3,5,7,9,20,31 은 셀프 넘버 들이다.

 

 

 

 

1번 문제

 

1 이상이고 5000 보다 작은 모든 셀프 넘버들의 합을 구하라.

 

1번 답 : ________

 

 

 

 

2번 설명

 

가로 세로의 네모 칸들로 이루어진 방에 총잡이들이 있다고 하자.
총잡이들은 가로 혹은 세로 방향으로 다른 총잡이가 보이면 총격전을 벌여 한 쪽만 살아 남는다.
칸 중에는 벽으로 막힌 곳이 있어서 총잡이들이 벽 너머로는 볼 수 없으며, 대각선 방향도 볼 수 없게 되어 있다.

 

■: 벽
□: 빈 칸
♂: 총잡이

 

에를 들어, 다음과 같은 가로 세로 네 칸 씩으로 된 방이 있다고 하면,

 

■■■□
□□□□
□■□□
■■■□

 

총잡이 세 명을 다음과 같이 배치해볼 수 있을 것이다.

 

■■■□
□□□♂
♂■♂□
■■■□

 

가로 혹은 세로 방향에서 다른 총잡이에 노출되는 총잡이는 어느 한쪽이라도 죽게 되므로,
다음과 같은 배치는 할 수 없다.

 

■■■□
□♂□♂
□■□□
■■■□

 

위와 같이 생긴 방에 최대한 많은 총잡이를 배치하는 경우, 최대 네 명까지 가능하며,
네 명을 배치하는 경우의 수는 다음과 같은 두 가지 방법이 존재한다.

 

■■■♂
□♂□□
♂■♂□
■■■□

 

 

■■■□
□♂□□
♂■♂□
■■■♂

 

또 한가지 예로, 만약 벽이 전혀 없는 가로 세로 네 칸씩으로 된 방이 있다면,

최대 네 명의 총잡이를 24 가지의 방법으로 배치할 수 있을 것이다.

 

 

 

2번 문제

 

다음과 같이 생긴 가로 세로 여덟 칸씩으로 된 방에는 최대 몇 명의 총잡이를 배치할 수 있으며,

그 경우, 몇 가지 방법으로 배치할 수 있겠는가?

 

□■□■□■□■
□□□□□■□□
■□■□□■□■
□□□□□□□□
□□□■□□□□
□□□□□■□■
□■□□□□□□
□□□□■□■□

 

2번 답 : 최대 ____ 명, ____ 가지.

 

 

 

3번 설명

 

RLE(Run Length Encoding)란, 임의의 수열을 (반복 수, 숫자)의 쌍으로 된 수열로 만드는 부호화 방법이다.
예를 들어 다음과 같은 열 개의 숫자로 된 수열이 있다고 할 때,

9, 9, 9, 5, 7, 7, 7, 7, 7, 7

RLE를 이용하여 다음과 같이 여섯 개의 숫자로 부호화할 수 있다.

(3,9), (1,5), (6,7)

 

해석하면, 9가 세 개 있고, 그 다음에 5가 한 개, 그 다음에 7이 여섯 개 나오는 수열이라는 뜻이다.

이 때, (원래 수열의 갯수) / (부호화 수열의 갯수) 를 압축률이라 하며, 위의 경우에서 압축률은 10 / 6 = 1.666 이다.
이렇게 부호화된 값은 쉽게 원래 값으로 복원할 수 있음을 알 수 있을 것이다.

 

그런데, 원래 값으로 되돌리는 것을 보장하지 않는 RLE 방법을 '손실 RLE'라 하자.
이 경우는 복원했을 때 오차가 생기게 되는데, 원래 수열과의 RMSE (Root Mean Square Error) 를 오차로서 정의한다.
크기가 n인 A 수열과 B 수열 사이의 RMSE는 다음과 같이 계산한다

 

RMSE(A,B) = sqrt( ( (A1-B1)^2 + (A2-B2)^2 + ... + (An-Bn)^2 ) / n)

 

'손실 RLE' 방법은 다양하게 존재하므로, 같은 수열이라도 다양하게 '손실 RLE' 부호화 할 수 있는데,

 

예를 들어, 위와 같은 수열의 경우
(10,9) 혹은, (10, 7) 혹은 (3, 9), (7, 7) 등으로 '손실 RLE' 부호화할 수 있을 것이다.

 

만약 (10,9) 으로 부호화했다면, 압축률은 5 이며, RMSE는 2 이다.
(10,7) 로 부호화했다면, 압축률은 5 이며, RMSE는 1.26 이다.
(3,9), (7,7) 로 부호화했다면, 압축률은 2.5 이며, RMSE는 0.63 이다.

 

 

 

3번 문제

 

다음과 같이 128개의 정수로 된 수열이 있을 때,

 

49, 49, 50, 52, 49, 47, 47, 46, 44, 42, 42, 38, 38, 38, 36, 34,
33, 33, 33, 32, 34, 38, 42, 41, 42, 42, 40, 41, 40, 38, 38, 37,
37, 39, 41, 40, 40, 40, 40, 42, 45, 47, 47, 46, 46, 46, 47, 47,
47, 47, 46, 44, 43, 39, 36, 34, 34, 32, 30, 29, 30, 31, 31, 31,
30, 28, 25, 23, 24, 22, 22, 25, 25, 27, 31, 33, 35, 37, 38, 39,
39, 40, 40, 41, 40, 40, 40, 40, 39, 38, 37, 35, 35, 34, 33, 32,
31, 30, 30, 29, 29, 28, 27, 27, 28, 27, 25, 26, 0, 0, 90, 90,
90, 90, 90, 91, 90, 88, 87, 84, 80, 78, 83, 89, 91, 90, 89, 92

 

오차를 가능한 한, 작게 억제하면서 32개의 정수(압축률 4)로 압축하는

자신만의 '손실 RLE' 알고리듬을 만들고, 그 알고리듬에 의한 부호화 결과 수열과 RMSE를 적어라.
(RMSE 가 1.8 미만이면 정답으로 간주하며, RMSE가 1.6보다 작을 수록 가산점 있음.)

 

주의; 답은 정확히 32개의 정수로 나와야 하며 32개보다 적거나 많으면 오답으로 처리 됩니다.

오답 예 1)

( 8, 49), ( 3, 44), ( 5, 38), ( 5, 33), ( 1, 38), ( 8, 42), ( 6, 38), ( 4, 40),

( 8, 45), ( 4, 47), ( 1, 43), ( 1, 39), ( 3, 36), ( 2, 32), ( 7, 29), ( 3, 25),

( 3, 22), ( 2, 25), ( 2, 31), ( 2, 35), ( 5, 38), ( 7, 41), ( 3, 37), ( 3, 34),

( 5, 31), ( 7, 28), ( 2, 0 ), ( 9, 90), ( 1, 84), ( 2, 80), ( 1, 83), ( 5, 89)

-> 64개의 정수로 오답

오답 예 2)

(8, 47), (7, 38), (6, 33), (8, 42), (11, 40), (14, 47), (12, 31), (8, 24)

(20, 39), (8,30), (6, 26), (2, 0), (9, 90), (1, 84), (8, 83)

-> 30개의 정수로 오답

 

3번 답

 

(__, __), (__, __), (__, __), (__, __), (__, __), (__, __), (__, __), (__, __),
(__, __), (__, __), (__, __), (__, __), (__, __), (__, __), (__, __), (__, __)

 

RMSE = ____