dong_gas

안녕하세요. 여러 이유로 https://blog.naver.com/dong_gas 동가스 : 네이버 블로그 23년부터 https://dong-gas.tistory.com/ 에서 여기로 이전했습니다. blog.naver.com 로 블로그를 이전했습니다. 글을 옮기거나 하진 않을 생각이고, 여기는 그냥 추억으로 냅둘 생각입니다. 이웃추가 환영입니다!

추하게 본선? Hello BOJ에 가게 되었다. 컷이 4솔이었다. A. 그냥 하란대로 구현했다. B. 잘 안보여서 C부터 풀고 다시 와서 풀었다. 난 이게 왜 골드5인지 아직 잘 모르겠다... 실버 기여도 많던데 ㅠㅠ C. 읽으면서 풀이가 보여서 바로 짰다. 위상정렬로 풀었다. N이 3000밖에 안되어서 별 생각없이 짜서 냈다가 시간초과를 받았다. O(N^3)풀이었다. 뭐 그냥 아주 쉽게 O(N^2)으로 바꿀 수 있었기에 한 2분 안에 다시 제출해서 맞았다. D. 이 문제가 참 어려웠다. 읽자마자 파라메트릭으로 풀어야 할 것 같이 생겨서 그렇게 풀려고 노력했다. 근데 판정하는 것을 한참동안 감도 잡지 못했었다. 그러다가 뒤늦게 X의 범위를 발견하고 점점 풀이를 구체화할 수 있었다. BFS도는 풀이를 짰는..

https://dong-gas.tistory.com/46 [목표] 2022 1. Sogang ICPC Team 운영 잘 하자 2. codeforces Expert 3. BOJ 1500 solve && solved.ac Diamond V 4. 대회 수상 어느 대회든 좋으니 수상. 5. 입대 준비 정보보호병 준비. 6. 운동 취미로 새로운 구기운동을 하나 배워볼 dong-gas.tistory.com 작년 1월 초에 이런 글을 썼었다. 나는 목표를 어느정도 이루었을까. 돌아보자. -> 잘 했나? 잘 했다고 생각하고 싶다. 남들이 어떻게 생각할 지는 잘 모르겠지만... 내가 할 수 있는 선에선 최고로 열심히 한 것 같다. 특히, 청정수컵/교내대회를 준비하는 것이 참 힘들었는데, 성공적으로 마친 것이 마음에 든다..

읽는 사람이 순열 사이클 분할(이하 순싸분)이 뭔지에 대해서는 안다는 가정 하에 글을 작성한다. '순열 사이클 분할'이라는 키워드로 검색하면 순싸분이 무엇인지 쉽게 알 수 있을 것이다. Codeforces에 순싸분이 자주 나오는 것 같다. 예전부터 순싸분이 나오면 탈탈 털렸었다... 근데 뭐 순싸분 자체가 어려운 개념은 아니니까... 가만히 있었는데 며칠 전에 또 털렸다. https://codeforces.com/contest/1768/problem/D 이 문제인데, 본 대회에서 80분동안 못풀었다.... 본 대회때 고민 + 오늘 다시 업솔빙하다가 알게 된 성질에 대해 한 번 정리를 해보려고 한다. 이를 대충 아시는 분들은 글을 읽을 필요없이 맨 아래의 결론과 생각이 일치했는지만 비교해보면 좋을 것 같다..

안녕하세요. dong_gas(김동건)입니다. 2022 Sogang Programming Contest가 성공적으로 마무리되었습니다.제가 올 한 해 가장 열심히 준비했던 대회입니다. 특히 대회 직전 2주 간은 올 한 해가 아니라 평생 가장 열심히 살았던 2주가 아닐까 싶습니다. raararaara 선배의 2020 Sogang Programming Contest 개최 후기를 참고하여 작성하였습니다. 후기가 참 맛있으니 시간이 된다면 한 번 읽어보시길..감사하게도 저 말고도 다양한 분들이 이번 대회 후기를 작성해 주셨습니다. 운영진 입장에서 이런 후기글은 참 고마운 것 같습니다.Master 1등 후기 - shandy5833Master 4등 후기 - lem0nad3(vermeil)잡부의 후기 - p_jun운영진..

