2022 대경권 프로그래밍 경진대회 수상 후기

대경권 프로그래밍 대회는 대구/경북 지역 대학생을 대상으로 SW중심대 사업단에서 주최하는 프로그래밍 대회이다.

플랫폼은 프로그래머스를 이용했다.

 

5문제 / 3시간 set으로 주어졌다.

https://programmers.co.kr/competitions/2496

2022 대경권 대학생 프로그래밍 경진대회

 

2018년때부터 개최된걸로 알고있는데 지난 모든 대회 1등은 경북대학교가 가져간걸로 알고있다.

 

문제리뷰

---

1. 단순 구현

계단의 높이를 수열로 주고 최대 높이 K까지 점프할 수 있을때 정상에 가기 위한 계단 수의 최소를 뽑는 문제였다.

문제가 굉장히 심플하고 풀이또한 명확했기 때문에 금방 풀거라 생각하고 많은 생각없이 코드를 짰는데 생각보다 반례가 많아서 까다로웠다. O(N)으로 풀렸던 기억이 난다.

 

2. Map 사용

computer의 개수가 N개 있고, 192.168.0.1 ~ 192.168.0.N 까지의 IP를 할당하는 DHCP 서버가 있을 때 해당 컴퓨터가 최근에 어떤 IP를 사용했는지 저장하는 cache를 map 자료구조로 저장하여 예외처리 하며 구현하는 문제였다.

문제의 지문이 매우 길었지만, 문제 자체는 단순해서 1번보다 시간이 적게걸렸다.

 

3. BFS 응용

백준에서 BFS관련 응용문제를 많이 풀어봤는데, 문제 보자마자 너무 전형적인 BFS응용 문제라는걸 알았다. 

N*M 매트릭스에서 시작지점 -> 끝지점으로 가는 최소 cost였는데 한가지 까다로운 점은 유닛이 90도 회전이 가능하고, 한 자리에서 연속회전이 3회 이상 불가능했던걸로 기억난다. 또한 이 회전에도 cost가 필요해서 실수할 여지가 다분했다.

대충 방문체크 슥슥잘해서 이거또한 생각보다 금방 풀었다.

 

제한시간이 총 3시간 이었는데 1~3문제를 1시간정도에 다 풀었다. 

남은 두 문제를 각각 한시간씩 투자해 풀면 되겠다는 생각으로 4번을 읽었다.

 

4. 유니온 파인드?

문자열이 주어지고 문자열에 해당하는 각 문자에 대한 고유 INDEX를 부여해서 자르고 합치며 나중에 존재하는 모든 set을 출력하는 문제였다. N범위가 생각보다 작아서 단순 브루트포스로도 풀릴줄 알고 모든 문자의 INDEX를 저장하는 배열을 통해 모든 쿼리마다 전부 확인하는 식으로 했는데 테케는 다맞는데 효율성이 다 TL이 떴다. 

각 문자열의 INDEX를 부모로 생각해 유니온 파인드 썼으면 될거같았는데 구현이 생각보다 매우 빡세서 그대로 넘겼다.

 

5. DP?

2*1, 1*2 타일을 해당 N*M 매트릭스에 최대 몇개 끼울 수 있는지 물어보는 문제였다. 단 주어진 매트릭스에 함정이 있어 함정이 있는 곳엔 타일을 놓을 수 없다.

딱봐도 전형적인 DP문제 같았는데 도저히 풀수가 없었다.. DP좀 연습해야 할듯..

그래서 그냥 무지성 백트래킹 돌려서 테케만 다맞고 역시 효율성 다 TL떴다.

시험이 끝나고 백준에서 이거 비슷한 문제를 찾으려고 했는데 찾을 수 없었다.

 

아무튼 1~3 다풀고 4번 20점 5번 30점 맞아서 총 350점으로 종료했다. 다 하고 시간이 좀 남았는데 스코어보드 보니까 1등이어서 약간 마음을 놓은 것 같다.

 

결과

---

최종은 1등으로 마무리 했다. 

참여하는 대학이 별로 없어서 사실 큰 의미는 없지만 그래도 항상 1등은 기분좋다.

 

다음년도 대회에는 참여하지 않을 것 같지만 그때도 우리 학교 학생이 1등해줬으면 좋겠다!