목록오늘의 코딩 (386)
one day left
원하는 시간에 잠에 푹 빠져들 수 있었으면 좋겠다. 불이 꺼진 방에 누워있으면 온갖 생각에 머리가 복잡해지고 가슴이 두근거려 도통 잠에 들기가 힘들다. 요즈음엔 잠에 들기까지 보통 한시간은 걸리는 듯하다. 몸은 피곤한 상태에서도.. 그놈의 Codeforces Round때문에 리듬이 망가져서 그런가.. ㅜㅜ최근 기상시간에 대한 자신감이 붙어서 어제 새벽알바가 있는데도 패기를 부렸더니 완전히 망했다.. 역시 나자신은 그렇게 믿을만한 놈이 못돼
의 정확한 구현을 하면서 떠올린 방법으로 ASC 47 - A. 을 풀어냈다. angle을 sweeping하는 건 항상 cyclic한 부분에서 precision의 문제가 있어서 구현을 망설였는데, 이렇게 아예 normalize를 하지 않고, segment들을 반복하여 펼쳐놓은 상태로 계산을 하면 훨씬 직관적인 코딩이 가능하다. 위와같은 그림에서 각 시작/끝점에 대한 처리는 하되, 답에 대한 계산을 2번째 occurrence, 즉 초록색 영역에서 해주면 된다. 이 문제의 경우에는, 1. 시작점인 경우 현재까지 센 drone수를 넣어주고, 2. 끝점인 경우 현재 deque의 모든 요소를 partial sum으로 더한 후 시작점에서의 drone수*size를 빼주며 3. drone인 경우 drone수를 +1해주는..
는 이전 ASC문제보다 (구현이) 조금 더 쉬운 angle sweeping 문제였다. 사실 이런 문제를 에서도 다룬 적 있는데, 원으로 생각하기보다, 0-2PI를 잘라서 cyclic segment로 이해해버리는 게 더 편하다. 사실 이 문제를 푸는 방법은 여러가지겠지만, scott_wu의 방식이 제일 직관적이고 간단한 구현으로 연결된다. 문제를 좀 더 간단한 문제로 바꾸어내는 능력이 진짜 중요해..BOJ에서 콘테스트 하나를 도주랑 같이 참여했음. 인터넷 예선 대비였는데, 내 구현력의 한계를 다시금 실감^_ㅠ 효율적 구현이 너무 늦어..연습을 빡세게 하려고 CF #319를 준비하고 있었으나 시간이 되고 페이지에 들어가보니 등록이 안돼있었다ㅡㅡ 이런 멍청한.. 그래서 콘테스트 하나 날림 ㅜㅜ 30번 rate..
오늘 논설에서 Boolean Algebra를 배운 기념으로..금요일 새벽, 그러니까 내일 밤에는 Codeforces Round가 있다. SNUTOC전에 마지막으로 해볼 수 있는 Contest인듯하니 꼭 참가해야겠다.ㅠㅠ 현재 멘탈로는 rating이 떨어지지만 않아도 다행.. 이겠지만
Euler's Formula를 planar graph에서 vertex, edge, face의 관계로만 알고 있었는데 본래는 더 대단한 걸 증명했던 거구나.. polyhedron을 평면상에 투사해서 밑면을 제외하면, 평면상의 그래프로 v-e-f'=1이 성립한다. 결국 polyhedron상에서는 v-e-f=2. 해당 상수는 도형의 종류에 따라 특정된다.어휴 가 도저히 코딩이 안된다ㅡ_ㅡ어떡하지 정말.. 꼭 다음에 또 코딩해 봐야지.그저 내 맥에어에 가 없길래 homebrew로 gcc4.9 인스톨을 시켰는데 30분째 돌아가고 있다. 이거 언제까지 컴파일이 돌아가는거지-_-;CF Div.1을 지금까지 participate하면서 대회 시간 안에 D,E는 읽어본 적도 없다. 이 상태가 몇달이 지나도록 계속되는 걸 ..
를 코딩했다. 2SAT을 겉핥기로 알고 있었던 나는 이 문제에서 탈탈 털렸다. 2SAT을 풀면 답이 나와야할텐데, 조건에 맞는 답을 구성하는 정확한 알고리즘이 전혀 떠오르지 않던 것-_-;; 그냥 greedy로 선택하면 되는데, 이걸 정확하게 구현하는 게 섬세한 코딩을 요했다. 이런건 경험에서 나오는 건가보다ㅠ_ㅠCF #318 D. 를 대회 시간 안에 코딩한 사람들에 대해선 그저 경외감밖에 들지 않는다.. 어떻게 (1) 최적 matching이 각각에 [i-2, i+2]에서 일어난다는 걸 증명하고 (2) 이에 맞는 적절한 segment tree구현을 해내는 일이 1시간 안에 일어날 수 있단 말인가-_- 지금 난 모든 재료들을 가지고 있어도 정확한 코딩을 위해 몇시간을 고민하는데..
토요일까지 외교학 과제를 하느라 바빴고일요일이 되어 소중한 PS의 시간이다! 싶어 도주랑 만나 연습을 했더니 똥망했다..정말..Codeforces #318을 나갔으면 정말 큰일날 뻔했다. B가 도저히 떠오르질 않아.. C를 봤는데 C도 애매하고.. 어휴ㅠㅠ B는 idea를 잘 떠올려야 했던 문제고, C는 leaf에서 올라오는 traversal이란 technique을 배웠다. D는 editorial이 이해가 안갔다..B에 막혔던 이유는 지금 생각해 보면 'block의 개수 변화'에 집착했던 탓인듯. 오히려 '각 tower가 없어지는 데 걸리는 operation수'로 생각하면 너무나도 쉬워진다. 역시 구해야 할 값부터 생각하고, 거기서 고려할 필요가 없는 값들을 생각에서 제외해야 함..
오늘은 하루종일 제이레빗 와 함께했다. 노래 참 좋아..알고리즘 수업을 처음 들어갔다. 다루는 주제들은 전부 한번쯤 발담궈본 주제인데, 내가 그 주제들을 가지고 시험을 칠 정도로 논리정연하게 알고있는 게 아니라서-_-; 조금 challenging할거라고 생각하고 있다.수업 참 바쁘다.. PS공부는 주말에야 할 수 있을 것 같다.
개강 첫날.. 현재 정상 수강신청된 강좌는 한 개 뿐이라-_-; 네 교수님께 모두 사인을 따로 받아야 한다. 오늘 두개는 무사히 완료!을 결국 전부 봤다. DreameScene을 쓰니까 바탕화면을 움짤..이라기보단 wmv로 계속 재생시킬 수 있더라고.. 바탕화면 아이콘 표시를 아예 없애고 바탕화면 갈때마다 행복해하고 있다.개강이라 새마음 새뜻으로 낡았던 스킨도 바꿨다. 훨씬 깔끔해진 기분! 역시 카테고리는 하나지! 그런데 검색결과가 텍스트 출력이 아니라 썸네일 출력이라서, 글마다 그림 하나씩을 넣어야할 것 같은 묘한 의무가 생겼다.. 이전 글들에 하나하나 넣기엔 너무 귀찮으니까 이제부터라도..에구 드디어 SPOJ 의 문제점을 알고 AC를 받았다. 본래 코드가 map을 너무 패기롭게 사용했었어..
주말을 정신없이 놀면서 보내고, 월요일도 딩가딩가 하다보니 벌써개강을 맞이하게 됐다.이번 학기는 내게 좀 특별한 의미를 가지고 있다. 복학후 첫학기이기 때문에 복학버프도 충분히 증명해야 하고, 밥벌어먹고 살기 위해서 택한 길을 이제 실제로 걸어나가야 하고, 거기서 실력도 쌓아서 증명해야 하는 자리도 있다. 하루하루를 바꾸긴 어렵지만, 전체적으로 돌아봤을 때 '아 이번 학기는 정말 달랐어'라고 평가할 수 있었으면 좋겠다. 정말 바쁘고 정신이 없어도, 내가 이 길을 꿈꾸면서 만들었던 여기 이 기록장에 꾸준히 발자취를 남겨야겠다. 항상 오늘 이 하루가 마지막인 것처럼 소중히 여기며 보내야지!
Andrew Stankevich Contest가 좋다길래.. Codeforces Gym에서 연습했는데..ASC 47의 A번 문제부터 탈탈 털림.. fort마다 순회하면서, drone과 tower를 각도로 나타낼 수 있는데, 여기서 segment tree를 써야 한다는 idea는 얻었다. 여기서 내 생각으로는 -PI/2~3PI/2를 돌면서, 만나는 tower에 대해서는 현재 선택타워에 대한 range sum을 답안에 더하고, 요소 하나를 추가하는 쿼리를 수행하고, drone에 대해서는 현재 선택타워에 대해서 +1을 모두 더하고, tower+PI의 위치에 대해서는 맨 끝 요소 하나를 제거하는 쿼리를 수행하는걸 생각했는데.. 예제데이터는 나오는데 바로 Test Case #2에서 WA가 난다ㅜ_ㅜ.. 답답저건 ..
26일은 CHelper를 깔겠다고 IntelliJ 코딩환경을 구성했으나, 플러그인 설치까지 완료하고 contest parsing도 잘 되는데, run만 하면 Nullpointerexception이 나면서 모든 java가 사라지는 바람에..ㅠㅠ 나는 java도 잘 모르고 IDE는 더더욱 모르기 때문에..ㅠㅠ 삽질만 하다 끝나버렸다. 대체 왜 이런가ㅠㅠ CHelper만으로 java를 새로 배울 이유가 되는데..27일은 오랜만에 Hackerrank에 들어가서 w16의 마지막 문제였던 를 해결했다. 당시 아이디어는 맞았는데 대부분의 케이스에 대해서 TLE가 났었는데.. 새로 얻은 라이브러리로 FFT를 가져와 구현해도 여전히 그러더라. 그게 2초 시간제한에 대해 모두 아슬아슬한 TLE들이었다..ㅜㅜ 로컬에서 돌리..
전대프연 문제들을 다 풀고.. 이것저것 문제들을 건들어보고 있다. 는 그냥 \( O(N) \) 의 순서들을 저장해놓고 각각의 거리를 재버리면 해결가능했고은 굉장히 간단한 \( O(N^2) \) 해법이 가능한데도 불구하고 이리저리 헤맸다. 3차원만 되면 머리가 복잡해져서.. 끙.. 이런걸 빠르게 구현하고 넘어가야 하는데.
전대프연 CDJ를 풀었다.
5회 전국 대학생 프로그래밍 대회 동아리 연합 대회 후기.전대프연 준비를 하고 집에 들어와 피곤해서 자는 걸 반복.. 하면서 오랫동안 블로그를 하지 못했다. 아무래도 팀연습인 데다가 실전연습으로 새로운 문제셋을 풀어보는 걸 반복하다보니 개인적인 생각을 정리할 시간은 부족했는데, 돌아보면 집에와서 개념정리를 하고 개인코딩 시간이 있었어야 했던 것 같다.ㅜㅜ 생각보다 더 열심히 했어야했어..22일 오늘 전대프연 대회가 있었고, 8월의 대부분을 투자한 결과는 6등이었다. 5등이 목표였는데 아쉽게도 약간 모자랐고.. 아쉬움이 많았다. 연습삼아 리저널을 돌 때는 아무리 생각해도 문제 해법이 나오지 않는 느낌이었는데, 이번 전대프연은 구현이 생각보다 까다로운 문제가 많았기 때문에 그런지 시간이 굉장히 모자랐다.시작..