2022 이화여대 전국 여고생 프로그래밍 경진대회 후기

2022월 9월 17일 토요일에 봤던 대회이다.

자소서 쓰느라 바빠서 후기를 지금 올린다.

자소서 쓰는게 얼마나 바쁘겠어 하면서 대회를 신청한 몇달전의 나를 때리고 싶었다.

 

올해도 온라인으로 진행되었고, 프로그래머스를 이용해 대회를 봤다.

오후 2시부터 4시까지, 2시간동안 6문제를 풀어야하는 대회였다.

1시부터 접속해서 이것저것 셋팅하라던데 별로 할 건 없어서 접속해두고 자소서 썼다;;

 

이번에는 규정이 좀 더 빡세져서 물이나 종이같은 것도 있으면 안됐었다. 이 두개까지 막는 대회는 처음 본 것 같다..

근데 사실 원래 물을 자주 안 마시고, 종이를 많이 쓰는 편도 아니고, 이화여대 대회는 더더욱 안 써도 돼서..괜찮았다.

 

전체적으로 문제를 이해하기 힘들었고, 조건이 명시되지 않았으며, 사람을 쓸데없는 부분에서 귀찮게 하는 대회였다.

---

1번은 냅색을 짜달라는 거였다. 근데 어떤 기준으로 가방을 채우는지 알기 힘들었다. 덕분에 세번 짰다...

무게를 고려하면서 가중치가 가장 높은 것부터 채우라길래 무게 범위 내에서 가중치가 가장 높은 것부터 채우라는 줄 알았다. 2번 예제에서 틀렸다.

문제를 다시 읽고, 여전히 뭔 뜻인지 잘 모르겠어서 그냥 무난한 DP 냅색을 짰다. 또 2번 예제에서 틀렸다.

문제를 다시 또 읽고, 혹시 이 뜻일까 하면서 (가중치/무게)로 정렬해서 짰다. 또 틀리긴 했는데 내가 정렬을 잘못 짰더라. 평소 sort 함수를 이용했었는데 c라서 어떻게 쓰는지 몰라서 그냥 직접 구현했는데 나중에 보니 잘못 구현했더라. 여기에 이미 30분을 꼴아박은 상태여서 이 페이스면 안되겠다 싶어, 다른 문제를 먼저 풀고 나중에 돌아와서 버그잡고 맞았다.

심지어 물건의 가중치와 무게가 모두 입력으로 주어지는 게 아니고 문제에 표로 적혀있어서....하나하나 다 배열에 입력해줬다. 표라서 복사도 안된다...

 

2번도 문제를 읽고 '엥 이게 뭔 소리야' 했다.

결국 어찌어찌 이해해보니 원점과의 거리가 r이면서 x좌표, y좌표가 모두 정수인 점의 개수를 세라는 소리였다.

'훌라후프를 든다'라는 표현이 생소해서 이해하기 힘들었던 것 같다. 그림이라도 하나 있었으면 훨씬 이해가 쉬웠을 것 같다.

r의 범위가 10000인가 그래서 x값을 for로 돌려주고 가능한 y값이 정수인지 확인해줬다. (피타고라스)

r이 작아서 x, y 둘 다 for 돌려도 되긴 할 것 같다...

 

3번은 그냥 DFS를 짜세요라고 써놓은 문제였다.

그런데 그래프의 연결 정보가 입력으로 주어지는게 아니라 문제에 표가 있고, 그 표를 직접 하나하나 치라고 써놨다!! '다음 표를 구현하고, DFS 방문 순서를 출력하시오'였나?? DFS 짜는 것보다 그래프 만드는 게 더 오래걸렸다.

 

4번도 문제를 한 번 잘못 이해했었다. 시간복잡도의 관점에서 문제가 이 뜻일수밖에 없다고 생각하고 문제를 바라본 것이 잘못이었던 것 같다.

1, 2, 3을 적절히 배열해서 합이 n이 되도록 하는 거였는데 n이 범위가 100이었던 것 같다. 경우의 수를 출력하는 게 아니라 정말 어떻게 배열하는지 하나하나 출력하라고 하니 어쩔 수 없이 시간복잡도가 최소 경우의 수만큼 발생하게 된다. 순서만 달라도 다른 경우라서 1 2 3이랑 3 2 1이랑 다른 거다.. 1이랑 2만 쓸 수 있다고 해도 경우의 수가 피보나치 수열을 따라갈텐데... 이게 안 터질리가 없지 않나. 그치만 그냥 짜라니까 짰다. 내가 뭔가 잘못 읽은 걸까?

 

5번은.....슬슬 기억이 가물가물하다. 5번 6번 순서가 헷갈리는데 아마 이게 맞을 것 같다.

일직선 위에 n개의 점이 있고, 이 점 중에 딱 m개를 고를 거다. 이때 골라진 점들 사이의 거리의 최솟값의 최댓값을 구하라는 문제이다.

뭐 당연하게도 파라매트릭 서치로 풀었다. 근데 점들의 위치의 범위를 안 줘서 l, r 범위를 뭘로 해야될지 모르겠는 거다. 그래서 질문했더니(토씨 하나까지 기억은 못하지만 대충 내용은 저렇다)

Q. a의 값의 범위가 어디일까요? (a가 위에서 말한 점의 위치)

A. 문제를 잘 읽어보세요

(아무래도 내 질문을 잘못 이해한 것 같지만 문제는 다시 읽어보고) Q. a의 개수는 주어져있는데 값의 범위는 안 주어져 있어요

A. 원래 범위가 안 주어집니다

Q. 그럼 int범위 안에 들어와도 된다고 가정해도 될까요

A. 재량에 맡기겠다

응애. 그냥 long long 때려박았다.

 

6번은 문자열 하나 주어지고 뒤집어가면서 정렬을 하는데, k번 뒤집었을 때 어떤 상태인지 출력하랬다.

이게 대체 뭔 소리일까?

밑에 '뒤집으면서 정렬하는 과정'에 대한 그림이 있길래 그걸 보면서 대충 끼워맞췄다.

그냥 사전순으로 빠른 순서대로 알파벳을 보면서, 제 위치에 없으면 그 알파벳이 제 위치로 오도록 뒤집으라는 것 같다.

문자열의 길이에 대한 언급도 없었기 때문에 질문을 했다.

Q. 문자열의 길이의 범위는 주어지지 않는건가요

A. 네

....

같은 문자가 있을 때는 앞에걸 먼저 뒤집는건지 뒤에걸 먼저 뒤집는건지도 궁금했지만 질문하지 않기로 했다.

그냥 앞에걸 먼저 뒤집는 걸로 했고, O(n^2)으로 구현했다.

 

1번으로 돌아가서 틀렸던거 바로잡고

시간남아서 문제 쭉 돌면서 제대로 짰나 슥 보고

뭐 그렇게 대충 대회를 끝냈다.

아, 조기퇴실은 불가능하다.

 

1번에 30분 넘게 꼴아박고 표 따라치기도 시전했는데 어째서 6문제 다 풀기까지 2시간도 걸리지 않은 걸까? 채점결과가 안 나오기 때문에 버그가 남아있는 거일수도 있겠다(미심쩍은 몇개는 테스트 해봤지만). 아무튼 2시간은 참 긴 시간인가보다.

---

이 글의 초반부를 쓰면서 자소서 덕분에 글을 조금 잘쓰게 됐나 싶었지만.....

전이랑 똑같은 것 같으면서도 나쁘지 않은 것 같기도?