폴리매스

파일을 압축하는 알고리즘에는 '허프만 알고리즘'이라는 것이 있다. 허프만 알고리즘은 많이 나오는 문자는 크기를 줄이고 적게 나오는 문자는 크기를 키우는

알고리즘이다. 예를 들어서 hello everyone은

e: 10 h : 0100 l : 110 n : 0101 o : 111 r : 000 v : 001 y : 011이 되어

010010110110111 1000110000011111010110로 압축된다. (자세한 원리는 생략한다.)

참고로 알파벳은 숫자보다 4배의 용량이 더 필요하다. 위의 경우에선 압축률은 72%정도 된다.

------------------------------------------------여기서부터 문제입니다!!!!------------------------------------------------------

리퍼는 이 알고리즘을 응용해 '리퍼만 알고리즘'을 만들었다.

이 알고리즘은 가장 많이 사용된 문자를 0으로 하고 다음으로 많이 사용된 것을 0, 다음은 1, 다음은 10, 11, 100, 101 ... 이런 식으로 압축을 한다.

같은 횟수만큼 사용된 문자는 먼저 나온 문자가 더 많이 사용됐다고 가정한다.

예를 들어, 리퍼만 알고리즘으로 hello world를 압축하면  h 1번, e 1번, l 3번, o 2번, w 1번, r 1번, d 1번이 사용됬으므로

l: 0, o: 1, h: 10, e: 11, w: 100, r: 101, d: 110이 되어 1011001 10011010110으로 압축된다.

(1) 'hello rriper'을 리퍼만 알고리즘으로 압축하면 어떤 배열이 만들어질까?

(2) (1)에서 만들어진 배열만 있으면 (1)에서 만들어진 배열을 원레대로 만들 수 없다. 원레 문장의 글자 수와 사용된 글자가 주어지면 (1)에서 만들어진 배열을 원레대로 만들 수 있을까? 없다면 반례는 무엇이 있을까? (반례는 하나만 찾아도 된다.)

그리고 여러분!!!! 오해하시는 것 같은데 2번 문제는 "hello rriper"을 원레대로 되돌릴 수 있는지 묻는 문제입니다!