devbelly

문제 www.acmicpc.net/problem/17024 알고리즘 Greedy 풀이 인접한 지역과 거의 인접한 지역에 다른 종류의 풀을 심어야 할 때, 풀 종류의 최솟값을 묻는 문제입니다. 주어진 예제말고도 그림을 그려 특징을 파악하며 풀면 됩니다. 한 노드 A에 인접한 노드 B, C, D가 있다고 가정해봅시다. 이 노드들은 A와는 무조건 다른 종류의 풀을 사용해야만 합니다. 하지만 A를 제외한 B의 인접 노드에 풀을 심을 때는 A와 다른 종류의 풀을 심어야 하지만(A는 두칸이 떨어져 있어 거의 인접한 지역이므로) C, D에 심었던 풀을 심을 수 있음을 관찰하면 됩니다. 일반화하면 노드 중 최대 indegree값 + 1 이 정답입니다. 코드 #include #define rep(i, n) for (in..

문제 www.acmicpc.net/problem/17408 알고리즘 segment tree 풀이 점 갱신과 구간 사이의 두 값의 합의 최댓값을 묻는 문제입니다. 두 번째 쿼리는 세그먼트 트리에 최댓값을 저장하면서도 추가적으로 최댓값의 인덱스를 저장한다면 해결가능합니다. 주어진 범위가 $l, r$일 때, $query(l,r)$을 사용해서 최댓값 $M$과 인덱스 $idx$를 얻었다면 $query(l,idx-1)$와 $query(idx+1,r)$을 사용해 두 번째로 큰 값을 구하면 됩니다. 코드를 간결하게 하려고 $cmp$함수를 작성해 사용했습니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for (int i = 1..

문제 www.acmicpc.net/problem/17038 알고리즘 2-SAT 풀이 소들마다 두 개의 목초지에서 식사를 하고, 소들의 식성은 두가지로 나뉩니다. 한 식성은 두 목초지의 풀이 같아야만 하고, 다른 식성은 두 목초지의 풀이 달라야만 식사를 합니다. 이 때, 가능한 목초지의 경우의 수를 구하는 문제입니다. 두 종류의 풀이 주어지는 점, 이를 동시에 만족하도록 하는 점에서 2-SAT임을 파악하여 풀도록 합시다. 한 종류의 풀을 True, 다른 종류의 풀을 False로 설정하고 SCC를 사용합니다. 입력에서 10개의 목초지가 주어지고 5마리의 소의 입력이 다음과 같다고 생각해봅시다. S 1 2 S 3 4 S 5 6 S 7 8 S 9 10 이 경우는 32가지가 정답인 것을 알 수 있습니다. 1 2 ..

문제 www.acmicpc.net/problem/17037 알고리즘 DP 풀이 $N$개의 사각형이 주어졌을 때, $K$번 겹치는 사각형들의 넓이의 합을 구하는 문제입니다. 일차적으로 생각할 수 있는 풀이는 주어지는 사각형의 범위가 작으므로 2차원 배열을 만든 후, 배열을 색칠하여 푸는 풀이를 생각할 수 있습니다. 하지만 $N$제한이 10만이고, 사각형을 색칠하는데에는 길이의 제곱에 해당하는 시간이 필요합니다. 최악의 시간복잡도는 $10^5 * 1000*1000$ 이므로 시간초과입니다. 사각형이 주어질 때 마다 색칠하는 것이 아니라, 네 모서리에 체크만 한 후 최종적으로 배열을 확인할 때, 모서리를 옮기며 풀면 최종적으로 $O(N)$에 해결가능합니다. 코드 #include #define rep(i, n) ..

문제 www.acmicpc.net/problem/16768 알고리즘 dfs 풀이 인접한 곳에 동일한 숫자가 있으면 연결이 됩니다. 연결된 크기가 $K$이상일 때 숫자들은 터지고 터지는 숫자들이 없을 때까지 시뮬레이션 하여 결과를 출력하면 됩니다. 이 문제와 거의 유사한 문제로 조건이 4개가 모이면 터지는 것에서 $K$개가 모이면 터지는 것 외엔 다른 것이 없습니다. 연결된 크기를 세기 위한 $dfs$함수와 터지고나서 숫자들을 떨어뜨리는 $gravity$함수만 잘 구현하면 쉽게 풀 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i N >> K; rep(i, N) rep(j..

문제 www.acmicpc.net/problem/16767 알고리즘 priority queue 풀이 소들의 도착시간과 풀을 먹는 시간이 주어질 때, 가장 오래 기다리는 소의 시간을 출력하는 문제입니다. 한 소가 풀을 먹을 때 다른 소들은 기다려야하며, 대기하는 소들이 여럿일 때는 연장자부터 풀을 먹습니다. 우선순위 큐를 사용하는 문제입니다. info 구조체를 만들어 풀도록 합시다. 각각 나이, 도착시간, 풀을 먹는 시간에 대한 정보를 담고 있습니다. 구조체를 우선순위 큐, lower bound에서 사용하기 위해 각각 비교함수들을 작성했습니다. 우선순위 큐에 있는 소들을 처리할 때, 또다른 소가 도착할 수 있음을 유의합시다. 마지막 소까지 시뮬레이션이 끝나고 큐를 모두 비워내기 위해 for문의 범위를 $i..

문제 www.acmicpc.net/problem/18267 알고리즘 union find 풀이 트리에서 각 노드마다 소의 종류가 정해져 있을 때, 주어진 쿼리에서 그 사이 경로에 해당 소가 있는지 찾는 문제입니다. 트리에서 인접한 노드가 서로 같은 종류의 소라면 유니온 파인드를 통해 묶어줍시다. 이후 쿼리에서 두 노드의 부모노드가 다르다면 경로상에 두 종류의 소가 있음을 알 수 있습니다. 만약 부모노드가 같다면 그 부모노드의 소가 어떤 종류인지 찾아 비교해주면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i N >> M; memset(p, -1, sizeof(p)); rep(..

문제 www.acmicpc.net/problem/13510 알고리즘 hld 풀이 트리에서 두 개의 쿼리를 처리해야 합니다. 첫 번째는 $i$번째 간선을 업데이트, 두 번째는 경로 사이의 최댓값을 구하는 문제입니다. 두 번째 쿼리는 이전에도 설명 드린 적이 있습니다. 트리에서 한 정점은 부모로 가는 간선이 유일하므로 간선을 정점으로 표시가 가능합니다. 두 정점과 그 사이를 잇는 엣지가 있다면 자식정점의 번호를 간선처럼 생각하면 됩니다. 간선 문제를 해결했다면 첫 번째 쿼리인 간선을 업데이트 하는 것도 자연스레 해결가능합니다. 문제에서 입력받을 때 $i$번 간선이 무슨 정점들을 나타내는지만 기록하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i..