10개의 댓글이 있습니다.
-
-
wookayin -
2000짜리 지역변수는 스택이 터진것 같은데 윈도우 환경에서는 런타임 에러나도 PC^2가 이거 잘 못잡고 그대로 답이 틀리니까 WA로 결과를 보내주..는 현상이 가끔 있습니다-_-; 그래서 전역변수가 짱임.
저도 좀 제 이야기를 달아보자면.. SEERC 2008은 작년에 팀연습하면서 돌았던 셋인데 못 푼 문제도 있었고 코딩 연습도 할 겸 돌아봤습니다. 그러나 오래동안 코딩을 게을리한 탓인지 무지하게 말려들었드랬죠..
YONGJA 팀이니까(?) 어려운 B, H 이런것 부터 잡아요. 사실 해법만 알면 간단한 문젠데 코딩에서 망해요. Integer Overflow, 배열 초기화, 오타(-_-), 판단미스 등등 온갖 실수를 다하면서 NO를 받아요. 그렇게 B, G, H랑을 맞고 나서는 D번 문제를 건드려봅니다. 이건 그래프 문제인데 적절한 DFS가 필요한 문제에요. 그런데 N이 10만인데, DFS를 짜면 스택이 터져요. 도대체 10만짜리 그래프에서 뎁스가 몇만짜리인 그래프를 입력에 넣으면 어쩌라는건지 ..
예전에 팀연습할 때에도 해법을 금방 떠올렸음에도 불구하고 런타임 에러가 자꾸 나서 패배했던 기억이 오버랩되면서.. 오기가 생겨요. 어셈블리 코딩하는 기분으로 Non-recursive로 바꿔요(아놔ㅠㅠ). 전역에 스택잡고 goto를 소스코드에 문질러요. 정말로 코드가 지저분해요(공개되기에 좀 부끄럽습니다만 ㅡ,.ㅡ) 10만짜리 넣어보니 스택은 안터지는데 TLE가 자꾸 날아옵니다. 이제는 시간제한이 빡빡한가보다 하고 최적화를 해요(STL이랑 좀 비효율적인 부분이 많아서..) 그러나 너무 빤짝빤짝 눈이부셔 NONONONONO..
자꾸 틀려서 접고 C랑 F를 봅니다. 왜 자꾸 TLE지!?!? 코드를 들여다봅니다. 사실은 재귀 함수가 둘이었는데 하나는 맞게 해놓고 다른 하나는 local variable restore를 안했[.....] 이 실수를 해결하니 맞더군요. 무지많이 틀리고, 삽질하는 게 인생의 참된 진리에요(?).
머리가 너무 뜨끈뜨끈해서 좀 쉬다가.. 가장 쉬웠던 세 문제 A, E, I를 풀까 말까 하다가 코딩해놓고 299분에 동시 서브밋하기로 마음을 먹어요. 드디어 기다리던 299분이 되고, 적절한 컨트롤로 광속제출을 해요. 리베님이 "욱 치팅임?"이라고 물어보지만 용자는 애드립을 쳐요. 그런데! 그런데! A가 틀렸어 (..) 네, 그렇게 해서 A만 빼고 다 풀었습니다 orz 나중에 뭐 틀렸나 보니 한 줄을 빼먹었어요 OTL.
실수 없이 말끔하게 코딩하는 것이 얼마나 중요한지를 새삼스럽게 느낄 수 있었습니다. 모의고사를 준비해주신 리베님께 다시한번 감사의 말씀을 드립니다. 문제별로 간단한 해법에 대하여 블로그에 한두줄 포스팅한게 있으니 혹시 해법이 궁금하신 분들은 참고하셔도 좋을 것 같습니다.
14년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
VOCList
팀 xhaism으로 참가한 xhae입니당. 후기에는 문제 풀이에 대한 다소의 스포일링이 있습니다 ㅠㅠ
당일 아침에 학교에서 시험이 있었습니다. 시험보고 매점에서 점심거리사서 후다닥 돌아오니 한 5분쯤 지났더라고요. 부랴부랴 문제뽑고 pc2를 켰습니다.
A번을 보니 어 이건 그 그거... 유명한 문제인 LIS(Longest Increasing Sequence) 구하기네요. N(1<=N<=100000)개의 원소가 들어올 때 LIS의 길이를 출력하는 문제였습니다. LIS를 구하는 유명한 방법으로 O(N^2)의 동적계획법이 있기는 하지만, 이 문제에서는 N이 최대 10만까지 들어오기에 O(N^2)의 프로그램은 TLE가 날 것 같았습니다. 사실 LIS를 구하는 알고리즘중에는 O(NlgN)의 복잡도를 가지는 알고리즘이 몇몇 있습니다. 예전에 그런 복잡도를 가지는 방법이 있다는 말만 듣고 우와 대단해 하면서 그냥 넘어갔었는데-...
검색했습니다 ㄲㄲ 구글신 찬양! 이해하고 나서도 직접 코딩하면서 내가 맞게 짜는건지... 어떤지 고민이 되긴 했지만 일단 예제가 나오길래 제출. YES! 이 문제에서 WA(Wrong Answer)받기 시작했으면 아주 돌돌 말렸을텐데 운이 좋았습니다 ㅠ_ㅠ
오픈북(...)으로 A를 풀고 나서 B를 읽다... 영 모르겠어서 스탠딩을 켜보니 E가 풀리고 있었습니다. 바로 E를 읽어보니 simple polygon이 입력될 때 해당 도형의 넓이를 구하는 문제. 신발끈 공식에 대입해서 바로 풀었습니다. 그리고 스탠딩을 다시 보니 아까 그멤버 그대로 I를 풀고 계시길래... I는 2차원 함수의 최대값을 가지는 x의 값을 구하는 문제였습니다. 근해공식 슥슥 대입해서 해결. 그리고 나서 스탠딩을 보니 이제 정체 상태입니다. 1등하신 용자 wook님께서 B를 푸셨길래 다시 B로 돌아가서 읽어봤는데 해법이 잘 떠오르지 않습니다. 조금 생각해보다 일단 다른 문제도 다 읽자고 이때 전 문제를 다 읽었습니다. 그리고 이때 버린 B는 결국 끝까지 못풀었네욤[...] F는 아직도 문제가 깔끔하게 이해가지 않는 부분이 있고, 대충 보아하니 H가 뭔가 수식으로 유도하면 간지나게 풀릴 것 같습니다. 행렬이 주어지고 행렬식을 구하는 문제였는데, 뭔가 곱셈을 하다보면 딱딱 떨어져 나갈거같은 느낌이라... 행렬을 이래저래 바꿔봤는데 잘 안되네요. 그 후에 G를 잡아봤더니 범위가 10^14승입니다. 저는 왠지 범위큰 문제들만 보면 일단 손이 후덜덜 떨리는게 ㅠㅠ 역시 좀 해보다 모르겠어서 패스.
그 후에 C를 다시 읽었는데, 문제를 조금 다르게 읽었습니다. 문제에서 선거를 한다길래 선거의 당선자는 당연히 한명이 있는 거라고 생각했습니다. 당선자가 반드시 한명으로 고정되면 문제가 그리디로 바뀌게 됩니다(아마도). 그래서 열심히 그리디로 짜보니 예제 하나가 계속 안나와서... 예제 설명을 읽어보니 당선자가 없을수도, 여러명일 수도 있더라고요. 솔직히 이시점에서 울고싶었음 ㅠㅠㅜㅜㅠㅠ 그런데 문제를 다시 이해하고 생각해보니 어 이건 2-SAT 문제네. 근데 나는 2-SAT을 풀 줄 모르잖아. 난 아마..
되더라고요. 구글짱... 대회도중에 어떤 알고리즘으로 해결하는지 다 검색하고[...] 코딩을 시작했습니다. 예제가 나와서 섭밋! WA! 또섭밋! WA! 알고보니 내가 섭밋하고 있던건 위에서 그리디로 짠 소스였을 뿐이고! 난 그리디 소스랑 2-SAT 소스 파일명이 비슷했을 뿐이고!
다시 제대로 된 소스를 제출했더니 또 WA! 조금 의심가는 부분이 있어서 고쳐봤는데 또 WA! 그래 막 읽어보고 처음으로 짜본 알고리즘이 맞을 턱이 엇ㅂ지...하면서도 왜 틀렸는지는 모르겠고 반쯤 포기하는 심정으로 Live archive 온라인 저지에 가서 제출을 해봤습니다. 어 근데 Accepted... 이게 무어 ㅠㅠㅠㅠㅠ 이건 LIBe님이 날 해코지하려는 음모가 틀림없다면서 막 저지 다시 봐달라고 때쓰고 난리가 아녔슴다 :( 직접 프로그램 돌려봐주시더니 마지막 하나가 안나온다고... 프로그램이 죽는다고 하시길래 이거 저거 고쳐보다 3번의 WA를 더 받고 나서야 원인을 찾았습니다. 함수 내부에서 원소 2000개짜리 boolean 배열을 하나 선언했는데 이 배열을 전역변수로 뺀 다음에 제출하니 맞더라고요. 그런데 재귀호출도 아니었고 스택 크기를 넘진 않을텐데 흠... 컴맹이라 왜 내부에서 선언했을때 프로그램이 죽었는지는 잘 모르겠습니다 ㅠㅠ 하여간 왠만큼 큰 변수는 전역변수로 선언하는 편이 안전한 것 같네요. 특히 윈도우 베이스에서 채점하는 서울대회는요...
이렇게 안드로메다를 다녀오니 218분에 YES 하나 추가. 이 전문제가 72분에 해결된걸 보면 한 두시간 반정도를 이문제 저문제보며 헤매고 있었네요 ㄲㄲ 곧 스탠딩은 동결되고 적당히 남은 문제를 추리다 대회 끝나갈때쯤 G를 해결. 그리고 대회가 끝났습니다 ㅠㅠ
개인적으로 뭔가 대회 도중에 공부를 많이 하게 된(...) 대회였네요. 몰랐던 알고리즘도 그렇고 프로그램 죽는 문제도 그렇고 좋은 연습이 되었습니다 :)
14년 전