다음 네 문제는 컴퓨터로 알고리즘을 작성하여 풀 수 있는 문제입니다.
(프로그래밍 언어는 C++ 또는 C를 사용하셔야 합니다.)
네 문제 모두 단답형이므로, 풀이 과정이나 설명을 적을 필요는 없고,
답을 적고 작성한 프로그램 소스 파일을 첨부해서 보내주시면 됩니다.
또, 넥슨에서 본 문제 메일을 발송한 시점에서 만 이틀이 지나기 전에
귀하의 답이 넥슨에 도착하지 않으면 불합격이며 보내주신 소스 파일은 채용 과정에서 검토됩니다.
문제의 설명과 예는 답을 구하기에 충분하므로, 추가적인 질문은 받지 않습니다.
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 이다.
<문제>
다음과 같이 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 = ____
4번
<설명>
다음과 같은 배열(array)이 있다고 가정할 때
A = { 30, 1, 18, 2, 5, 10, 15, 9, 5, 25, 5 }
B = { 2, 4, 11, 5, 24, 18, 8, 4, 13, 18 }
:*: 는
"A 배열과 B 배열에 동시에 존재하는 수의 갯수를 구하는 연산" 이고
|*| 는
"A 배열과 B 배열에 동시에 존재하는 수의 집합(set)의 크기를 구하는 연산"이라고 정의하면
A :*: B = 9 이고 ( A' = { 18, 2, 5, 5, 5 }, B' = { 2, 5, 18, 18 } )
A |*| B = 3 이다. ( { 2, 5, 18 } )
문제
첨부된 Problem4Data.exe를 실행하면 work folder에 array1.dat, array2.dat 파일이
생성되며 각 파일의 크기는 4GByte 이다. ( 실행 전 디스크 용량 체크 필요 )
각 파일은 64 bit unsigned integer 값이 Little Endian 형식으로 차례로 기록되어 있으며 해당 array 내용은 다음과 같다.
array1.dat =
{
0b9cba234dfa382b, 39a3a0d4d852f190, b9327f793917ff50, 1616a4aabd698224
...
fa042ea941e23e5f, 3b822f8e29debd79, 10c3149ac586d931, ff7010cd11748990
}
array2.dat =
{
c801c1d4fa7aa667, 354950b8ddf236d5, b2cd486f07bf5480, 87bd78f1a50ce1e8
...
751cb8fad5eb894e, b0e9830fdf5b86d4, fc0a9158f62abfc6, 4f178f9413158f9c
}
array1 = A, array2 = B 라고 했을 때
A :*: B 값과
A |*| B 값을 구하여라.
4번 답 : A :*: B 값 __________ , A |*| B 값 __________
생각보다 쉽네요. 입사 문제가 이정도라니...;;;
언제 시간 나면 한번 고민해보아야겠네요.
(4번은 첨부파일을 구하지 못했습니다. 랜덤 찍는 프로그램 돌려서 해도 무방할 듯 합니다.)
)로 이루어진 한 줄이다. 각각의 실수는 세 점의 좌표를 나타낸다. 원의 지름은 1,000,000을 넘지 않으며 입력은 EOF로 끝난다.
의 값은 3.141592653589793이다.
댓글을 달아 주세요