kth990303의 코딩 블로그

문제는 아래와 같다. https://www.acmicpc.net/problem/21923 21923번: 곡예 비행 동헌이는 모형 비행기 조종 대회에 참가하였다. 이 대회에서는 격자 모양의 공간에서 모형 비행기를 조종하여 얻는 비행 점수로 순위를 매긴다. 격자의 각 칸에는 점수가 부여되어 있고, 비행 www.acmicpc.net 그림만 보고 1초 정도 투포인터가 생각난 문제. 재밌어 보이는 문제였는데, 생각보다 삽질을 좀 했다. 간단하게 해설 및 주의포인트들을 살펴보도록 하겠다. 의식의 흐름 및 해설 이 문제같은 경우는 상향으로 비행할 때와 하향으로 비행할 때, dp 점화식이 달라지기 때문에 dp 함수를 2개로 나누는 것이 훨씬 편하다. 처음에는 한꺼번에 처리하려 했으나, if문 남발이 너무 심해져서 따로..

UCPC 2021 예선에 나온 문제이다. 본 대회 당시, 다익스트라+dp로 뇌절쳤던 문제여서 다시 풀어보았다. https://www.acmicpc.net/problem/22358 22358번: 스키장 첫 번째 줄에 다섯 개의 정수 $N, M, K, S, T$ ($1 \le N, M \le 10^5$, $0 \le K \le 10$, $1 \le S, T \le N$) 가 주어진다. 이후 $M$ 개의 줄에 각 코스의 정보가 세 개의 정수 $a_i, b_i, t_i$ ($1 \le a_i < b_i \le N$, $1 \le t_i www.acmicpc.net AC받은 풀이를 먼저 살펴보고, 다익스트라가 안되는 이유를 포스팅하겠다. AC 풀이 N이 최대 10만이지만, 리프트 횟수가 최대 10이다. 또한, l..

탈탈 털렸다... 하지만 덕분에 자극이 되기도 한 대회였다. 스코어보드는 아래 링크에서 확인가능하다. https://ucpc.acmicpc.net/contest/scoreboard/668 UCPC 2021 예선 ucpc.acmicpc.net 밑에 간단하게 그에 대한 후기를 남겨보겠다. 나는 D~F를 보고 모두 아이디어가 딱히 떠오르지 않았다. 마침 A~C가 다소 쉬운 듯하다는 소식을 들어 C로 빨리 넘어갔다. C는 간단한 확률/수학 문제였다. 중간에 구현을 조금 잘못하면서 헤매긴 했으나, 빠르게 C번 AC. 팀원 한 분께서 B가 BFS문제인데, 이유없이 틀린다는 소식을 들어 B로 넘어갔다. 그런데 아무리 봐도 B가 틀리는 이유를 모르겠어서 열심히 반례를 찾다가 다음 반례를 찾았다. 2 2 1 1 1 2 ..

문제 https://www.acmicpc.net/problem/15897 15897번: 잘못 구현한 에라토스테네스의 체 성원이는 오늘 이산수학 수업 시간에 에라토스테네스의 체에 대해 배웠다. 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 성원이는 이 방법에 너 www.acmicpc.net 꽤 어렵게 다가온 수학문제이다. N이 1e9이므로 O(N)은 시간초과가 발생한다. 어떻게 해결해야 할까? Harmonic Lemma (조화수열의 성질) 예시로 N=6인 경우를 들어보자. j의 값은 i의 값이 더해지므로, i의 값이 횟수에 영향을 준다. 맨 처음에 j는 디폴트값으로 1이므로, 1+(N-1)/i의 값이 횟수가 됨을 확인할 수 있다. 그러나, 아직까지는 아래 O(N) ..

백준에서 알고리즘 문제를 풀다가 아래 에러가 발생하였다. 프로젝트 속성 설정 등 별의별짓을 다해봤지만 그게 문제가 아니었다. 정답은 내 코드의 배열 크기가 너무 컸다는 것이 문제였다! 즉, 내 코드가 잘못된 것. 배열의 크기를 5001*5001*20으로 잡았더니 발생하는 현상. 1957364KB에 8168ms...ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 결국은 그냥 내 코드가 잘못된 것이었다. 배열의 크기를 1억 미만으로 잡아주자. +) 만약 잠깐 됐다가 다시 안된다? 그런 경우는 cout

