친구 둘(향기, 타잔)군과 함께 제 2회 자바 알고리즘 경진대회(이하 JAC)에 참가했다. 평소 공모전이나 대회같은 걸 별로 즐기지(?) 않는 나로서는 새로운 경험이었으나, 역시 세상은 넓고 배울 것은 많다는 교훈을 새삼스레 깨닫게 된 하루가 아니였나 싶다. 한마디로 지금 이러고 있을 때가 아니다... 정도랄까.
어쨋든 하루를 끝마치고 모처럼의 신선했던 경험을 정리해보고, 혹 도움이 될까 싶어 기출되었던 문제를 소개해보고자 한다.


앞에 자바가 붙어있긴 하지만, 딱히 자바의 고수가 아니어도 전혀 상관없다. 알고리즘 대회인만큼 코딩실력보다는 문제를 해석하고 재구성, 풀이해내는 능력이 중요하다. 총 6문제가 출제되었는데, 모두 문제 자체는 금방 이해할 수 있을 정도로 직관적이었다. 보통 어려운 문제라고 하면 문제 자체를 이해하기가 어려운 경우가 꽤 많은데, 사실 그런 경우보다는 이해하기는 엄청 쉬운, 막상 풀려고 하면 손대 못대는 그런 문제들이 더 어려운 법이다. 가장 쉬운 예로 "26의 증명"이나 그 유명한 "페르마의 정리"를 들 수 있겠지.

※ 26의 증명 : 제곱수(25)와 세제곱수(27)의 사이에 존재하는 정수는 26이 유일하다는 것.

다만 시간이 3시간으로 제한되기 때문에, 단순계산으로 문제당 30분정도밖에 시간이 없다. 팀당 인원이 3명이므로 평소 이런 류의 대회에 대비한 훈련이 잘 되어 있고 분업이 원할하다면 그리 빡빡한 시간은 아닐지 모르나, 3:3 스타팀플에서도 노성큰레어, 1겟 드라군, 2스타 레이스따위의 빌드를 남발하는 우리에게 그딴게 있을리 없다. 대충대충 얼기설기 유야무야 나눠서 코딩을 하다보니 시간이 부족하더라;;


흑백의 그리드 형태를 띈 체스판 위에, 한 면에만 빨간 점이 있는, 그리고 빨간 점이 위로 향한 주사위가 2개 주어진다. 하나의 주사위를 굴려서 다른 주사위의 위치에 도달하기까지 최단경로를 구하는 문제. 물론 빨간 점은 위로 와야 한다. 중간에 통과가 불가능한, 길막용 주사위가 최대 3개 존재한다.

처음에는 체스판 색상이 같아야만 가능하다고 언뜻 생각했으나 다시 생각하니 옆으로도 굴릴 수 있으니 상관이 없더라. 내가 푼 문제가 아니라 자세히는 모르지만, 시간나면 한번쯤 생각해볼만한 문제인듯. 상식적으로는 어떠한 경우라도 가능할 것 같긴 한데...


연산 자체보다, parsing이 핵심이었던 문제;; 개인적으로는 도대체 왜 알고리즘 대회에 나왔는지 이해가 안되는 문제. 짜증나서 문제를 자세히 읽어보지도 않았고, 다시 알게 된다하더라도 다시 접하고 싶지는 않은 문제.

특정한 형식으로 2 by 2 Matrix형태를 띈 복소수 행렬이 2개 주어지는데 이를 연산하는 것이 문제였다. 자세한 내용은 기억이 나지 않아서... (딱히 기억하고 싶지도 않고;;)


100 by 100의 그리드 형태의 땅이 주어지는데, 여기에 랜덤하게 눈사람이 배치가 되어 있다. (정확한 그리드의 크기와 눈사람의 수는 기억이 나지 않으므로 패스)

문제는 내부에 눈사람을 포함하지 않는 최대면적의 사각형을 찾아내는 것이다. 단, 경계면에 포함된 눈사람은 문제가 되지 않으며, 경계면 1라인을 제외한 내부에만 포함되지 않으면 된다. 입출력 양식은...확실히 기억나지 않지만, 입력은 가로 알파벳, 세로 숫자의 조합(ex. A8, B2) 으로 눈사람의 위치가 주어지면, 사각형의 좌표를 나타내는 식이었던 것으로 기억한다.


0보다 크고 백만보다 작은 임의의 수가 주어졌을 때, 이것을 4개의 소수의 합으로 나타낼 수 있느냐 하는 것이다.
예를 들어 입력값이 17이 주어졌다면, 2 + 3 + 5 + 7 의 형태로 나타낼 수 있을 것이다.
답이 복수라 할지라도 하나만 출력하면 되고, 불가능할 경우 Impossible 메시지를 출력하면 된다.

입력값으로 주어진 수를 대충 2개로 쪼갠 다음, 각각의 수를 소수의 합으로 나타내어질 수 있는지를 체크해서 리턴하는 방식으로 했다. 불가능하면 다르게 쪼개는 방식으로 반복하도록. 다만 이 방법은 숫자가 커지면 소수인지 체크하는 부분에서 시간이 기하급수적으로 늘어나기 때문에 몇가지 잔재주를 피워놓긴 했는데, 뭐 딱히 상관은 없겠지.


제목 그대로 풍선 터뜨리기 게임이다. N by M의 Matrix 형태를 띈 7가지 무지개 색상을 나타내는 알파벳(rgbyopi)이 bubble.input 이라는 파일에 저장되어 있다. (※ 여기서 N와 M의 최대값은 20이다.)

헥사와 비슷한 방식으로, 가로세로 2개 이상 같은 알파벳이 연속되어 있을 경우 풍선이 터지는데, 터진 풍선의 자리는 오른쪽의 풍선이 당겨지는 방식이다. (아래 위로는 풍선이 이동하지 않는다)

예를 들어 입력값이, 아래와 같다고 하자.

일단 풍선이 터지면 다음과 같은 형태가 된다. (ㆍ은 빈곳을 의미한다)
여기서 빈 곳을 오른쪽에 있는 풍선들이 매우면, 다음과 같은 형태가 된다.

이러한 식으로 계속해서 반복해서, 더이상 풍선이 터지지 않을때까지 진행과정을 출력해주는 프로그램이다.
크게 어렵지 않지만, 역시 성능 문제가 중요하지 않을까 생각되는 문제.


ACM에 나왔던 문제라는데...원래 시답잖은 문제풀이나 좋아하지 그런데랑은 담을 쌓고 사는 나로서는 들어본적 없는 문제였다.

7자리의 숫자가 주어지는데, 인접한 두 수의 합과 차(큰수에서 작은수를 뺀것) 모두가, 인접한 수를 제외한 나머지 5개의 숫자와 중복되지 않도록 숫자를 이동시키는 문제이다. 역시 불가능한 경우 불가능 메시지를 출력하고, 답이 복수라 할지라도 아무거나 하나만 출력하면 OK.

예를 들어 입력값이 7392519 라고 한다면, 2와 5의 합은 7이므로, 조건에 부합하지 않는다. brute-force식으로 모든 경우의 수를 나열한 다음 모든 연산을 하면 쉽게 풀리긴 하는데, 성능 대결이기 때문에 뭔가 잔대가리를 굴려야 할 것 같은데, 향기군이 어떻게 풀었는지는 모르겠다. 나중에 코드를 달라고 해봐야지...

결과는 뭐...오랜만에 동아리 친구들이랑 맛난거 먹고 재미도 있었고 게임도 했고...뭐. 보람찬 경험이었다라는 정도로만;;