요근래 제 자신의 머릿속 Processing을 나름대로 Tracing해보는 연습을 하고 있습니다. 문제를 푸는 과정을 동영상으로 찍어보기도 하고, 문제를 풀면서 소감도 바로바로 적어보려고 합니다. 아래의 글은 제가 오늘 블로그에 적었던 SRM 489에 있었던 일... 에 대한 글입니다. 요즘 블로그 새로 옮기고 꽃단장 좀 하고있는데 오셔서 rss도 업어가 주시고 분노로 가득찬 악플이라도 좀 달아주시면 힘내서 열심히 뻘글 쓰도록 하겠습니다.
Easy 문제를 열고 뭐랄까 정신이 혼미한 상태로 30분쯤 보냈던 것 같습니다. 문제가 이해되지 않았던 것은 아닌데 뭐랄까 혼자 문제를 너무 복잡하게 읽었던 것이 아닌가 싶습니다. 이때 당시의 제 머릿속을 추적해보면...
집어넣는 token의 수가 1개일 때, 2개일 때, 3개일 때, ... n개일 때의 경우로 확장해서 dynamic programming을 해 보자! => 공식이 잘 안나와서 꼬임
집어넣는 token의 종류가 1가지일 때, 2가지일 때, 3가지일 때, ... 의 경우로 확장해서 dynamic programming을 해 보자! => 마찬가지로 공식이 잘 안나와서 꼬임...
!@$!@#!@#@!!!!
결국 Easy 문제를 Dynamic Programming으로 풀려는 시도를 계속 하다보니 머릿속이 계속해서 deadlock에 걸린듯한 접근만을 반복적으로 시도하게 되었고, 결과적으로 대회시간 30분을 그냥 허비한 셈이 되었습니다.
Med
대회 시간이 40분을 남겨놓은 시점에서 이대로 가다간 하나도 못풀고 0점으로 대회를 마칠것 같은 불길한 느낌이 들어서 Med를 열었습니다. Med 또한 문제 자체는 쉽게 이해되는 문제였습니다. 다만 주사위를 오른쪽으로 굴릴 때와 뒤쪽으로 굴릴 때에 대한 머릿속 시뮬레이션이 약간 혼란스러웠습니다. 종이에 힘겹게 경우의 수를 그려가면서(주사위가 놓여있을 때 윗면은 U, 아랫면은 D, 하는 식으로 UpDownLeftRightFrontBack의 6개 상태를 놓고 위로 옮길때와 오른쪽으로 옮길 때의 Transition을 미리 적어놓는 식입니다) Cell에다가 들어올 수 있는 모든 경우의 수를 나열해 보았습니다.
제 | 목 | 의 | 공 | 간 |
| - | - | - | - |
U | LR | ... | ... | ... |
F | FLR | ... | ... | ... |
D | LR | - | ... | ... |
B | BR | FB | ... | ... |
U | R | D | L | U |
(...은 적다 포기했음)
아오 존나쪼금 테이블로 적어봤는데 왜이리 어렵죠? ㅠㅠ 하여튼 종이에 저렇게 쓰다 보니까 경우의 수가 그렇게 많지 못하겠다는 생각이 들었습니다. (4,1) 위치나 (1,4)위치의 경우 U가 되기 때문에 그 뒤로는 법칙에 따라 이동할 수 없는 구간이 되어버리니까요.
게다가 Easy에서 입은 내상이 워낙 컸던지라 일단 점화식을 보자는 마음에 다돌리기를 해서 50x50의 구간에 대해 U로 도착하는 경우의 수를 뽑아보았습니다. 결과는...
하여튼 x=4 혹은 y=4에 해당하는 구간만 빼면 대부분 2로 가득차있는 아름다운 테이블이 저를 기다리고 있더군요. 그래서 그냥 저 x=4 혹은 y=4에 해당하는 부분만 if 문으로 처리해주고 나머지는 적당히 범위 체크해서 2를 반환하게 해서 그럭저럭 점수를 받을 수 있었습니다.
어쨌든 Med의 경우에는 나름 머리를 잘 썼다면 쉽게 풀 수 있는 문제를 안전빵으로 푸느라고 먼저 손으로 테이블을 적어보고, 또 작은 범위에 대해 계산해보는 코드를 짜느라 시간을 많이 소모한 감이 있습니다. 실제 상위권 랭커들은 10분만에 쓱싹 몇줄짜리 코드만 짜고 잘도 맞추더군요.
Hard
대회 시간중에는 읽어볼 시간도 없었는데, 좀 막막한 문제이긴 합니다. 한동안 고민해보면서 풀이를 생각해볼 생각입니다.
결론
Easy는 아예 풀지도 못했고 Med의 경우에도 너무나도 쉬운 문제가 나와서(GCJ 경험이 좀 있는 사람이라면 아무 아이디어도 없을 때 작은 데이터에 대해 Brute-Force 알고리즘으로 문제를 먼저 풀어보고 올바른 답을 유추하는 방식의 문제풀이 접근 경험이 있을 겁니다) 개인적으로 참 아쉬운 대회였다는 느낌입니다.
Neon
요근래 제 자신의 머릿속 Processing을 나름대로 Tracing해보는 연습을 하고 있습니다. 문제를 푸는 과정을 동영상으로 찍어보기도 하고, 문제를 풀면서 소감도 바로바로 적어보려고 합니다. 아래의 글은 제가 오늘 블로그에 적었던 SRM 489에 있었던 일... 에 대한 글입니다. 요즘 블로그 새로 옮기고 꽃단장 좀 하고있는데 오셔서 rss도 업어가 주시고 분노로 가득찬 악플이라도 좀 달아주시면 힘내서 열심히 뻘글 쓰도록 하겠습니다.
Table이 블로그에서는 이쁘게 나왔는데 여기선 그저 그렇네요... 둘다 Markdown 문법인데 아쉽습니다.
오늘의 대회
Easy
Easy 문제를 열고 뭐랄까 정신이 혼미한 상태로 30분쯤 보냈던 것 같습니다. 문제가 이해되지 않았던 것은 아닌데 뭐랄까 혼자 문제를 너무 복잡하게 읽었던 것이 아닌가 싶습니다. 이때 당시의 제 머릿속을 추적해보면...
결국 Easy 문제를 Dynamic Programming으로 풀려는 시도를 계속 하다보니 머릿속이 계속해서 deadlock에 걸린듯한 접근만을 반복적으로 시도하게 되었고, 결과적으로 대회시간 30분을 그냥 허비한 셈이 되었습니다.
Med
대회 시간이 40분을 남겨놓은 시점에서 이대로 가다간 하나도 못풀고 0점으로 대회를 마칠것 같은 불길한 느낌이 들어서 Med를 열었습니다. Med 또한 문제 자체는 쉽게 이해되는 문제였습니다. 다만 주사위를 오른쪽으로 굴릴 때와 뒤쪽으로 굴릴 때에 대한 머릿속 시뮬레이션이 약간 혼란스러웠습니다. 종이에 힘겹게 경우의 수를 그려가면서(주사위가 놓여있을 때 윗면은 U, 아랫면은 D, 하는 식으로 UpDownLeftRightFrontBack의 6개 상태를 놓고 위로 옮길때와 오른쪽으로 옮길 때의 Transition을 미리 적어놓는 식입니다) Cell에다가 들어올 수 있는 모든 경우의 수를 나열해 보았습니다.
제 | 목 | 의 | 공 | 간 |
(...은 적다 포기했음)
아오 존나쪼금 테이블로 적어봤는데 왜이리 어렵죠? ㅠㅠ 하여튼 종이에 저렇게 쓰다 보니까 경우의 수가 그렇게 많지 못하겠다는 생각이 들었습니다. (4,1) 위치나 (1,4)위치의 경우 U가 되기 때문에 그 뒤로는 법칙에 따라 이동할 수 없는 구간이 되어버리니까요.
게다가 Easy에서 입은 내상이 워낙 컸던지라 일단 점화식을 보자는 마음에 다돌리기를 해서 50x50의 구간에 대해 U로 도착하는 경우의 수를 뽑아보았습니다. 결과는...
쓸 | 모 | 없 | 는 | 제 | 목 |
(?에 어느 숫자가 들어가는지 기억이 안남)
하여튼 x=4 혹은 y=4에 해당하는 구간만 빼면 대부분 2로 가득차있는 아름다운 테이블이 저를 기다리고 있더군요. 그래서 그냥 저 x=4 혹은 y=4에 해당하는 부분만 if 문으로 처리해주고 나머지는 적당히 범위 체크해서 2를 반환하게 해서 그럭저럭 점수를 받을 수 있었습니다.
어쨌든 Med의 경우에는 나름 머리를 잘 썼다면 쉽게 풀 수 있는 문제를 안전빵으로 푸느라고 먼저 손으로 테이블을 적어보고, 또 작은 범위에 대해 계산해보는 코드를 짜느라 시간을 많이 소모한 감이 있습니다. 실제 상위권 랭커들은 10분만에 쓱싹 몇줄짜리 코드만 짜고 잘도 맞추더군요.
Hard
대회 시간중에는 읽어볼 시간도 없었는데, 좀 막막한 문제이긴 합니다. 한동안 고민해보면서 풀이를 생각해볼 생각입니다.
결론
Easy는 아예 풀지도 못했고 Med의 경우에도 너무나도 쉬운 문제가 나와서(GCJ 경험이 좀 있는 사람이라면 아무 아이디어도 없을 때 작은 데이터에 대해 Brute-Force 알고리즘으로 문제를 먼저 풀어보고 올바른 답을 유추하는 방식의 문제풀이 접근 경험이 있을 겁니다) 개인적으로 참 아쉬운 대회였다는 느낌입니다.
13년 전