분류 전체보기 (124) 썸네일형 리스트형 개코 전쟁 (승리!) MLE의 원인에 대해 다시 싹 찾아봤다 원인은 3가지로 요약된다 1. 정말 할당된 자료의 크기가 너무 크다 2. 재귀의 깊이가 깊다 3. 무한 루프 나의 경우 3번이 원인으로 MLE를 맞았다 다익스트라 알고리즘에서 최단경로의 갱신은 이미 구해놓은 거리보다 작으면 갱신을 해야하는데 나의 경우 작거나 같으면 갱신을 하게 만들어 두었다 하지만 이 부분을 갱신할값 dist[nxt]) continue 이렇게 구현을 해서 두 값이 같은 경우에 대해 미묘한 차이가 발생했고 해결에 어려움이 있었다 다음부터는 표준에 맞게, 잘 구현해야겠다는 생각이 들었다 그래도 이렇게 삽질한번 해서 다양한 과정을 거치면서 이것저것 배웠는데 다음 후기글에서는 이에 대해 기록해야겠다 백준 개코전쟁(진짜 전쟁중, 치열함) 저번 글에서는 거의 뭐 하소연을 쭉 썼는데 오늘은 말하자면 내가 뭘 가지고 있고, 더 필요한건 뭔지 어떻게 챙길지 정도 생각해보는 글이다 일단 나는 catch2라는 테스팅툴이 있고, 코포에서 투어리스트 디버그 코드에 관한 블로그 글이 하나 있다 MLE 맞은 코드라 디버깅 시작부터 막막하긴 한데, 뭐 해봐야지 다른 방도가 없다 그러니 지금부터는 디버그 관련해서 여러 글을 참고하여 개코전쟁을 뜯어보려 한다 미래의 실력 좋은 나는 이렇게 만들어 가는거라 믿는다...😭 p.s. 커피도 쟁여놨다ㅋㅋ 백준 2325 개코전쟁 (진짜 전쟁중) 먼저 이 문제에 대해 AC를 못받았다 하지만 풀이를 생각해 냈고, 그게 올바른 풀이라는 것도 2주에 거쳐 확인했다(기간만 1달...) 심지어 나와 같은 풀이방법으로 구현해낸 다른 사람의 코드로 AC를 받았는데 내 코드만은 MLE가 나오는 상황이다 그러니까 정리하자면 1. 올바르게 문제를 푼 줄 알았는데 틀렸다 2. 잘 못 푼줄알고 2주가까이 검증했다 3. 그런데 다른사람의 풀이를 결국 봤는데 나랑 같았다 4. 그래서 그 분도 잘못풀었겠지 싶어 복붙해서 서밋했는데 AC가 나왔다 5. 멘붕와서 어제부터 잠못자고 유령상태다.... 왜 맞은걸까? 나는 왜 틀린걸까? 무한 반복.... 무한 반복중인 상황을 나름 정리해보자면 1. 메모리 초과를 받았으니 배열 선언부분을 확인해보자! -> 올바르네ㅎㅎ, 똑같음을 확인.. 거듭제곱 이항 계수 이걸 하루 왠종일 할줄은 몰랐다 연말에 하루종일 이항계수 공부하는 인생.... 아무튼 시작 오탈자가 있어 수정한다 우측 상단에 inv(n!)이랑 (n!)^p-2랑 합동이란 뜻이다 dp를 분할정복이라 적어서 수정예정 2020, NOV 21 SSAFY 5기 1차 후기 토요일 10시에 시작해서 딱 1시간 1차 시험이 있었다 어떤 문제가 출제되었는지 구체적으로 적지는 못한다 규정이 그래서 이 부분은 어쩔 수 없다 아무튼 이번 시험은 코로나때문인지는 몰라도 사전 절차가 조금 복잡했다 문자도 바로 전날까지 계속오고 시험 1시간 전에도 날라왔다 덕분에 별 문제없이 사전준비를 할 수 있었다(얼굴이랑 같이 화면 사진찍고 서약서 쓰고 프로그램 깔고 등등) 시험은 2가지 유형으로 치러졌다 1차시에는 무슨 아이큐테스트 같은 문제들이 쭉 나왔는데 온라인 시험 특성상 시간이 빡빡했다 아마 삼성 인적성인가? 그 무슨 시험 있는데 그거 그대로 가져와서 시간 빡빡하게 준 것 같은 느낌이었다 2차시에는 정올 서술형같은 문제들이 출제되었다(정보 올림피아드) 정올 문제를 모른다면, 그냥 문과 6평 .. 2020 google kick start round f 벌써 대회 일주일 지났는데 이제야 후기를 올린다ㅋㅋ 대회는 총 4문제가 나왔고 내 성적은 2솔이다 1,2번 풀고 3,4번을 못풀었다 대화시간을 착각해서 1시간 늦게 시작했는데(총 3시간짜리 대회) 대략 1시간반? 1시간 10분정도 만에 2문제 풀어서 해볼만 하다 싶었더니, 3번째 문제가 극악이었다. 에디토리얼에서는 dp를 쓰거나 미니맥스를 써서 풀 수 있다고 했는데 아마 대회 대상이 학생들이다 보니, 이런 알고리즘도 알아둬라 이런 의미로 출제한 문제 같았다. 아무튼 느낀점 최근 손코딩을 얼핏얼핏 배우고 있는데, 특히 그리디나 구현 등의 문제에서 상당한 이점이 있어 이번 대회에서 많은 도움을 받았다. 끝 templates for cp cp를 할 때 있는 그대로의 쌩코드*를 갖다 박는 사람은 없다 나도 처음 시작 할 때는 매크로같은거 하나도 안쓰고 했는데, 결국 자료형 크기나 여러 제약때문에 이것 저것 갖다 쓰게되고, 이렇게 코드가 길어지다 보면 매크로나 온갖 잡기술을 쓸 수 밖에 없다. 솔직히 풀만한 문제인데 이런 잡기술 몰라서 레이팅 낮아지면 억한 심정 생겨서 금방금방 배우게 된다.(내가 그랬다😂) 그러니 이 글은 그냥 참고만하고, 실제 대회에 참가해서 배우는 것을 강추한다. *적당히 i/o관련 코드만 쓰는 분들도 있습니다. 수정 예정 9/1 수정본 앞으로 이 글은 항상 술마시고 수정할 예정이다 항상 술먹고 문제를 풀었는데, 술만 마시면 멀쩡한곳을 최적화 한답시고 때려부수고 있기를 매번 반복중이라 그만 하기로 했다 아무튼 본격적으로.. atcoder abc 177 a,b번은 빠르게 풀어냈는데 c번에서 망해버린 라운드 난 c번을 기하적으로 생각 못했고, 다만 수리적으로 전체의 제곱에서 a^2+b^2+...요걸 빼주고 /2를 해주면 된다는 사실을 알아냈다 하지만 이 로직을 그대로 구현하면 오버플로우가 발생한다 실제로 앳코더 오피셜에서 선생님이 이렇게 풀면 long long 형에서는 오버플로우라고 설명하고 있다 오피셜에서는 기하적으로 좀 더 생각해서, 합이 계단처럼 증가하는 모습을 확인할 수 있고, 그 형태를 구현해 냈다 참고로 저스티스후이님은 오버플로우 없이 1번 로직으로 구현하셨다. 대단하다..... dp로 구현한 애도 있다 다들 구현력이 어마어마하다. Edu CodeForces R96 D2 Review 기왕 문제 푸는거 어차피 목표가 3솔이니까 C부터 풀자! 라는 생각으로 했다 망한 라운드다... 서밋한거 다 WA떠서 0솔 마무리 레이팅 망했다 아무튼 리뷰 시작 Proc A. 단순한 구현문제였는데 윌리엄은 진짜 배열을 construct했다. 아직도 그게 뭔지 잘 모르겠다. 아무튼 쉽게 AC받은 문제라 그냥 스킵했다. Proc B. 대회중에는 보지도 못한 문제이다. 난이도는 C번보다 어렵다는 여론이다. SecondThread에 의하면 이 문제는 일명 Knapsack algorithm이라고 한다. 칼이랑 도끼중에 싼걸 먼저 다 털고 나머지를 털면 된다.(그리디) Proc. C 이거 진짜 대회때는 못 풀고, 아침에 금방 풀어서 너무 억울했다. 솔루션 배열을 전부 1로 채우고, 타겟배열의 값이 0인곳만 찾아서.. 이전 1 ··· 9 10 11 12 13 다음