백준 플랫폼에서 류호석배 알고리즘 코딩테스트가 열려 있어서 한번 참가해보았다. https://www.acmicpc.net/contest/view/666 제3회 류호석배 알고리즘 코딩 테스트 www.acmicpc.net 당시에 4문제를 해결하였고, 3번이 꽤나 어려웠던 기억이 있다. 중간중간에 저녁식사, 운동 등으로 잠깐 탈주했긴 했는데, 5시간 풀집중했어도 3번을 해결할 수 있었을지는 미지수. 다음날에 난이도 티어를 구경해봤는데 생각보다 높게 매겨져 있어서 놀랐던 문제셋이었다. 나는 대체로 다른 사람들에 비해 티어를 좀 후하게 주는 편 (의도한 것이 아니다) 이었는데, 이번엔 내가 다른 사람들에 비해 박하게 티어를 매긴 편이었어서 놀랐다. 문제는 역시 알고리즘 대가인 분께서 출제하셔서 그런지 꽤 괜찮았었..

푹 쉴까 아니면 코테를 응시할까 고민하다가 au0504님이 3시쯤에 코테를 응시한다길래 나도 한 번 응시해본 대회이다. https://www.acmicpc.net/contest/view/658 가희와 함께 하는 2회 코딩 테스트 www.acmicpc.net +) 1회 코딩테스트 후기는 아래 주소에서 볼 수 있다. https://kth990303.tistory.com/66 [210523] 가희와 함께하는 1회 코딩테스트 후기 그룹연습 시간과 대회 시간이 겹쳐서 응시할 생각이 없었는데, aru0504님이 응시한다고 하셔서 1~2문제만 풀어보고 넘기려다가 중간에 문제가 안풀려 오기가 생겨 도전해본 대회이다. https://www.acmi kth990303.tistory.com 뒤늦게 응시한 대회인데도 5등을 ..

PS를 좋아하는 사람이라면 누구나 알고 있을 듯한 대회, 삼성 대학생 프로그래밍 경진대회(SCPC) 2021에 참여하였다. 첫 응시인 만큼 본선 진출을 노린다기보단, 경험 및 실력증진을 위해 참가하였고, 목표는 1차 예선 통과이다. 369점으로 1차 예선을 마무리하였다. 2차 예선에 진출할 수 있을지는 미지수... 간단하게 아래에 문제를 풀면서 들었던 생각을 써보겠다. 1. 친구들 [80점 / 80점] 첫 번째 문제조차 풀지 못할까봐 긴장 반 설렘 반으로 문제를 살펴보았는데, 생각보다 할만했다. 나는 유니온파인드로 over kill 한 느낌이 있는데, 간단한 구현만으로 처리가 가능할 듯하다. 만점자 수가 굉장히 많은만큼 배점도 상당히 낮다. 1번 문제의 배점이 100점이 아닌 80점인 경우는 처음 보는 ..

UCPC 2021이 이제 한달도 남지 않았다. 이번에 나는 군생활을 하면서 알고리즘 실력을 향상시키고 여러 대회를 경험해보고 싶었기 때문에 우리 학교 알고리즘 소그룹에서 팀원을 구해 경험삼아 대회에 나가볼 사람을 구했었다. 2018년, 2019년, 2020년에 비해 이번년도에는 건국대 팀이 많이 없었다. (UCPC 참여인원 중 건국대학교 소속인 사람은 우리 팀 포함 총 4명뿐이었다.) 속상하기도 했지만, 이왕 이렇게 된거 열심히 해보자 다짐하게 되는 계기가 됐다. UCPC 본선 진출은 상위 50팀 내외이다. 이는, 아무리 못해도 최소 플레티넘 중위 문제를 해결해야 본선에 진출할 수 있다는 의미. (UCPC 2020은 서버가 터져서 거의 모든 팀을 본선으로 보내버린 예외의 경우) 나는 이번 년도에 본선진출..

개인적으로 너무 참여하고 싶은 부스트캠프에 접수해보았다. 아직 2학년이어서 연습 삼아 부캠에 접수하여 코테를 응시해보았다. https://boostcamp.connect.or.kr/guide_wm.html 부스트캠프 개발자의 지속 가능한 성장을 위한 학습 커뮤니티 boostcamp.connect.or.kr 서류 및 이력서 접수로 탈락하는 경우는 없는 듯하다. 나는 프로젝트 경험이 많이 없는 편이었고, 알고리즘 및 백준 경험을 많이 작성하였다. 프로젝트라 해봤자 다 개인프로젝트고, 그마저도 Spring이나 node.js로 crud와 로그인 구현한 정도뿐이다. 1차 코딩테스트 (2021.06.24.) 1차 코딩테스트 안내 메일이 왔다. 사용가능한 언어는 C, C++, C#, Java, Javascript, ..