본문 바로가기

백준

 (223)
백준 16563 - 어려운 소인수분해 https://www.acmicpc.net/problem/16563 소인수 분해는 $O(\sqrt N)$의 시간 복잡도로 $\sqrt N$까지 반복문을 돌아 자연수를 나누는 방법이 가장 잘 알려져 있다. 하지만 이 문제는 소인수 분해를 해야 할 수의 개수가 $N \leq 10^{6}$이므로 이 방법을 사용하면 TLE 판정을 받게 된다. Linear sieve를 이용하여 소인수 분해를 $O(\log N)$에 할 수 있는 방법이 있다. Linear sieve를 사용하여 소수 목록을 $O(N)$에 구한 후 소인수 분해를 실시하면 1초 이하의 시간으로 AC를 받을 수 있다. Linear sieve를 알지 못한다면 이 글을 참조하여 사용하면 된다.
[KOI] 백준 2169 - 로봇 조종하기 https://www.acmicpc.net/problem/2169 힌트 1 더보기 주어진 상태 공간에서 방향을 반영한 DP 테이블을 설계할 수 있다. DP 테이블을 만들 수 있겠는가? 힌트 2 더보기 이 문제를 바텀 업 DP로 해결을 시도할 경우 $2MN$번 반복문을 돌아야 할 것이다. 혹시 자기의 코드가 $NM$번 반복문을 돌고 있을 경우 무엇을 빠트렸는지 생각해보자. 힌트 3 더보기 최장 경로를 찾아야 하면서도 입력 값에 음수가 들어간다. 혹시 DP 테이블 초기화에 문제가 있진 않는지 점검한다. 풀이 더보기 3방향으로 로봇이 움직이면서 최장 경로를 찾는 문제이다. $N, M \leq 1000$ 임을 감안하여 우리는 다음과 같은 DP 테이블을 생각할 수 있다. dp[i][j][k] := k방향으로 좌표..
백준 1615 - 교차개수세기 https://www.acmicpc.net/problem/1615 힌트 더보기 이 문제를 풀기 위해선 inversion counting에 대한 지식이 있어야 한다. 문제에 주어진 형태처럼 교차 그래프가 주어졌을 때의 LIS 문제를 풀어본 경험이 있다면 이것도 비슷하게 접근할 수 있다. 생각해보자! 풀이 더보기 교차 그래프가 주어지고 몇개의 간선이 교차하는지 알아내야 한다. 어느 쪽 노드 집합을 기준으로 정렬을 한 후 반대 쪽 노드 집합들의 나열 형태를 보면서 교차 간선의 개수를 세보자. 그러면 inversion counting의 형태를 띄는 것을 관찰할 수 있다. 자세한 설명은 동일한 유형의 문제 풀이를 참조하라. 그대로 inversion counting의 개수를 출력해주면 된다. 전체 코드 #pragm..
[ICPC] 백준 20040 - 사이클 게임 https://www.acmicpc.net/problem/20040 힌트 더보기 유니온 파인드를 사용하면 그래프의 사이클 존재 여부를 빠르게 판별할 수 있다. 풀이 더보기 각 정점을 이어나갈 때 사이클이 어느 순서에 생기는지 알아야 하는 문제이다. 각 정점을 이을 때마다 DFS를 이용한 사이클 검출을 실시하면 $O(m^{2})$의 시간 복잡도로 인해 시간 초과를 받을 것이다. 하지만 유니온 파인드를 이용하면 아주 짧은 시간으로 사이클 여부를 판단할 수 있다. 각 정점을 union 하면서 만약 부모가 같은 정점을 마주치면 트리 상태에서 간선을 한 개 추가하는 것이므로 곧 사이클이 존재하는 그래프가 됨을 알 수 있다. m개의 쿼리를 진행하면서 사이클이 생기는지 검사하도록 하자. 전체 코드 #pragma GC..
[USACO] 백준 1774 - 우주신과의 교감 https://www.acmicpc.net/problem/1774 2021-08-17 기준 한글 번역의 질이 좋지 못하다는 코멘트가 있는 상황이다. 영어로 문제를 읽을 것을 추천한다. 이 문제는 2차원 평면에서 MST(Minimum Spanning Tree)를 완성해야 하는 문제이다. 각 정점이 서로 연결되었을 때의 간선들을 전부 생성해서 적절한 방법으로 MST를 구성하여 얻은 가중치의 합이 정답이 된다. 시간 복잡도는 간선을 생성하는 과정이 dominant factor이므로 $O(N^{2})$이다. 구현 다른 MST 문제와는 달리 2차원 평면이라 구현에 막연함이 있을 수 있다. 우리는 map을 이용하여 각 좌표의 index를 매기고 이 index를 기반으로 유니온 파인드를 만들면 간단하게 구현할 수 있..

티스토리툴바