교내 알고리즘 대회
GDSC HUFS와 AI교육원에서 우리학교 재학생을 대상으로 교내 알고리즘 대회를 개최했다. 참가부문은 Challenger Track, Begginer Track으로 두 가지가 있었고, 개발언어는 C/C++, Java, Python을 지원한다. 자신있는 C++로 문제를 풀었다.
알고리즘 과목을 수강한 선배들도 참가했겠지만 시상내역을 보고 Challenger Track에 신청했다. 알고리즘 대회만큼은 고등학교때 여러번 참가한 경험이 있기 때문에 자신있었다.
문제
A. K번째 수
입력된 수들을 정렬하는 문제다.
Q(i, j, k)는 i번째부터 j번째까지만을 오름차순 정렬했을 때 k번째의 숫자를 출력하라는 의미다.
algorithm 헤더에 있는 sort() 함수를 이용해 풀었다.
알고리즘 분류: 정렬
B. 네모 땅 영역 나누기
비슷한 문제 (https://www.acmicpc.net/problem/2583)
좌표로 나타나는 그래프를 격자로 변환해 2차원 배열에 저장하고 BFS 알고리즘으로 탐색했다.
격자상의 그래프는 여러번 풀었지만 모눈종이 그래프(좌표로 나타나는 그래프)는 익숙하지 않아서 시간이 좀 걸렸다.
알고리즘 분류: 그래프 이론, BFS
C. 터치 다이얼
왼손 엄지와 오른손 엄지로 스마트폰을 사용한다.
예를 들어 010-1234-5678 이라는 번호를 다이얼로 입력할 때 왼손을 쓰는지 오른손을 쓰는지 그 순서를 출력하는 문제다. (왼손이면 L, 오른손이면 R)
기준은 왼쪽 열의 숫자는 왼손, 오른쪽 열의 숫자는 오른손, 가운데 열은 가까운 거리의 손이다. 만약 거리가 같다면 오른손잡이는 오른손, 왼손잡이는 왼손을 쓴다.
제출후 테스트 케이스 중 틀린 케이스가 있었다. 구현 부분중에 분명 틀린 부분이 있었을텐데 다른 문제에 시간 투자를 해서 어디가 틀린지도 모른체 넘어갔다.
알고리즘 분류: 구현
D. 덕지덕지 게시판
일정한 크기의 게시판에 직사각형의 전단지를 붙일 때 전단지가 붙지 않은 나머지 공간의 넓이를 구하는 문제다. 전단지는 겹칠 수 있다.
이 문제도 B번 문제처럼 격자 형식의 입력이 아니라 좌표 형식의 입력이였기에 조금 혼동이 있었다. 2차원 배열을 생성하고 전단지가 차지하는 부분의 사각형을 임의의 값으로 채워 남은 부분과 구분해 풀었다.
이 문제도 틀린 테스트 케이스 있었는데 C번과 같은 이유로 빠르게 넘어가 고치지 않았다. 아마 범위 밖으로 나가는 경우를 생각안했기 때문인것 같다.
알고리즘 분류: 구현
E. 모든 팰린드롬
주어진 문자열에서 펠린드롬이 나올 수 있는 모든 부분 문자열의 수를 구하는 문제다.
처음에 문제를 읽고 중첩 반복문과 점화식을 세워 한번에 해결하려다가 잘 안흘러가자 멘붕이 왔다. 결국 시간을 엄청 뺏기고 다른 풀이법을 생각했다. 펠린드롬을 판단하는 함수를 구현하고 매번 부분 문자열을 생성할때마다 함수를 호출하는 방법을 선택했다.
몇몇 테스트 케이스에서 시간초과를 만나 부분 점수를 얻었다.
알고리즘 분류: 문자열
F. Black Chain (?)
(못 풀어서 기억이 업서요)
G. 삼각분할법
정n각형에서 삼각분할을 할 때 가장 삼각형간의 거리가 가장 멀 때의 값을 구하는 문제다.
DP문제였던 것 같은데 해결하지 못 했다. 평소 DP관련 문제는 개인적으로 재미도 없고 시간이 오래걸려서 잘 안풀었는데 그게 업보가 됐나보다..
알고리즘 분류: DP
대회 결과
446점으로 8위..
후기
올해 학교에 오고부터 게을러져서 문제 풀이를 덜 했더니 대회 점수를 많이 못 땄다.
그래도 어떤식의 문제들이 나오는지 데이터 쌓았으니 다음 대회에는 순위권에 들어갈 수 있을지도. 내년에 군대 가니까... 3년뒤에 보겠네 미친..
약간 관종끼가 있어서 수상식 때 얼굴 좀 비치고 싶었는데 되게 아쉬운 대회였다. 아직 실력이 부족하다.
그래도 기념품은 받았다 ㅎㅎ
굉장한 터미널을 가지고 있는 에코백과
굉장한 명언이 써진 액정 닦는 천
ㄷㄷ
