도대체 koi나 경시대회 문제들은... 어떻게 해야 풀 수 있나요?
글쓴이: galadriel / 작성시간: 목, 2004/05/27 - 6:08오후
www.koi4u.net 이런 사이트에 있는
경시대회급 문제들을 요즘 구경하고 있는데 이런 문제 풀엄두가 잘 안납니다.
이런 문제들은 어떤식으로 풀어야 하나요. 중학교수준 문제까진 어찌어찌
풀긴 푸는데 어떤건 엄두가 안납니다.(뭐랄까 해법이 안떠오른다는..; )
요즘 고등학생들 하는거 보면 신기하기만 하던데 어떻게 공부해야지 경시대회
문제 같은거 잘 풀 수 있나요?? -_-;;
Forums:
제 짧은 식견으로는 컴퓨터 분야 문제는 대부분 문제 풀이에 필수적인 알고
제 짧은 식견으로는 컴퓨터 분야 문제는 대부분 문제 풀이에 필수적인 알고리즘을 쉽게 찾지 못하도록 응용문제 스타일로 바꿔놓는것 같습니다. 몇일에 걸쳐서 푸는 문제도 아니고 당일 즉석에서 풀어야 하는 문제라면 이런 식의 출제 외에는 방법이 없을것 같습니다. 결론은 문제은행 풀이를 통하여 문제에 포함되어 있는 알고리즘을 얼마나 빨리 찾아낼 수 있는지가 관건인것 같습니다. 예전에 중국 대학생 팀에게 물어보니 참가전에 400문제를 풀어봤다고 하더군요. -_-;
별거 없습니다..
거기 있는 문제들은 대부분 예전에.. 대가들이 풀어놓은 문제들을 변형한 문제 들입니다.
제가 장담하는데 Introduction to algorithm / MIT press
제대로 다 익히시면 거기 있는 문제 껌입니다.
그리고 그거 하는 학생들이 천재라서 몇시간 만에 푸는게 아니라 예전에 풀었던 문제를 확인하는 자리 입니다.
KOI 출신도 새로운 유형을 만나면 금방 못풀더군요..
음..
그래프에 대한 지식은 필수였구요..
초반에는 출제유형이 다이나믹 프로그래밍이 주를 이루었었지만..
휴리스틱으로 문제유형이 넘어가더군요..
주로 주어진시간 10초내로 최적의 답을 찾아내는..
휴리스틱의 경우는
유형을 알더라도..
정말 익숙해지지 않으면 풀기 어렵습니다..
그리고 다이나믹 프로그래밍의 경우는
같은문제면 정답자들의 로직이 거의 비슷하지만..
휴리스틱의 경우에는 푸는 사람마다 방법이 천차만별이죠..
그런데 이때 공부했던 내용중..
현재 실제 프로그래밍하면서 써먹는거는..
데이터 스트럭쳐 밖에 없더군요..
머 복잡한거는 라이브러리 구해다가 쓰니까요.. ;; lol
나중에 기회되면 이런거 연구도 해보고 싶긴하지만..
음
엄청난 반복 밖에는 길이 없습니다.
:?
----
블로그 / 위키 / 리눅스 스크린샷 갤러리
그리고 KOI 문제 보다..
ACM-ICPC 문제 를 풀어 보시는것도 좋을거 같네요..
[code:1] 12회 정사각형 채우기 112*112
제한시간이 없다..?? 실제 시험에는 있겠지요... 설마..
한시간쯤 생각하고 2시간동안 풀고.. 넉넉히 3시간 정도는 있어야겠네..
----------------------------------------------------------------------------
저기에서의 제한 시간이란...
저기에서의 제한 시간이란 "연산" 에 걸리는 제한 시간일겁니다.
from bzImage
It's blue paper
이문제 어떻게 풀죠?
일단 가능한 숫자 조합을 찾아야 하는데,
가능한 숫자 조합을 찾는것 부터가 NP 아닙니까?
115*115 = a_1^2 +a_2^2 +a_3^2 + ... 의 해 잖아요,
그럼, A_1 부터 가장 큰수 부터 찾으면, 수퍼 인크리징 셋이 나오는데,
물론 이넘이 넓이는 같지만 사각형에 꼭 맞는다는 보장은 없군요.
5*5 = 4*4 + 3*3 이지만, 4*4 와 3*3의 타일로 5*5를 채울순 없잖아요.
일단 그렇게 가능한 타일 조합을 모두 뽑아내야 하는데,,
이렇게 가능하리라고 여겨지는 타일조합을 찾는것 만을 놓고 보면, Knapsack problem 이네요.
여기까지는 어떻게 115라는 숫자가 그리 큰숫자가 아니라서 적당히 재귀호출로 가능할것 같습니다.
그런데 그 후에 찾은 해가 사각형에 꼭 들어 맞는지 판별해야 하고, 만약에 들아 맞는다면 그 후에 동일한 모양의 타일 갯수를 가지더라도, 채우는 방법의 수는 여러가지가 있을것 같습니다.
ACM-ICPC
수행시간에 제한이 없는건 알고리즘에서 의미가 없지 않을까요. :evil:
차라리
http://acm.uva.es/problemset/
가서 푸셔서 Judge Server에서 Submission 해보시면서 하시는게
정말 실력을 키우는데 좋습니다.
ACM-ICPC, 국제 대학생 프로그래밍 경진대회 라고도 하죠;
-----------
청하가 제안하는 소프트웨어 엔지니어로써 재미있게 사는 법
http://sozu.tistory.com
쩝.. 가만보다보니 만드는데 얼마 안걸릴꺼 같아서 만들어봤는데..
쩝.. 가만보다보니 만드는데 얼마 안걸릴꺼 같아서 만들어봤는데..
112 짜리를 돌리는데는 시간이 꽤걸리는군요..
얼마나 걸리는지는 아직 결과가 안나왔고..
그런데 작은것을돌려보니 이상하게 답이 무조건 1개라는..ㅡ,.ㅡ;;
내가 멀잘못했나..ㅡ,.ㅡ;;
문제는 깔끔한데.. 답이 이상한.. 어쨋거나 급하게 만들어서.. 지금퇴근시간이라..ㅋㅋㅋ
혹시 시스템 좋으신분 함돌려보시길..ㅎㅎ
#define NEMO_SIZE 112 typedef struct { int x; int y; int nstat[NEMO_SIZE]; int narr[NEMO_SIZE][NEMO_SIZE]; } T_NEMO; int Cnt; int main( void ) { T_NEMO tn; memset( &tn, 0, sizeof( T_NEMO )); nemo( tn ); printf( "tot count [%d]\n", Cnt ); return 0; } int nemo( T_NEMO tn ) { int i, x, y, mx, my, mxy; for( x = tn.x; x < NEMO_SIZE; x++ ) for( y = tn.y; y < NEMO_SIZE; y++ ) if( !tn.narr[x][y] ) goto LOOPOUT; LOOPOUT: if( x == NEMO_SIZE && y == NEMO_SIZE ) { nemo_prn( &tn ); Cnt++; return 0; } for( i = y, my = 0; i < NEMO_SIZE; i++, my++ ) if( tn.narr[x][i] ) break; mx = NEMO_SIZE - x; mxy = ( mx < my )? mx : my; for( i = 0; i < mxy; i++ ) { if( tn.nstat[i] ) continue; tn.x = x; tn.y = y; narr_num_write( &tn, i + 1 ); nemo( tn ); } return 0; } int narr_num_write( T_NEMO *ptn, int n ) { int i, j; for( i = ptn->x; i < ptn->x + n; i++ ) for( j = ptn->y; j < ptn->y + n; j++ ) ptn->narr[i][j] = n; ptn->nstat[n-1] = 1; return 0; } int nemo_prn( T_NEMO *ptn ) { int i, j; printf( "====================================================================\n" ); for( i = 0; i < NEMO_SIZE; i++ ) { for( j = 0; j < NEMO_SIZE; j++ ) printf( " %3d", ptn->narr[i][j] ); printf( "\n" ); } printf( "====================================================================\n\n\n" ); return 0; }----------------------------------------------------------------------------
퇴근하면서 돌려놓고 집에와서 보니.. 30분정도 걸렸네요..답은
퇴근하면서 돌려놓고 집에와서 보니.. 30분정도 걸렸네요..
답은 하나밖에 안나오네요..ㅡ,.ㅡ;;
112 112...........
112 112.........
.........................
전부다 112 로 채워진 1개..
아무래도 문제가 이상한것 같습니다... 제가 잘못풀었을리가 없는거 같은데..
^^;;;;;;;;;
----------------------------------------------------------------------------
[quote="ㅡ,.ㅡ;;"]퇴근하면서 돌려놓고 집에와서 보니.. 30분
지금 당장 생각해 봤을 때 n의 크기와 관계없이 답은 '전체를 커버하는 정사각형 하나' 밖에 안 나올 꺼 같은데요.
혹시 n이 얼마든간에 '되는 경우'를 찾으신 분 없나요?
Consider the ravens: for they neither sow nor reap; which neither have storehouse nor barn; and God feedeth them: how much more are ye better than the fowls?
Luke 12:24
자세히 생각해보니 이상한점이 하나 있습니다.
동일한 크기의 정사각형을 한번만 사용하라는 조건은 없네요.
2*2 의 타일에 사각형을 채우는 방법은.
12
34 이렇게, 길이가 1인 타일 4개를 사용하는 방법이 있는건가요?
동일한 크기의 타일을 한번만 사용한다면, 가능한 해는 가장큰 타일 한개를 사용해서 채우는 방법뿐이 없을것 같습니다.
그렇지 않다면, 적당한 크기의 타일을 채운후 1*1의 타일로 빈곳을 채우면 되겠구요..
이런상황에서는 능한 갯수는 상당히 많아서 적당히 랜덤함수 돌려서 채워도 동일한 모양으로 채워진 타일이 나올가능성이 적을것 같네요.
후자라면 너무 쉬운거 같은데 아직 푼사람이 없는게 이상하고, 전자라면.. 음..
gg 입니다. ^^
Re: 자세히 생각해보니 이상한점이 하나 있습니다.
문제에 정확히 나와있지만, '서로 다른 크기의 정사각형' 입니다.
Consider the ravens: for they neither sow nor reap; which neither have storehouse nor barn; and God feedeth them: how much more are ye better than the fowls?
Luke 12:24
으.. 머리 아퍼..^^
으.. 머리 아퍼..^^
[quote="ihavnoid"][quote="ㅡ,.ㅡ;;"]퇴근하면서
님이 볼때도 그럴것 같죠?
저도 결과를 보고서야 다른답이 나올수 없을꺼 같다는생각이 드는군요..
문제가 좀 수정되었으면 좋은문제가 될꺼같네요..
"같은크기의 사각형을 한번만 사용할수 있다"
를 =>
"사각형의 크기가 4이면 사각형을 4개까지 사용할수 있고 5이면 5개까지 사용할수 있다."
로 바꾸면 문제가 좋을꺼 같네요..그리고 112는 좀 크네요.. 100 이하로 하면 시간이 적당할듯..
문제가 이러면 다양한 형태가 발생하겠네요..
----------------------------------------------------------------------------
[quote="ㅡ,.ㅡ;;"]님이 볼때도 그럴것 같죠?저도 결과를
문제의 적당함 여부는 잘 모르겠고요... 저는 이게 '수학적 증명'이 가능한지 좀 생각해 보고 싶습니다... '없다는 증명' 내지는 '반례'를요...
Consider the ravens: for they neither sow nor reap; which neither have storehouse nor barn; and God feedeth them: how much more are ye better than the fowls?
Luke 12:24
기존문제에 있어서는 프로그램을 아무리 돌려봐도 답이 1개만 나오는..
기존문제에 있어서는 프로그램을 아무리 돌려봐도 답이 1개만 나오는..
아무래도 답이 1가지 외엔 없는것으로 보이고
위처럼 문제를 바꿨을때는 크기가 18로 주니까 답이 38개가 나오네요.
#define NEMO_SIZE 18 typedef struct { int x; int y; int nstat[NEMO_SIZE]; int narr[NEMO_SIZE][NEMO_SIZE]; } T_NEMO; int Cnt; int main( void ) { T_NEMO tn; memset( &tn, 0, sizeof( T_NEMO )); nemo( tn, 0 ); printf( "tot count [%d]\n", Cnt ); return 0; } int nemo( T_NEMO tn, int n ) { int i, x, y, mx, my, mxy; narr_num_write( &tn, n ); for( x = tn.x; x < NEMO_SIZE; x++ ) for( y = 0; y < NEMO_SIZE; y++ ) if( !tn.narr[x][y] ) goto LOOPOUT; LOOPOUT: if( x == NEMO_SIZE && y == NEMO_SIZE ) { nemo_prn( &tn ); Cnt++; return 0; } for( i = y, my = 0; i < NEMO_SIZE; i++, my++ ) if( tn.narr[x][i] ) break; mx = NEMO_SIZE - x; mxy = ( mx < my )? mx : my; for( i = 0; i < mxy; i++ ) { if( tn.nstat[i] > i ) continue; tn.x = x; tn.y = y; nemo( tn, i + 1 ); } return 0; } int narr_num_write( T_NEMO *ptn, int n ) { int i, j; for( i = ptn->x; i < ptn->x + n; i++ ) for( j = ptn->y; j < ptn->y + n; j++ ) ptn->narr[i][j] = n; if( n ) ptn->nstat[n-1]++; return 0; } int nemo_prn( T_NEMO *ptn ) { int i, j; printf( "====================================================================\n" ); for( i = 0; i < NEMO_SIZE; i++ ) { for( j = 0; j < NEMO_SIZE; j++ ) printf( " %3d", ptn->narr[i][j] ); printf( "\n" ); } printf( "====================================================================\n\n\n" ); return 0; }----------------------------------------------------------------------------
댓글 달기