devbelly

문제 www.acmicpc.net/problem/15586 알고리즘 union find 풀이 $N$개의 정점으로 이루어진 트리 위에서 쿼리마다 가중치가 $k$이상인 인접한 노드들의 수를 구하는 문제입니다. 이 문제에서는 정점의 수와 쿼리가 5000이어서 각 쿼리마다 dfs를 돌려 수행이 가능했지만 이 문제는 둘 다 10만이므로 각 쿼리마다 dfs를 수행하면 시간 초과가 발생합니다. 경로의 최솟값이 $k$이상인 정점의 갯수는 가중치가 $k$이상인 간선들을 이어 만든 포레스트에서 자신이 속한 포레스트의 크기를 찾는 것과 동일합니다. 자신의 속한 포레스트의 크기를 구하기 위해선 유니온 파인드를 사용해야 하는데, 유니온 한 정점끼리 일관성을 갖기 위해서는 쿼리를 $k$를 기준으로 내림차순 정렬을 해야 합니다. ..

문제 www.acmicpc.net/problem/15591 알고리즘 DFS 풀이 $N$개의 정점이 트리를 이루고 각 엣지마다 가중치가 있을 때, 가중치가 $k$이상으로 이어져 있는 노드의 수를 구하는 문제입니다. $N$과 $Q$의 수가 최대 5000이므로 각 쿼리마다 $dfs$를 수행해도 시간초과가 나지 않습니다. $dfs(here, parent, weight)$를 호출하여 인접한 노드가 가중치 $k$이상으로 이어져 있는지 확인하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for (int i = 1; i = k && there != prv) { ret += 1; ret += dfs(there, here..

문제 www.acmicpc.net/problem/2613 알고리즘 이분탐색 풀이 $N$개의 구슬을 $M$개로 나눌 때, 각 그룹마다의 합이 가장 큰 것이 최소가 되게 하는 문제입니다. 최대의 최소화. 익숙한 이분탐색의 주제입니다. $solve$함수에서 입력값을 기준으로 $M$개 이하의 그룹을 만들 수 있는지 확인합니다. 딱 $M$개가 아닌 이하도 포함을 하는 이유는 그룹을 새로이 쪼개어 $M$개의 그룹을 만들 수 있기 때문입니다. 코드 #include #define rep(i, n) for (int i = 0; i p) { psum = 0; group += 1;..

문제 www.acmicpc.net/problem/17026 알고리즘 스택, 정렬 풀이 직각이등변삼각형으로 된 산의 꼭짓점이 주어집니다. 산의 색깔이 같을 때, 구분되는 산의 갯수를 구하는 문제입니다. 산 자체를 관찰하면 조금은 헷갈릴 수 있는 문제입니다. 산을 산의 시작 좌표와 산의 끝 좌표로 치환하여 문제를 풀어 나가야 합니다. 즉 산을 선분으로 치환하면 문제는 $N$개의 선분이 주어질 때, 완전히 겹치는 선분을 제외하고 세는 문제로 바뀌게 됩니다. 바뀌게 된 문제는 시작좌표를 오름차순으로 정렬하되, 시작좌표가 같다면 끝좌표는 내림차순으로 정렬하여 풀면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for..

문제 www.acmicpc.net/problem/15685 알고리즘 implementation 풀이 드래곤 커브들이 주어졌을 때, 네 모서리가 모두 드래곤 커브인 1x1 사각형의 갯수를 구하는 문제입니다. 다음 세대가 시작할 때, 이전세대에서 사용했던 방향 + 1로 드래곤 커브를 진행합니다. 이때 이전세대의 마지막 부분부터 이전세대의 첫 부분 순으로 다음 세대의 처음부터 다음 세대의 마지막부분의 방향을 결정합니다. 이를 관찰하여 구현해 풀면 되는 문제입니다. 코드 #include #define rep(i, n) for (int i = 0; i N; rep(i, N) { int x, y, d, g; cin >> x >> ..

문제 www.acmicpc.net/problem/15663 알고리즘 back tracking 풀이 N개의 자연수에서 M개를 고른 수열을 출력하되, 중복한 수열을 출력해서는 안됩니다. 재귀로 푸는 문제입니다. M개의 숫자를 고르는 것을 각 단계라고 생각해보겠습니다. 수열을 완성하기 위해서는 M개의 단계마다 수를 선택해야 합니다. 현재가 $i$번째 단계일 때, 당연하게도 이전에 고른 수를 선택해서는 안됩니다. 이를 확인하기 위해서 $used$배열을 사용했습니다. $used$배열은 다른 단계에서 선택한 수를 중복하지 않게 고르기 위함입니다. 다음으로 고려해야할 부분은 같은 단계에서 중복되는 선택입니다. $N$과 $M$이 각각 3, 2이고 숫자로 2 4 4 가 주어졌다고 해봅시다. 첫 번째 2와 두 번째 4를 ..

문제 www.acmicpc.net/problem/13512 알고리즘 HLD 풀이 트리 위에서 두 가지 쿼리를 진행해야 합니다. 첫 번째는 $i$번째 정점의 색을 바꾸는 것. 두 번째는 1번 정점에서부터 $v$정점까지 가는 경로 중 첫 번째로 만나는 검은 정점의 번호를 출력하는 것입니다. 트리에서는 문제를 풀기가 어려우므로 HLD를 이용해서 쭉 펴도록 합시다. 일자 상태로 만들었다면 세그먼트 트리의 사용이 가능해집니다. 세그먼트 트리에서 인덱스가 작을수록 트리 위에서는 루트에 가깝습니다. 이러한 이유 때문에 $query$함수에서 세그먼트 트리 쿼리를 처리할 때, 왼쪽에 검은 정점이 있다면 바로 리턴을 했습니다. 오른쪽에 있는 구간은 왼쪽보다 루트로부터 멀기 때문입니다(처음으로 만나는 검은 정점이 아님). ..

문제 www.acmicpc.net/problem/17025 알고리즘 dfs 풀이 아이스크림의 형태가 주어질 때, 가장 큰 조각와 둘레의 길이를 구하는 문제입니다. 단, 가장 큰 조각이 여러 개 일때는 가장 작은 둘레를 출력해야합니다. 기초 dfs 문제입니다. 정답 pair의 갱신을 쉽게하기 위해 $cmp$함수를 작성하여 풀었습니다. 코드 #include #define rep(i, n) for (int i = 0; i N; REP(i, N) REP(j, N) { char x; cin >> x; if (x == '#') board[i][j] = 1; } REP(i, N) rep(j, N) { if (!visited[i][j..