devbelly

문제 www.acmicpc.net/problem/13511 알고리즘 HLD 풀이 첫번째 쿼리는 두 정점 사이의 간선가중치의 합, 두번째 쿼리는 k번째 정점을 구하는 문제입니다. 트리에서는 루트정점을 제외하고는 모든 정점의 부모정점을 유일합니다. 이를 이용하면 트리의 리프노드마다 간선의 가중치를 넣을 수 있습니다. u와 v의 lca를 a라고 가정하겠습니다. k번째 정점을 구하기 위해서는 그 정점이 u와 a사이에 있는지 a와 v사이에 있는지를 일차적으로 확인해야합니다. u와 a사이의 정점의 갯수가 cnt개라고 할 때, $k\leq cnt$ 라면 u로 부터 k번 위로 올라가면 되고 a와 v사이에 k번째 정점이 존재한다면 (전체 정점의 갯수 -k+1)번 위로 올라가면 k번째 정점을 구할 수 있습니다. 코드 #i..

문제 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좌표만 모아놓은 벡..

선언 영역 말 그대로 선언을 할 수 있는 영역입니다. 예를 들어 전역 변수는 모든 함수의 바깥에서 선언할 수 있습니다. 그 변수의 선언 영역은 그것이 선언된 파일입니다. 또한 어떤 변수를 함수 안에 선언한다면 그 변수의 선언 영역은 그것이 선언된 블록입니다. namespace 새로운 종류의 선언 영역을 정의함으로써 이름이 명명된 namepsace를 만들 수 있다는 기능이 c++에 추가되었습니다. 하나의 namespace에 속한 이름은 동일한 이름의 다른 namespace에 선언된 이름과 충돌하지 않습니다. namespace는 전역 위치 또는 다른 namespace에 놓일 수 있습니다. 이는 namespace가 상수 참조를 하지 않는다면 기본적으로 외부 링크를 갖게 됩니다. (const는 static 하므..

문제 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$ 이 됩니다. 입력을 받아 현재 자신이 어디의 버튼을 가리키고 있는지 찾습니다. 그리고 부모-자식관계로 묶어줍니다. 그리고 부모-자식관계가 성립하지 못한 버튼이 있다면 카운트를 해줍..