devbelly

문제 www.acmicpc.net/problem/18321 알고리즘 Union find 풀이 $N$개의 지역과 $N$마리의 소가 있습니다. 초기 배치 상태가 주어질 때, $i$번 지역에는 $i$번 소가 있도록 해야 합니다. 소들이 움직이기 위해 wormhole이 주어질 때, 사용하는 wormhole 넓이의 최솟값이 최대가 하도록 요구하는 문제입니다. 최소의 최대화, 최대의 최소화는 익숙한 이분탐색 주제입니다. 이분 탐색 + DFS로도 풀 수 있으나 좀 더 빠른 Union find로 풀이법을 소개해드리겠습니다. 초기에는 모든 지역이 이어져 있지 않다고 가정합시다. 그리디하게 넓이가 큰 간선부터 양 지역을 연결하는 것은 최선의 전략입니다. 정답이 $k$인데 $k+x$넓이의 간선(x는 양수)을 사용하는 것은 ..

문제 www.acmicpc.net/problem/11438 알고리즘 sparse table 풀이 LCA를 빠르게 처리하는 문제입니다. LCA를 구하는 과정은 두 단계로 나뉩니다. 첫 번째는 두 정점 간의 깊이를 일치시키고 만일 이때 정점이 일치하지 않다면 각자의 $2^i$ 위의 정점을 살펴보며 다르다면 트리에서 올라가면 됩니다. 높이가 일치한 후 $2^i$ 위의 정점이 다르다면 올라갈 여지가 남았다는 뜻이기 때문입니다. LCA쿼리당 요구하는 시간복잡도는 $O(logN)$입니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for (int i = 1; i = 0; --i) { if ((dep[u] - dep[v]) ..

문제 www.acmicpc.net/problem/2091 알고리즘 DP 풀이 만들 값과 동전의 갯수가 주어졌을 때, 동전을 최대로 사용하여 해당 값을 만드는 문제입니다. 최소동전을 사용하는 것은 동전들의 관계가 canonical 하므로 그리디로 해결가능하나 최대로 사용하기 위해선 다이나믹 프로그래밍을 이용해야합니다. $cache[i]$= i원을 만들 때, 사용하는 최대 동전의 갯수 작은 동전부터 작은 값의 테이블을 채워나가면 됩니다. 특정 값까지 테이블이 채워져 있다면, 당연하게도 동전을 많이 사용하려면 다음 테이블을 갱신할 때 작은 동전부터 사용해야하기 때문입니다. 테이블에 채워져 있는 값을 발견했다면 그 값 이전은 이미 최대로 동전을 사용하기를 마친 상태이고, 값 뒤에만 갱신해나가면 됩니다. 코드 #..

문제 www.acmicpc.net/problem/18879 알고리즘 sorting 풀이 2차원 공간에 여러 particle들이 주어졌을 때, 상호작용 후 최소한의 particle의 수를 묻고 있습니다. 상호작용의 조건은 $x1\leq x2,\, y1\leq y2$ 을 만족해야합니다. 만약 두 좌표가 있을 때, 상호작용해서 없애야하는 좌표는 상대적으로 오른쪽 위에있는 좌표입니다. 왼쪽 아래 좌표는 후에 다른 좌표들을 더욱 없앨 수 있기 때문입니다. 주어진 좌표들을 정렬한 후, y좌표를 담을 벡터를 만듭니다. 이는 지금까지 살아있는 y좌표들의 그룹입니다. 좌표를 정렬했으므로 좌표벡터의 $i$번쨰 원소는 이전의 모든 좌표들과 상호작용할 첫번째 조건이 충족되었습니다($x1\leq x2$). y좌표만 모아놓은 벡..

문제 www.acmicpc.net/problem/11562 알고리즘 floyd-warshall 풀이 $u$에서 $v$로 갈 때 필요한 최소한의 다리 설치 수를 묻고 있습니다. 플로이드-와샬의 특징은 모든 출발지와 도착지에 대해 최단거리를 구할 수 있습니다. 문제의 특징과 잘 맞으며 더군다나 $n$ 제한에서 플로이드-와샬임을 느낄 수 있습니다. 처음 모든 $dist$를 큰 값으로 초기화합니다. 만약 양방향 도로가 주어진다면 $dist[u][v]$, $dist [v][u]$를 0으로 설정합니다. 이는 각 정점에서 다른 정점으로 가기 위한 최소한의 다리 설치를 의미합니다. (단, 다리 설치는 단방향 다리에만 추가적으로 설치할 수 있습니다). 반면 단방향 도로가 주어진다면 연결되지 않은 곳만 1로 업데이트해주면..

문제 www.acmicpc.net/problem/14932 알고리즘 Union-find 풀이 버튼을 순차적으로 나갈 때, 금고를 풀 수 있는지 묻는 문제입니다. 하나의 노드에서 다른 노드로 간다. 라는 점에서 다양한 풀이들을 떠올릴 수 있습니다. 저는 처음에 SCC로 접근하여 컴포넌트의 수를 카운트하여 답을 계산하였습니다. 다른 풀이로는 하나의 노드를 자식으로 다른 노드를 부모로 설정하여 유니온 파인드로 접근하는 것입니다. 각 버튼의 고유값을 매기기 위해 순차적으로 번호를 매겼습니다. (r,c)에 해당하는 번호는 $r*N+j$ 이 됩니다. 입력을 받아 현재 자신이 어디의 버튼을 가리키고 있는지 찾습니다. 그리고 부모-자식관계로 묶어줍니다. 그리고 부모-자식관계가 성립하지 못한 버튼이 있다면 카운트를 해줍..

문제 www.acmicpc.net/problem/1744 알고리즘 Greedy 풀이 수들이 주어졌을 때, 각 수들을 적절히 묶어 모든 수들의 합이 최대가 되도록 하는 문제입니다. 직관적인 그리디한 문제입니다. 두 수의 묶었을 때 가장 크기 위해서는 각 수가 첫번째로 큰 수, 두번째로 큰 수가 되어야합니다. 단 놓치기 쉬운 포인트 중 두 수를 묶는 조건입니다. 두 수가 음수면 무조건 양수로 만들 수 있으니 곱해나가는 것이 맞으나 두 수가 양수여도 두 수의 곱보다 합이 작을 경우 묶어서는 안됩니다. 예를 들어 수가 1, 1이라면 곱하는 것 대신 두 수를 더하는 것이 더 이득이기 때문입니다. 아래 코드는 양수와 음수를 구분하여 벡터에 넣은 후, 음수벡터의 크기가 홀수라면 1을 추가합니다. 양수 벡터는 수를 따..

문제 www.acmicpc.net/problem/18878 알고리즘 정렬 풀이 $i$번째 소부터 자신의 기호식품의 순위에 따라 가져 갈 때, 각 $i$번째 소마다 몇 개의 시리얼을 나누어 줄 수 있는지 묻는 문제입니다. 문제를 나이브하게 접근하면 처음부터 기호식품을 확인하며 나누어 주면 됩니다. 즉 1번째 소 뒤에 있는 $N-1$마리의 소들에 대해서 나누어주고, 2번째 소 뒤에 있는 $N-2$마리의 소들에 대해 나누어주는 식입니다. 이와 같이 시뮬레이션하면 요구하는 시간 복잡도는 $O(N^2)$ 이므로 시간 초과를 받게 됩니다. 뒤에 서있는 소부터 계산해보도록 합시다. 만약 $k$번째 소 이후에 몇마리가 가져갈 수 있는지를 다 계산을 하였다면 $k-1$번째 소는 이전의 상황과는 관계없이 무조건 자신이 가..