600 - ThreeTeleports
- 500점이 아닌 600점이길래 어려울꺼라 생각했는데, 중간에 경유할수 있는 텔레포트가 3개로 제한되어 있고 가장 빠른길은 텔레포트를 몇개를 거치는지, 어떤 순서로 거치는지, 어디가 시작점이고 어디가 끝점인지 여부가 중요하므로 이를 선택하는 전략을 정하는게 주요한 문제였는데, 모든 경우의 수를 다 계산해도 3*2+3*2*2*2+3*2*2*2*1*2 밖에 안되므로 모든경우를 다 만들어 돌려봄.
- 처음 코딩할때 시작점과 끝점을 어떻게 정하느냐에 따라 경우의수가 나뉘어 진다는것을 생각못해 좀 더 걸림.
- 가장 긴게 32bit int 범위를 넘어간다는것을 예상하지 한번더 고생함.
- 하지만 예제 입출력이 다양하게 잘 되어 있어서 이런 실수들을 다 커버해주심..
- 결과 : 337.28
struct Point
{
int x1, y1, x2, y2;
};
class ThreeTeleports
{
public:
long long result;
int xMe, yMe, xHome, yHome;
Point tele[3];
int used[3];
bool backword[3];
bool allUsed()
{
for(int i = 0; i < 3; i++)
{
if(used[i] == 0) return false;
}
return true;
}
int nextUsedNumber()
{
int maxvalue = 0;
for(int i = 0; i < 3; i++)
{
maxvalue = max(maxvalue, used[i]);
}
return maxvalue+1;
}
long long getDistance(long long x1, long long y1, long long x2, long long y2)
{
return abs(x1-x2)+abs(y1-y2);
}
void setMinimumPath()
{
int prevX = xMe;
int prevY = yMe;
long long nowPath = 0;
for(int i = 1; i <= 3; i++)
{
for(int j = 0; j < 3; j++)
{
if(used[j] == i)
{
nowPath += 10;
if(backword[j] == false)
{
nowPath += getDistance(prevX, prevY, tele[j].x1, tele[j].y1);
prevX = tele[j].x2;
prevY = tele[j].y2;
}
else
{
nowPath += getDistance(prevX, prevY, tele[j].x2, tele[j].y2);
prevX = tele[j].x1;
prevY = tele[j].y1;
}
}
}
}
nowPath += getDistance(prevX, prevY, xHome, yHome);
result = min(result, nowPath);
}
void getMinimumPath()
{
if(allUsed())return;
for(int i = 0; i < 3; i++)
{
if(used[i] == 0)
{
used[i] = nextUsedNumber();
backword[i] = false;
setMinimumPath();
getMinimumPath();
backword[i] = true;
setMinimumPath();
getMinimumPath();
used[i] = 0;
}
}
}
int shortestDistance(int xMe, int yMe, int xHome, int yHome, vector <string> teleports)
{
this->xMe = xMe;
this->yMe = yMe;
this->xHome = xHome;
this->yHome = yHome;
for(int i = 0; i < teleports.size(); i++)
{
used[i] = 0;
sscanf(teleports[i].c_str(), "%d %d %d %d", &tele[i].x1
, &tele[i].y1
, &tele[i].x2
, &tele[i].y2);
}
result = getDistance(xMe, yMe, xHome, yHome);
getMinimumPath();
return (int)result;
}
};
900 - BinaryCards
- 대회를 30분이나 늦게 시작했더니 900문제를 열었을땐 시간이 8분밖에 남지 않아 깨끗이 포기.
- 으아니 근데 이게 Div1 250 이라니!!
- 같은 방 어떤 분이 풀었으나 챌린지 할때 공격을 못함.
- 그분은 Sys fail 뜸.
- 결국 아마 난 시간이 있었어도 쉽게 못 풀었을꺼야 아마.. ㅠㅠ
간략히 느낌점.
_ 발달 이론을 믿자. 난 성장할 수 있다.
_ 집중의 중요성. 고수는 일반인들의 위기 상황에 집중하는 걸 평소에도 할 수 있단다. 같은 시간을 들이더라도 얻을 수 있는게 다른것은 당연함.
_ 자신을 다스리는 법 깨닫기. 안좋은 상황에서도 자신의 기량을 발휘할 수 있어야 한다.
_ 삶과 배움에 대한 깊은 성찰의 중요함. 조지 웨이츠킨은 스스로 생각을 하고 자신을 바라봄으로써 여러가지 배우는 방법을 터득했다.
_ 나만의 소프트존을 만들 수 있는 방법은 무엇일까? 에 대한 고민
_ 나만의 배움의 기술은?
달 가르키는 손가락 보기
_ 대만 나쁜놈들
엉뚱한 생각하기
_ htc가 그래서 안좋군 (...)
왜 재미있게 읽지 못했을까?
_ 자기 이야기를 주욱 늘어 놓는 것을 보면서 거기서 배움의 기술을 유추할 생각을 하지 못함. 책 제목은 배움의 기술이면서 왜 자기자랑만 한담? 하고 생각했었음 -_-;;
_ 문체가 재미있는 문체는 아님.
채스와 태극권에서 세계 정상에 올랐고 현재는 모든 선수 생활을 접고 배움에 대해서 강의 중이시란다. 내가 지금 이렇게 헛되이 하루를 보내는 동안 지구 어딘가에선 멋진 일을 해내고 있는 사람이 있다.
1. 작년에 영어 공부를 한답시고 A 전자사전을 구입했다. 그냥 쓸땐 몰랐는데 몇 주 쓰다보니 몇 가지 문제점이 발견하게 되었다. 개인 학습 프로그램이 진도를 제대로 저장하지 못하는 부분과, 문학 컨텐츠에 들어가 있는 단어 사전에는 같은 단어가 3~5번씩 반복되서 나오는 버그도 있었다. 가장 참기 힘든 버그는 단어장 공부를 하다보면 전자사전이 다운되는 문제였다. 제조사 고객 센터에 문의를 해보았는데 구입한지 너무 오래 지나 교환이나 환불은 불가능 하단다. AS를 보내니 1주일후 돌아왔지만 몇가지 문제는 해결되었으나 몇가지 문제는 그대로 있다. 혹시나 이런 사태를 대비해서 보낼 때 전자사전안에 동영상을 찍어 재현되는 모습을 담아서 보내주기 까지 했는데도 완전한 수정은 이루어 지지 않았다. 다시 AS보내서 1주일 이상 안쓰기도 당시는 아까웠고 그냥 내가 참으면 된다고 생각해 지금까지 그냥 그러려니 하고 쓰고 있다.
2. 지난해 스마트폰의 열풍을 따라 나도 같은 스마트폰으로 교체를 했다. 남들이 다 사는건 별로 내키지 않아서 과일회사의 제품대신에 비슷한 집중을 받으며 KT를 통해 나온 N스마트폰을 구입했다. 그리고 그날 저녁에 발견한 몇가지 문제점. 액정밝기를 어둠게 해놓았을 때 화면의 깜빡임 현상이 있었고, 많은 이들이 같은 증상을 호소하고 있었다. 더군다나 WIFI설정을 해 놓아도 화면이 꺼져 있을때는 몇대로 3G로 바뀌는 버그 때문에 KT에서는 유통시켰다는 이유로 모든 이 폰 고객에게 1G라는 데이터 상품을 나누어주는 서비스를 해야만 했다. 하드웨어적인 단점도 존재하는데, 전원버튼의 설계 문제로 인해 먼지나 이물질의 유입이 심해서 전원버튼이 금방 말을 안듣게 된다. 내가 그 문제로 인해 AS센터를 방문 했을때 같은 문제로 한분이 수리중 이였고, 내가 수리받아 나오는데 전원 버튼 문제로 다른 분이 수리하러 방문했을 정도로 심각한 문제다. 초기 설계 결함으로 리디자인된 보드로 교체를 받았으나 또한번 문제가 발생해 전원 버튼 문제로만 두번 AS받았다. 요즘은 KT문제인지 핸드폰 문제인지 모르겠지만 다른 KT휴대폰 보다 2분이나 느리게 시간이 표시되고 통화중에도 전화가 너무 자주 끊긴다. 다시는 이 제조사의 핸드폰은 구입하지 않을 생각. 약정기간 끊나기 전에 기변을 심각하게 고려하고 있다.
3. 13인치의 작은 노트북 모니터 화면으로 집에서 코딩을 하다가 답답해져서 모니터를 하나 장만했다. 얼마전 O모 사이트에서 행사하는 S모 모니터 27인치를. 4개 이상의 불량화소가 있을 때만 교환 해준다고 되어 있었지만 지금껏 불량화소가 있는 제품을 받아본 적이 없길래 별 걱정안하고 구입했다. 설마 있겠어? 라는 말도 안되는 믿음을 가지고 구입을 했던것인데...... 도착한 제품에는 거의 한 가운데에 초록색 핫픽셀이 하나 있었고 너무나도 밝게 빛나고 있는지라 신경이 쓰였다. 혹시나 하는 마음에 제조사에 문의 해보니 쓰는데 불편하면 교환해 준다길래 애초에 기대를 하지 않았던 지라 매우 고마웠다. 그래 여기까지는... 해피한 지름기일듯 싶지만 교환되어 온 제품이 같은 크기이 하급모델. 단순한 실수였을테니 다시 연락해보니 상급 모델은 제고가 떨어져 물건이 도착하는데로 테스트하고 보내준다고 했고, 3일에 거쳐 받아 세팅을 다 하고 선정리 다 하고 제품의 모니터를 켜보니..
2010년의 첫번재 목표는 영어에 대한 기초 잡기. 영어를 전혀 모르는거나 마찬가지인 실력이였기 때문에 6개월을 할당했는데, 안드로이드 외주도 해보고 ACM-ICPC대회 연습을 위해 문제도 건들여 보고 하느라 영어엔 크게 집중을 하지 못했었다. 막판에 학원에 거주하면서 공부를 했었는데 처음부터 그렇게 했더라면 더 만족스러운 한해가 되었을텐데 ㅠㅠ.. 하지만 동사가 뭐고 목적어가 뭐고 영어 단어의 단어를 다 주어져도 제대로 해석 못하던 말도 안되던 실력에서 이제 그거는 벗어났으니 어느정도 만족한다.
2.
복학해서 최고의 목표는 ACM-ICPC 대회에서 상을 타는 것 이였다. 이전에 장황하게 포스팅 했던 것 처럼 이 대회에서 은상을 수상했다. 대상과 금상은 절대 무리라고 생각했었고 아주 잘되면 은상은 받지 않을까? 라는 생각을 했으니 내가 생각했던 최고의 결과가 나왔던셈인데...
지금 생각해보면 나만 너무 목멨던게 아닌가 하는 생각이 든다. 다른 수상 학교는 학교 공지사항에도 글이 올라오고 학교 홍보자료에도 쓰이던데 우리학부는 전혀 관심도 없고 소모임내에서, 그것도 내가 올리라고 부탁해서 자유게시판에 수상소식을 알리는게 전부일뿐이였다. ㅋ_ㅋ 그래도 가장 관심을 가져준 교수님께서 이번에 학부장 교수님을 하시게 되어 다행인데... 올해는 수상이 가능할까?
3.
우리학교는 졸업작품 전시회를 해야 졸업이 가능한데 역학기 복학을 하는 바람에 졸업작품 전시를 하지 못했다. 졸업작품 주제도 못정해지는 불상사가 발생하는 것은 아닐까 하는 걱정이 있었으나 교수님께서 원하시는 프로젝트가 있어서 그걸 하기로 했는데 잘못 발을 담근건 아닌가 하는 걱정이 들기도 하고 ㅠㅠ 여튼 이건 현재진행형이다.
국내 소프트웨어 회사가 수익을 더 확보하기 위해서, 더 많은 사용자를 늘리기 위해서는 글로벌 소프트웨어 회사를 꿈꿀 수 밖에 없다. 그만큼 국내 시장은 한계가 있고 이미 커질만큼 커졌다. 그래서 오래전부터 많은 회사들이 해외 진출을 노렸으나 성공했다는 이야기는 안타깝게도 아직까지 들어보지 못했다.
실리콘밸리 회사에서 근무한 경험이 있고, 현재는 ABC Tech의 대표이며 카이스트 겸직교수를 맡고 있는 김익환님이 자신이 직접 경험 했거나 수년간의 컨설팅 경험을 바탕으로 씌여진 이 책은 우리나라에서 글로벌 소프트웨어 회사라고 불리울만한 회사가 나오길 바라는 마음을 볼 수 있다.
책의 내용은 새로운것이 없다. 소프트웨어 개발에 관심을 가진 분들이라면 목차만 봐서도 책에 어떤 내용이 들어 있을지 짐작을 충분히 해볼만한 내용이다. 하지만 그렇다고 책의 의미가 없어지는 것은 아니다. 초등학교 도덕교과서에 있는 내용이 기초이고 중요하지만 이를 행하기는 매우 어렵듯이, 모두가 다 알고 있을 법한 내용이긴 하지만 이를 행하는 것은 매우 어렵다.
책을 읽고 나서 다시 한번 제대로된 소프트웨어 공학을 개발 프로세스에 적용해보려는 노력을 해본다면 저자가 책을 쓰는데 들인 수고에 대한 보답을 하는 길이 아닐까 한다. 단, 책에서 소프트웨어 공학의 중요성에 대해서는 얇은 책인데도 못이 박히도록 언급해 주셨지만 그 방법에 대하서는 설명이 안 되어 있으므로 이 부분은 염두해두자. (경우에 따라서는 필요 없는 책이 될수도 있겠다)
이번 학기에 소프트웨어공학이 개설되어 있긴 하나 지금까지 학교 다니면서 전공을 사랑한 덕분에 전공학점을 다 채워 수강과목에 넣지를 않았다. 소프트웨어 공학에 대한 중요성을 잘 모르기 때문이기도 했는데 랩실 옆자리 책장에 있는 소프트웨어 공학 교재를 읽어봐야겠다.
제가 지난 5월부터 활동했던 한빛리더스에서 2기 모집을 시작 한다고 합니다. 해야 할일이 위에 나열되어 있지만, 1기에서 한 일은 주로 "신간도서 읽고 리뷰 및 오탈자 등록"이였고요, "미출간 도서 읽고 미션수행"은 신청자에 한해서만, "설문조사"는 크게 어렵지 않은 내용들 (신간 도서의 제목, 겉표지 선정하기) 이였습니다. "급 미션"이 설문조사였구요.
하지만 이번엔 급미션과 설문조사 내용을 분리해놓은걸 보니 뭔가 다를 듯 싶기도 하네요. 1기의 활동은 한빛리더스 미션 게시판을 통해 엿볼 수 있습니다. "기획의견 및 아이디어"는 자유롭게 게시판에 등록하는 거였지만 피드백도 적고 참여하는 사람도 적었어요. 2기에서는 어떤 개선점이 이루어질진 모르겠습니다. ^.^;;
2006년도 여름방학이 시작하기 전에 학교에 붙어있던 포스터를 통해 "대학생 프로그래밍 경시대회" 라는것을 알게 되었다. 당시 "씨앗" 이라는 학술 소모임을 만들어 운영하고 있었기 때문에 과 게시판에 공지를 했고, 그래서 모인 인원은 12명. 룰 대로 라면 4팀은 나갈 수 있는 인원이였지만 미숙하고 (부끄러운 이야기지만 이때는 로봇 체점사이트의 존재도 몰랐다. 문제는 어찌 구했는데 예제 입출력과 직접 만든 허술한 테스트 케이스에서 제대로 나오면 풀었다고 여기고 연습을 했다) 무리한 스터디 운영으로 인해서 대회 접수 당일에는 3명으로 줄어 들었다. 그 중 한명 마져도 대회에 나가지 않겠다고 하는것을 인원이 부족하면 참가가 안되니 설득하여 등록시켜 대회를 치루었다. 다행히 인터넷 예선에서 쿼터제 덕분에 가까스로 서울대회에 갈 수 있게 되었고, 대회에서는 5시간동안 2문제만 풀고 Honorable Mention에 그쳤다.
2007년도 대회에 나갈 생각을 하고 있었으나 06년 말에 운 좋게 산업기능요원으로 복무를 하게 되어서 군대는 가고 싶지 않았기에 다른거 다 뒤로하고 떠나느라 4년이 지난 이번에 대회를 참가할 수 있었다.
그간 나름대로 연습을 했다. 복학을 해서 이 대회에 다시 참가 했을 때 수상을 할 수 있을만한 실력을 만들고 싶었다. 안타깝지만 우리학교에서 이 대회 준비를 할 만한 사람을 찾기는 어렵기 때문에 혼자 수상 가능할 정도의 실력을 쌓지 않으면 안된다고 생각을 했다. 하지만 어떻게 공부를 해야 하는지 방법을 몰랐고, 회사 다니면서 가끔식 문제를 풀어보았지만 두서없이 이것저것 건들여보기만 할 뿐 실제적인 실력이 나아진다는 느낌이 드는건 별로 없었다.
그러던중 만난 사이트중 하나가 Dovelet이다. 나같은 초보에게 딱 적합한 사이트로 어떤 테스트 케이스에서 오답이 나오는지 친절히 알려주어 다른 사이트에서 겪을 수 있는 답답함을 해소해 주었다. 오답의 경우를 알려주는 것이 문제 풀이 능력 향상에 도움이 안 될 수 있고, 재미를 반감시킬 수 있다는 의견도 있겠지만 어디까지나 초보자에게는 오답케이스를 알려주는 것도 의미 있는 일이라고 생각한다. 난 알고리즘 문제 풀이의 초보자 이기 때문에 쉬운 난이도부터 차근차근 풀어 볼 필요가 있는데 그에 딱 적합한 사이트였다. 여기서 지금까지 500문제가 넘는 문제를 풀었다. 어려운건 건들지 못했으며 내 수준에서 풀 수 있는 문제들만 =_=;;
올 초부터는 마음맞는 04학번 친구들과 같이 Topcoder도 시작했다. 다들 실력은 그리 좋지 않아 블루와 그레이 사이를 오고 갔지만 재미있게 연습했던 기억이 난다. 최근엔 하지 못해 몇달 째 그린으로 남아있지만 -_-;;;
올 여름방학에 있었던 Algospot의 Summer-Camp도 많은 도움이 되었다. 실력있는 분들이 직접 기본 내용에 대해서 강의를 해주었고, 그 내용을 적용하는 문제들을 골라준 덕분에 많은 연습을 할 수 있었는데, 당시 대전에 있었기 때문에 주말마다 먼거리 이동을 했지만 아깝거나 힘들진 않았다(.... 사실 무지 피곤했다ㅠ). 이곳에서 하루 종일 알고리즘 문제를 푸는데에 집중 했던 감옥 체험은 생전 처음해봤다. 구글 코리아의 스낵바가 없었다면 중도 포기를 했을지도.[사랑합니다 스낵바 ㅠㅠ] 이 캠프에서 DP를 풀 때 어떤식으로 사고를 해야 하는지, 기하 문제를 풀기 위해서 무엇을 알고 있어야 하는지, 문제를 어떤식으로 변형하여 생각을 해야 하는지 등에 대해 맛을 볼 수 있었는데, 이번 겨울방학때도 캠프를 열 계획이라고 하니 가능하면 또 참가해볼 생각이다.
학기가 시작하고 어떤 문제를 풀어보며 대회 준비를 해야 하는지 모르는 상황에서, 아주대학교 정현환님이 전화를 해주셔서 아주대 연습에 같이 연습하자 해주신 덕분에 인터넷 예선과 본선 대회 준비를 하는데 방황을 하지 않을 수 있었다. 여기서 연습하면서 가장 기억에 남는 것은 A번 난이도의 문제를 여러개를 순서대로 2~10분안에 해결하는 타임어택 문제풀이. 컨테스트가 이어지는 동안 긴장의 끈을 놓지 않고 재미있게 문제 풀었던 기억이 난다.
하지만 막상 이번 인터넷 예선을 치루고 나서는 지금껏 준비한다고 준비를 했던건데 예상했던것 만큼 문제를 풀지 못해 낙담했다. 우리팀은 쉬운 A번을 내가 잡아서 빨리 끝내 패널티에서 유리해지려고 했었는데, 8번 내리 틀려 버리는 바람에 완전 꼬여버렸다. '비토의 친척들' 이라는 문제를 살짝 변형 한 듯한 B번과 공식을 알고 있던 G번을 풀었지만, 간단한 DP로 보이는 C번도 결국 답을 내지 못했다. HM을 받고 쿼터제로 올라가는 수모는 피할 수 있었으나 노력한거에 비해서 결과가 나오지 않아 썩 기분 좋은 예선이 아니였다.
쏟아지는 과제들과 중간고사 일정, 그리고 졸업작품. 인터넷 예선이 끝나고 갑자기 더 바빠져서 대회 연습을 제대로 못했다. 처음 팀을 만들때 "우리팀은 시험기간에도 연습할꺼다~" 라고 말했는데 막상 시험기간이 되니 그럴 여유가 전혀 없어서 매일 모이기로 한 것도 못 모이게 되었다. 그 와중에도 틈틈이 한두문제씩 풀어보긴 했으나 인터넷 예선의 충격으로 대회에서의 자신감이 높진 못했다.
심지어 대회 당일이 팀원중 하나가 D회사 인적성 검사를 받는 날이랑 겹친다는 사실을 알게 되어서 팀원에게 대회 포기하고 인적성 검사 받으러 가라고 까지 말을 했었다. 대회는 이번이 마지막이라며 지금까지 연습한게 아깝다며 회사는 '다음'에 다시 지원할수 있다고 그 친구는 D회사을 포기하고 대회를 선택해 주었고 대회에 참여하게 되었다. (안타깝게도 D회사에서는 인적성 검사 일정을 조정해 줄 수 없다고 했단다.)
금요일에 마지막 전공 중간고사을 보고 나니 예비소집에 가 있던 팀원에게 연락이 왔다. 팀노트를 예비소집에 미리 제출을 해야 한다며.. 4년전 대회때는 책은 마음껏 가지고 와도 되는거여서 마찬가지로 팀노트를 대회당일 가지고 가면 되는거라 생각을 했던지라 시험끝나고 하려고 작성을 해놓지 않았었다. 고맙게도 예비 소집이 끝나기 전까지 보내주면 대회측에서 프린트를 해준다고 해서 부랴부랴 작성하기 시작. Algospot 캠프때 배웠던 내용들과 그 때 풀었던 문제중에 신선했던 문제들, 다시 풀이를 떠올리는데 오래 걸릴 것 같은 문제들을 추렸다. 캠프에서 기하 관련 라이브러리 정리 해둔 것을 붙여 넣고, 잘 외워지지 않은 알고리즘 몇개를 붙여넣고 보내주었다.
우리팀이 자리잡은 숙소에 저녁늦게 도착하여 간단히 문제를 풀어보려고 시도했다. 이때 본게 union-find 관련문제. 더 많이 보려고 했지만 시험에 대한 여파 때문인지 눈을 뜨고 있기 힘들어 난 먼저 잠을 잤고 눈을 떠보니 대회 당일 아침이였다.
마음을 최대한 편하게 먹었다. 나름대로 연습을 했었지만 인터넷 예선 결과가 그다지 좋지 않았기도 했고, 상을 타려고 생각했다가 실패를 하면 받을 정신적인 상처에 대한 방어 체계 였던듯 하다. HM만 피하고 싶은 생각 뿐이였다. 2006년부터 우리 학교에서 참가를 해 지역대회까지는 항상 나갔지만 언제나 HM을 받았기 때문에 이번엔 순위를 받고 싶은 생각 뿐이였다.
학교이름의 마지막은 Education. 오탈자가 있다는건 대회 끝나고 몇일뒤 알았다. (ㅠㅠ)
대회 시작을 알리는 징이 울리고 이번에도 인터넷 예선과 같이 A번을 내가 잡았다. 마음을 편하게 먹으려고 했고 팀원들에게도 맘편히 쉬엄쉬엄 문제 풀자 라고 까지 말을 했는데, 문제를 읽고 Visual Studio에서 프로젝트를 만드는데 두번이나 CLR Console Application 프로젝트를 만들어 버렸다. 한박자 쉰다음에 제대로 Win32 Console Application 프로젝트를 만들고 코딩을 했는데, 제출하기 전에 떨렸다. 인터넷 예선때 계속 되었던 WA가 떠올라서 (ㅠㅠ). 하지만 이번엔 다행히도 한번에 Yes를 받았다. 맘 편한척 했지만 안도의 한숨을 쉬었다. 이어서 무작정 모든 경우의 수를 돌려 보면 되는 B번도 풀었다.
하지만 이번 대회의 복병이 숨어있었는데 바로 D번. 문제를 읽자마자 어젯밤 자기 전에 보았던 union-find가 떠올랐다. 하늘이 우리를 돕는구나 라는 생각에 정리해둔 팀노트를 보며 작성해서 제출했지만 WA. 다른 방법으로 풀어야 한다는건 전혀 생각을 하지 않고 사소한 실수가 있을꺼란 생각에 몇 번 수정하다가 WA를 몇번 더 받고 다른문제 부터 풀기로 마음 먹었다.
괜히 문제만 길고 어려워 보이지만 사실은 역시 그냥 다 돌려보면 답이 나왔던 C번도 풀어 내고나니 더이상 무엇을 풀어야 할지 감이 오지 않았다. 주위를 둘러보니 초록색 풍선이 많이 있는데 우리는 초록색 풍선을 가지고 있지 않아 D번이 초록색 풍선이라 생각을 했다. 쉬운 문제인데 인터넷 예선때 처럼 또 무언가에 말려 들어 못 풀고 있는거라 생각이 들어서.
마음의 동요가 생길꺼 같아서 여태까지 열어보지 않았던 스탠딩을 보니 왠지 지금의 순위만 지키면 수상 할 수 있을꺼 같은 생각이 들었다. 괜히 급해졌다. 열어보는게 아니였는데 ㅠㅠ.
D번에 대한 알고리즘의 반례를 팀원이 찾아준 덕분에 깨끗하게 union-find를 포기했다. 어떻게든 끼워맞춰 풀려고 했던것을 접근 방법을 바꾸어 방향 그래프를 만들어 모든 도달 할 수 있는 Node를 마킹하는 식으로 풀어 8번만에 간신히 yes를 받았다. 이 때 벌써 대회시간 5시간중 4시간이 넘게 지났다. 평균적으로 한시간에 한문제씩 풀었다. 스탠딩을 보니 D번의 많은 삽질 때문에 4문제 푼 팀중에서 순위가 썩 좋지 않았다. 하지만 한문제를 더 풀면 순위가 10등 이상 상승 할 수 있을 것 같아 보였다. 게다가 D번을 풀어서 우리에게 온 풍선의 색은 여전히 초록색이 아니였다.
2~3번째로 많이 달고 있는 듯이 보이는 초록색이 오지 않아 하나의 희망이 생겼다. "풀지 않은 문제중에서 쉬운 문제가 숨어있다. !" 대회 초반에 보았던 DP를 이용하는 문제 인듯한 E번을 뚫어져라 쳐다 보았다. 솔루션이 떠오르지 않아 기분 전환겸 화장실에 괜히 한번 걸어갔다 오는 중에 자식과 부모간의 조합을 이용한 점화식이 떠올랐다. 바로 코딩하고 제출~ 하였으나 Run Time Error~ 이진트리를 배열로 만든지라, 배열 범위를 체크해보니 트리의 깊이가 가장 깊을 때 자식의 수를 체크하는 부분에서 배열의 범위를 넘어가는 곳에 접근을 하는 바람에 죽은 것이였다. 예외처리 할 생각을 안하고 바로 배열범위만 두배로 늘리고 제출했다. PC^2에 뜨는 결과창이 무서워 하단으로 내리고 저지의 응답을 기다렸다. 작업표시줄에서 반짝이며 메시지가 도착했음을 알리는것을 보고 떨리는 마음으로 클릭해 창을 앞으로 꺼냈다. 보이는건 yes!
나도 모르게 박수치고 자리에서 일어섰다. 이 문제를 푸니 도착한 풍선의 색은 초록색. 그토록 궁금하던 초록색의 문제가 바로 E번 이였다.
우리팀의 제출은 이렇게 끝이 났다. 한문제 더 시도를 해 보았지만 문제를 잘 못 이해 한건지, 이상 없어 보이는 알고리즘으로는 WA만 받았다. 4문제 풀었던 팀들이 얼마나 한문제를 더 푸느냐에 따라, 5문제 이상 푼 팀중에서 학교 중복이 얼마나 많으냐에 따라 우리의 수상 여부가 결정되는 상황이다.
다른 팀들이 문제를 더이상 풀지 않았으면 하는 못된 마음을 먹으며 남은 30여분을 보냈다. 종료를 알리는 종소리를 듣고 애써 외면했던 마음의 짐을 하나 내려 놓았다.
4년전 대회에서는 한시간 정도에 두문제를 풀고 나머지 4시간 동안 아무런 문제도 풀지 못했다. 시간은 길었지만 아무리 시도해도 풀리지 않은 문제 탓에 지루했고 재미도 없었는데, 이번 대회는 대회 내내 골고루 문제를 풀어서 개인적으로 재미있게 대회를 치루었다. 4년전 대회에서는 종료하고 손에 들고 있던 풍선이 팀원 수보다 적은 2개였는데 이번엔 5개였다. 그땐 하나라도 가지고 노는게 아까워 건들지 못했는데 이번엔 낼름 하나를 풀어서 핼륨 가스를 마셔줬다.
대회가 끝나고 보관했던 짐을 찾아서 핸드폰을 켜 acm.kaist.ac.kr 에 접속을 해서 팀명과 학교명이 적혀 있는 스탠딩을 확인했다. 최종 스탠딩은 우리가 E번을 풀기 직전의 스탠딩인듯 보였고 학교를 세어보니 동상은 거의 확실하고, 4문제를 풀었던 아주대, 연세대, 인하대, 시립대 팀이 모두 그대로 라면 은상까지 가능했다.
Algospot의 문자중계를 보니 다른 대학의 상황이 업데이트 되어 있었다. 중계를 통해 연세대와 아주대는 4문제로 종료되었다는 것을 알 수 있었지만 인하대와 시립대의 상황은 나와 있지 않았다. HM만은 피하고 싶었던 처음 마음은 잊고, 이를 확인하니 은상을 받지 않으면 섭섭할꺼 같다는 생각이 들기 시작 -_-; 사람의 마음은 욕심이 끝이 없다니.
기업설명회가 끝나고 특별상 수상이 끝나고, 본대회 수상식 시작!. 동상 부터 시작을 했는데 상황을 몰랐던 시립대와 인하대를 호명했다. 우리팀의 은상이 확정되는 순간이였다. 오늘 아침까지만 해도 상을 받을 수 있게 될지 몰랐다. 정말 꿈에도 몰랐다.
[ 출처 : http://yfrog.com/4pn7mlj ]
맨 왼쪽에 있는게 나 =_=;
긴장을 하지 않고 마음을 편하게 먹을려고 애쓴 덕분이였던거 같다. 작년에 우수한 성적을 냈던 숭실대와 서강대의 멤버들이 휴학을 해 이번대회에 참가하지 않은 덕도 있다. 운이 좋게 풀 수 있는 문제가 나온 덕도 있다. 이렇게 이런저런 이유를 찾아보려 하지만 상을 받았다는게 신기하고 잘 믿겨지지 않는다.
최종 스탠딩이 올라온것을 보니 5문제 푼 팀중에선 가장 패널티가 많다. 학교별 1등만 상을 받을 수 있는 덕분에 우리보다 우수한 많은 다른 대학 팀들은 아무런 상을 받지 못하고 우리에게 까지 상장이 내려왔다. 때문에 어느 누군가에게는 별것 아닌 은상으로 비추어 질 수 있다는것도 안다. 하지만 우리에게는 큰 값어치가 있다.
저녁 리셉션때 대회 디렉터이신 좌경룡 교수님께서 우리팀이 다른 대학의 희망이 되었다고 말씀해 주셨다. 매년 대회를 치루지만 수상하는 팀은 거의 정해져 있다. 비 수상권에 있는 대부분의 대학이 이 대회에 대해서 관심도 없고 지원도 없다. 학교에서 대회를 알고 준비하는 학생도 없고, 어떻게 준비해야 하는지 아는 사람도 별로 없다. 대회의 존재를 알게 되어 준비를 한다 하더라도 4년전에 우리가 그랬던 것 처럼 정보의 빈부 차이와 경험의 유무에서 오는 어쩔 수 없는 갭이 존재한다. 우리학교도 그런 학교 중 하나인 상태에서 4년이 지나서야 수상을 하게 되었다.
난 이번 대회가 마지막이다. 이번의 성과가 학교 후배들에게 좋은 자극이 되어 할 수 있다는 자신감을 가지고 열심히 공부를 하는 계기가 되었으면 하는 바람이다. 좌교수님 말씀대로 타 대학에서도 노력하면 수상이 가능하다는 용기도 가졌으면 하는 마음도 있다. 우리학교에서도 학교나 학부 차원에서 조금 더 관심을 가지고 지원을 해줬으면 하는 바람도 있다. 이번 한번의 반란이 아닌 후배들이 이어서 다음 대회에서도 좋은 성적을 내주었으면 하는 소망도 있다.
대회가 끝난지 3일이 지났는데 아직도 꿈같은 느낌이 든다. 오래전부터 나갈려고 마음에 두었던 대회였고 수상했으면 하는 막연한 소망을 가지고 있었고 이게 이루어졌다. 모든 지나간 것이 그러하듯 꿈같다는 느낌과 약간의 허무감이 남아있다. 어서 이를 떨치고 일상으로 돌아가야지.
지금 이 기분과 생각을 남기고 싶어 다소 장황하게 블로그에 글을 남긴다. 나중에 보면 손발이 오글거릴 글 하나 완성. =_=;;
색 작업을 하면 할수록 이상해지는거 같아서 최소한으로만 했다. 결국 음영도 집어넣지 않음..
동아리 활동은 2005년부터 했는데 어쩐지 회지에 그림을 내는건 이번이 두번째. 지난번에 그렸던것과 마찬가지로 사진을 보고 그렸다.
학술제때 동방에 잠시 놀러갔던 적이 있는데 진성이가 기타를 가지고 놀길래 알려달라고 해서 "로망스"의 앞부분을 배웠다. 휴학한 해성이가 놀러와 그 모습을 사진으로 담아 두었다. 내 핸드폰에. (-_-;) 무엇을 그릴까 고민하다가 핸드폰 속 사진을 보고 이걸 그리기로 마음먹음. ㅎ.ㅎ
