문제 BOJ 6549번 풀이 히스토그램 문제에 스택과 세그먼트 트리를 사용한 풀이가 있는데, 세그먼트 트리를 사용하여 풀어보겠습니다. 위와 같은 히스토그램이 있습니다. 아래와 같은 분할 정복을 사용하여 문제를 풀어보겠습니다. * 구간 [left, right]를 정복하고 있을 때, - 해당 구간에서 최소 높이를 h라고 두고, 높이가 h인 직사각형의 인덱스를 i라고 하겠습니다. - (right - left + 1) * h가 답이 될 수 있습니다. - 그리고 구간 [left, i - 1]과 [i + 1, right]에서 다시 분할 정복을 해나가면 됩니다. 테스트케이스를 예시로 설명해보겠습니다. [1, 7]을 정복하고 있을 때 2번째 직사각형의 높이가 1로 가장 작으니(최솟값이 여러개 있으면 아무거나 선택해도 ..

문제 백준 14428번 풀이 전형적인 세그먼트 트리를 구현하는 문제입니다. left ~ right의 대푯값을 left ~ right에서 가장 작은 값의 인덱스로 놓아주고 갱신해주면 됩니다. 소스코드 #include using namespace std; int arr[100001], seg[400001]; int init(int node, int start, int end) { if (start == end) return seg[node] = start; int mid = start + end >> 1; int a = init(node * 2, start, mid), b = init(node * 2 + 1, mid + 1, end); if (arr[a] == arr[b]) return seg[node] =..

문제 백준 9997번 풀이 모든 경우의 수를 고려하더라도 시간 복잡도가 $ O(2^N) $ 이므로 시간 내에 해결할 수 있습니다. 그러나, 비트 연산자를 이용해서 탐색하는 경우 시간 복잡도가 $ O(N 2^N) $ 이므로 TLE가 나기 때문에, dfs를 구현하여 풀어야 됩니다. a부터 z를 사용하였는지 체크하는 것은 OR 비트 연산을 사용하여 빠르게 처리할 수 있습니다. 소스코드 #include using namespace std; typedef long long ll; int n; vector vec; int solve(int sz, int vis) { if (sz == n) { if (vis == (1 > n; for (int i = 0; i > s..

문제 백준 1806번 풀이 투포인터, 누적합(map), 분할정복을 사용하여 풀 수 있습니다. 이 문제의 경우 배열의 모든 원소가 자연수이므로 투포인터 풀이도 가능합니다. 왼쪽(l), 오른쪽(r) 변수와 l ~ r 사이의 합을 저장하는 sum 변수를 만들어 문제의 조건에 맞게 l과 r을 관리하면 됩니다. * sum이 S(문제에서 주어지는 것)보다 크거나 같으면 left를 한칸 오른쪽으로 옮깁니다. * 그렇지 않으면 right를 오른쪽으로 옮깁니다. - 위 과정을 l과 r 모두 n - 1이 될 때까지 반복합니다. 소스코드 #include using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); cout.tie(0); int n, s, ans = 1..

문제 백준 12930번 12930번: 두 가중치 0번 정점에서 1번 정점으로 가는 최단 경로의 비용을 출력한다. 0번에서 1번으로 갈 수 없는 경우에는 -1을 출력한다. www.acmicpc.net 풀이 조건이 복잡한 다익스트라입니다. priority queue에 cost, 현재 정점, 가중치 1의 합, 가중치 2의 합을 저장해두고 매번 갱신해주면 됩니다. 소스코드 #include using namespace std; typedef long long ll; typedef pair ppll; ll dist[21], graph[21][21][2]; vector _node[21]; int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; for (int t..

문제 백준 1197번 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 � www.acmicpc.net 크루스칼 알고리즘 3 3 1 2 1 2 3 2 1 3 3 테스트 케이스의 내용을 시각화하면 아래와 같습니다. 트리 구조를 유지하되, 간선의 가중치를 최소화하려면 (1, 3)의 간선을 제거하면 됩니다. ​ 크루스칼 알고리즘은 최소 비용 신장 트리를 찾는 알고리즘입니다. 작동 방법을 설명하기 위해 아래 그래프의 최소 스패닝 트리를 구해보겠습니다. 우선, 간선의 가중치가 오름차순이 되도록 정렬을 ..