언제나 제자리걸음..

기대 안하고 있다가 다른 사람이 컷이 4문제 정도일 것 같다는 말에 혹시? 했는데..

본선 진출..... ㅋㅋㅋㅋㅋㅋ

가볼까 말까........

(08.11 18:12 수정)

----------------------------------------------------------------------

예선 참가 도중의 스크린샷도 하나도 없고, 끝나고 완전히 다 닫혀버려서 소스코드도 하나도 없어서 그냥 지나가려고 했지만,,

그래도 재밌었던 경험이라? 조금 부끄럽기도 하지만 짤막하게 남겨본다.

알고리즘 같은걸 제대로 배워본 적도, 공부해본 적도 없어서 보통 이런 대회는 자신이 전혀 없고,,

괜히 쳤다가 참혹한 현실의 결과에 우울할 것 같아 응시를 잘 안하지만,

그래도 잉여로운 나날에 변화점이 될 수 있지 않을까 시도해봄.

예선은 원래 오후 1시 ~ 7시였지만, 당일날 멍때리고 있다가 오후 2시부터 시작하였다.

다행히 문제를 보고 싶다는 동아리 선배의 말에, 스크린샷/복붙을 해둔 친구가 있어서 글 쓰기는 조금 편한 듯.

기본 코드를 제외한 문제 원문이 그대로 있지만, 혹시 모르니 다 올리진 않고 적당히 내 기억에따라 작성...

언어는 C++, Java 2가지였고, 원래 Java 를 별로 안좋아할 뿐더러 C++11 이라 Java 보다 불편할 이유가 없었기에 모두 C++ 로 풀었다.

여튼 문제는 총 6문제!

1 -> 2 -> 4 -> 5 -> 3 순으로 풀었는데, (6은 못품)

1 -> 2 -> 4 까지 2시간 정도 걸렸고, 5번을 푸는데 1시간 정도 투자했던 것 같다.

3번도 1시간 정도 투자했던 것 같지만 결국 못풀었고...

6번은 제대로 시도조차 못해봤다.

결론적으로 1, 2, 4, 5번 이렇게 4개 문제를 풀었음.

Code Festival 문제

1. 카카오 프렌즈 컬러링북

2차원 벡터로 표현된 이미지에서 가로세로 같은색끼리 classification 해서 총 몇개 그룹으로 나뉘는? 뭐 그런 문제였다.

그냥 재귀함수 하나 짜서 돌렸다.

2. 보행자 천국

2차원 맵을 주고 좌측 상단에서 우측 상단까지 최단거리로 가는데, 지점마다 제한(방향전환 불가 / 진입불가)이 있고, 총 몇개의 루트가 있는지를 구하는 문제.

얘도 마찬가지로 재귀로 짰는데, 타임아웃이 났다.

벡터를 하나 더 만들어서, 한번 경우의 수가 구해진 경로는 저장을 했더니 통과.

3. 브라이언의 고민

스팸필터를 피하기 위한 규칙적인 광고글을, 원래 문구로 복구시켜보는 문제.

파이썬을 사용하지 않는 문자열 처리를 싫어해서 젤 뒤로 미뤘는데, 결국 마감시간에 쫓겨 제출하지 못했다.

나름 짠다고 짰는데, 경우의 수를 제대로 고려해주지 못했다.

급하게 작성을 하다가 결국 풀지 못한 문제...

중간에 안놀고 1시부터 제때 풀기 시작했으면 풀 수 있지 않았을까 싶어서 아쉬움이 많이 남는다.

4. 4단 고음

어.. 음...

시작음이 1이라고 할때, x3 +1 +1 순서로 높아지는 3단 고음을 구현하는 아이유가,

삼단고음을 중간중간 섞어서 당일 컨디션에 따라 원하는 고음 높이를 구현하기 위한 가지수를 구하는...(뭔소리야)

(생략)

3단 고음은 다음과 같이 적용된다. 1단계에서는 음높이가 세 배가 되며, 2단계와 3단계에서 음높이가 각각 1씩 증가한다. 이를 기록으로 남길 때 * 와 + 기호를 사용하기로 했다. 즉, 3단 고음을 한 번 한 경우는 문자열로 나타내면 다음과 같다.

*++

(생략)

3단 고음의 2단계를 마친 후 3단 고음을 새로 시작한 다음, 나머지 단계를 이어서 하는 경우는 *+*+++

(생략)

최종 음높이: 15

위 문제들과 마찬가지로 그냥 재귀로 역으로 찾으면서 내려갔다.

당연히 그냥 전체 돌면 타임아웃이 나고 중간에서 적당히 빠져나와줘야 하는데...

역계산 하면서 나오는 + 갯수상, 반드시 나와야하는 * 갯수(예를 들어 +가 3개라면 남은 *은 2개, 즉 현재 계산 중인 높이가 3^2 = 9 이상)로 먼저 걸렀는데 또 타임아웃.

그래서 다음으로 최종 음높이를, 밑을 3으로 하는 로그(log(n) / log(3)) 를 취한 값을 구해서, * 이 나올 수 있는 최대 갯수를 구한 다음에 이걸 기준으로 한번 더 걸러주니 정답처리 되었다.

5. 캠핑

쐐기의 좌표를 주고, 외곽선을 제외한 내부에 다른 쐐기가 없는, 대각선으로 쐐기 두개를 고르는 문제였다. (설명을 못하겠네.. ㅈㅅ..)

얘는 그냥 루프로 돌렸지만,, 당연히 그냥 다 돌면 타임아웃...

주어진 쐐기에 대한 좌표들을 x에 대해서, 그 다음 y에 대해서 정렬을 했고, 루프 안에서 인덱스 몇개를 저장하는 방식으로 루프 횟수를 줄이니 8.5초(...)로 통과가 되었다.

6. 신비로운 유적 탐험

트리의 최대 공통부분의 크기를 구하는 문제. 위 예시의 경우 답은 7

바이너리 트리였다면 좀 시도를 해봤을텐데, 시간도 없었고 감이 잘 안와서 시도도 못해본 문제...

1학년때 특허의 claims 항목과 관련하여 비슷한 논문(?)을 봤었는데, 그냥 그 기억만 떠오르고 말았다.

------