ICPC가 끝났다. 예선 18위, 본선 20위다. 수상컷은 8솔이었다. 무섭다. 뭐 풀이는 koosaga님 같은 :god:들의 블로그를 보면 되기 때문에 딱히 적지 않겠다. 뭐 딱히 적을 문제도 없고... 오래되어서 기억도 안 난다. 대회 후기를 쓰려 했지만, 내 시점에서 쓰고 싶은 얘기가 딱히 없다. 별로 한 게 없기 때문. ICPC는 굉장히 어렵고, 잘하는 사람들이 굉장히 많다는 걸 느끼고 왔다. 그냥 뭐 팀 얘기나 미래에 대한 얘기나 써보자. DPS 6월 즈음에 학회 Slack에 semteo04선배가 팀원 한 명을 구한다고 올리셨다. 나는 그 당시 팀이 없었기 때문에 바로 DM을 보냈고, 뭐 며칠 뒤에 팀이 되었다. 솔직히 semteo04가 팀원 구한다는데 어케 참음 ㅎ; 근데 뭐 그 당시에 학회에..

https://codeforces.com/contest/1754/problem/B https://www.acmicpc.net/problem/25184 내가 만든 문제랑 매우 유사한 문제가 코포에 나와서 신기해서...ㅋㅋㅋ 풀이 코드도 동일하다 예제도 나랑 똑같이 만들어져 있다 ㅋㅋ 기념용 뻘글

후기를 쓰려고 했는데, 벌써 예선이 끝난지 일주일이 되었다... 교내 대회 준비와 과제에 치여 후기글을 쓸 겨를이 없었다. 정수론 과제를 하다가 하기가 싫어진 김에 간단하게 글을 써본다. 먼저, 이번 예선은 부득이하게 2인 팀으로 참가하게 되었다. 우리 팀은 매주 목요일 팀연습을 했었다. 대회 이틀 전 목요일에도 팀연습을 하기로 했었는데, 갑자기 Picasso 선배가 코로나에 걸렸다고 하셨다. 그래서 팀연습 못하겠네...라는 생각을 했는데 생각해보니까 대회도 못나갈 상황이었다. 바로 대회 본부에 문의 넣어서 2인팀으로 참가가능하냐고 물어봤더니, 가능하다하셔서 semteo04선배와 나 둘이서 참가하게 되었다....ㅋㅋ 본선에 못갈까봐 많이 무서웠는데 다행히 좋은 결과를 받았다. 운이 좋게도 전체 18위, ..

최근 대회(SUAPC)에서 SA, LCP를 몰라서 2등 했다. 그래서 Suffix Array와 Longest Common Prefix를 공부하였다. 삼소멤의 Suffix Array and LCP Array 글을 보며 공부했다. 공부하다가 알았는데 gumgood님 글이더라 ㄷ! 뭔가 반가웠다 ㅋㅋ 13264 접미사 배열 2 suffix array를 구해보자. 9248 Suffix Array suffix array와 lcp를 구해보자. 1786 찾기 KMP기본문제로 유명한 문제인데, 어디선가 SA로 풀 수 있다고 해서 SA로 풀어보았다. 문자열 S에 문자열 T가 몇 번 나타나는지, 그 위치는 어디인지 찾으면 된다. 더보기 부분문자열은 접미사의 접두사임을 생각하면 풀이를 떠올릴 수 있다. SA에 접미사가 정렬..

간만에 쓰는 코포 글 요즘 코포가 좀 이상했다... 맨날 말려서 C도 못 풀고... 끝나고 보면 왜 못풀었지라는 생각이 드는 문제들밖에 없었다. 블루 아이디가 2개라 그런지 간절함도 없었고... 그냥 안 풀리니까 하기 싫고. 하기 싫으니까 더 안 풀리고 뭐 반복이었던 것 같다. 많이 억울했다 ㅠ div3 날먹으로 일단 다시 블루 복귀는 성공했다... A. 그냥 브론즈 5 구현 B. 10보다 큰 것만 뒤에 0이 붙는다. 즉, 0이 나오면 0 앞 두 개가 알파벳을 나타내는 숫자이다. 이를 잘 구현하면 된다. 뒤에서부터 보면 편하다. C. 최소 비용으로 가려면 시작과 끝 사이 알파벳으로만 움직여야 한다. 또, 최대한 많이 밟아야 하니까 그 사이 알파벳들은 다 밟는 게 이득이다. 구현실수로 패널티를 쌓았다. 1..