Generator

알고리즘 문제 푸는것을 포기한 것이 아니다. 

 

 

잘 순항중이다. 하지만, 난이도 높은 문제에 시간을 투자하는 것도 중요하고 좋아하지만 하나 풀때마다 정리하기에 시간이 많이들고 쉬운 문제는 정리하기에 오버헤드가 크다고 생각한다. 또한, 지금은 개발 분야 공부를 하고 있기에 온라인 대회에 나왔던 쉬운 문제들을 하루에 하나씩 풀면서 살아가고 있다. 그 와중에 숙제 처럼 남겨 뒀던 문제가 있다.

 

https://www.acmicpc.net/problem/8481

8481번: Generator

후배가 푸는 걸 보고 문제 설명도 듣고 재밌겠다 싶어서 언젠가 시간이 나면 꼭 풀어봐야지 했는데 그게 가장 바쁘다고 생각하는 지금이 될지는 몰랐다. 공부와 코딩으로 머리가 멈췄을때 이 문제를 꾸준히 조금씩 하다 어제 해결 하였기 때문이다.

 

문제 설명

문제에 있는 링크에 들어가면 0~10 총 11개의 파일을 다운 받을 수 있다. 우리는 11개의 파일을 분석하여 10만 바이트 안에 해당 파일의 내용을 출력하는 프로그램을 작성해야한다.

 

문제 해결

당연히 이 문제는 퍼즐(?)형 문제이기 때문에 각 파일에 대한 설명을 하지는 않을 것이다. 하지만, 해결 하게 되는 과정을 적으려고 한다. 먼저 나는 문제를 풀기 앞서 세 가지 프로그램을 만들었다.

1. 정해프로그램

2. 연구프로그램 

3. 비교 프로그램

 

우선 1번 정해 프로그램은 2번 연구 프로그램에서 분석하여 해답에 해당하는 내용이 나오면 정해 프로그램으로 옮겼다. 그리고 정해 프로그램에서는 해답에 해당하는 부분을 파일로써 출력한다.

f=open('./generator/gen0.out','w')
f.write('ONTAK 2010')
f.close()

 

0번 문제의 경우에는 위와 같을 것이다. 그렇게 하여 만들어진 프로그램을 3번 프로그램에서 원본 프로그램과 비교한다. 비교 프로그램 내부에는 두가지 함수가 있는데 한줄씩 읽고 비교하는 함수랑, 전체를 비교하는 함수 두가지가 있다. 이를 분리한 이유는 파일중 한줄로 이루어진 파일과 여러줄로 이루어진 파일이 있는데, generator 문제를 시도 하는 사람이라면 알겠지만 이 문제에는 뭔가가 있기 때문이다. 

 

팁으로는 파이썬에서 압축을 활용하는 것이다. 이 문제의 풀이는 정말 다양할 것 같은데 나 같은 경우에는 문자열 압축을 어느정도 많이 사용하였다. 마지막에 파일비교로 잘 해놓고 이걸 print로 고치는 작업을 했는데 파일비교는 개행이 안들어가는데 print는 강제로 개행이 들어가서 이걸 못찾아서 엄청 헤맸다.

후기

하나하나 풀면서 재미도 있었고 힘들고 귀찮은것도 많았지만 막상 풀리니까 기분은 좋았다. 난이도가 저정도인가? 싶기도 한데 구현 시간이나 생각해보면 잘 모르겠긴하다. 비슷한 문제로 20000바이트 챌린지가 있는데 그 문제도 역시 시간만 있으면 도전해보고 싶기도하다. 이 문제의 경우에 압축을 최대한 활용하여 아슬아슬하게 풀긴했는데 편법이라고 생각된다. 물론 시간 투자를 하면 어떻게든 방법은 있을 것 같다. 여담으로 studio code에 저 파일 띄워서 보고 있으면 주변에서 이상한눈으로 보고있는듯한 느낌이 든다. 맞힌 분들 코드들 보면 byte수가 극한으로 작은 분들도 계시는데 존경스럽다.