kth990303의 코딩 블로그

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) ..

백준 플랫폼에서 류호석배 알고리즘 코딩테스트가 열려 있어서 한번 참가해보았다. 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등을 ..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 이 문제도 좀 유명한 편인데 뒤늦게 풀었다. N은 50만, 시간 제한은 1.5초라 상한 시간복잡도는 O(NlgN)인 문제이다. KOI 2009 지역본선 초등부 4번, 고등부 2번이기도 한 문제이다. 지역본선이라 그런지 난이도는 높지 않은 듯하다. (근데 애초에 초등학생이 이정도 문제 풀 정도면 대단한거 아닌가... 요즘 초등부 문제들이 워낙 괴랄해서 쉬워보이는건가...) 의식의 흐름 및 해설 처..

https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 이 문제 역시 예전에 해결했던 문제이다. 그러나 복습 겸 다시 한 번 풀어보았다. 의식의 흐름 및 해설 역시 골드 난이도 답게 호락호락하지 않았다. 확실한 건 점수를 많이 얻을 수 있는 과제를 많이 할 수록 좋다는 점이다. 당연해보이지만, 여기까지 접근했다면 30%는 맞는 셈. 그런데 최대한 많은 과제를 하기 위해선 마감기한이 최대한 앞에 있는 것을 하는 게 좋지 않을까? 그렇다고 마감기한 순으로 정렬하면 더 높은 점수를 받을 수 있는 과제..

생긴 건 되게 bfs 처럼 생겼는데 알고보니 bfs + bipartite matching + binary_search (필수는 아니지만) 가 복합적으로 사용되는 문제였다. https://www.acmicpc.net/problem/1348 1348번: 주차장 세준 주차장은 R*C크기의 직사각형 모양이다. 세준 주차장에는 N개의 차와, M개의 주차 구역이 있다. 그리고, 모든 차는 주차 구역에 주차하려고 한다. 교통 제한 때문에, 차는 주차장의 경계와 평 www.acmicpc.net 의식의 흐름 및 해설 하나의 주차장에는 하나의 차만 들어갈 수 있고, 그 외에 이동하면서 차끼리 충돌은 고려하지 않는다. (휴... 정말 다행이다. bfs로 충분히 할 수 있겠다.) 주차장과 차끼리 연결되는 모습이 이분그래프를 ..

개인적으로 가장 어려워하면서도, 가장 흥미가 있는 주제인 LCA 문제이다. 사실 처음부터 lca 문제를 해결하려던 건 아니고, 트리 문제를 구경하던 중 lca가 떠오르는 문제를 발견하여 lca 연습 겸 풀어본 문제이다. https://www.acmicpc.net/problem/13511 13511번: 트리와 쿼리 2 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 아래의 두 쿼리를 수행하 www.acmicpc.net 상한 시간복잡도: O(NlgN) 사용 알고리즘: LCA LCA 코드 살펴보기 LCA를 O(lgN)의 속도로 찾아내야 상한 시간복잡도를 넘기지 않는다. 루트노드의 번호가 ..

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