[백준] 2887번 : 행성터널
2887번: 행성 터널 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 🤔 문제분석 크루스칼 알고리즘을 알고 있어야 해당 문제를 해결 할 수 있다. N-1개의 터널을 모두 건설하여( 최소산장트리의 간선의 개수) 행성들이 모두 연결된 상태를 만들어야한다. 또한, 간선의 개수를 구할때 O(n^2)이 아닌 O(3N)으로 해결 할 수 있는데, 비용을 계산할때, x와 y와 z를 각각 독립적으로 계산하여 간선에 누적한다. 📝 의사코드 간선을 만든다. x, y, z를 각각 분리하여 만들고,..
[백준] 6549번 : 히스토그램에서 가장 큰 직사각형
[백준] 6549번 : 히스토그램에서 가장 큰 직사각형 6549번: 히스토그램에서 가장 큰 직사각형 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 🤔 문제분석 이틀공안 고민하다가, 결국 해결하지 못하여, 풀이법을 참조하였습니다. 😂 해당 문제를 해결하는 방법은 스택을 활용하여 푸는 방법과, 분할정복, 세그먼트 트리를 활용하여 푸는 방법이 있습니다. 분할정복, 세그먼트 트리 최소 높이를 찾아서, 그 지점을 기준으로 양쪽을 분할한다. 해당 구간에서 최대 ..
[백준] 11505번 : 구간 곱 구하기
11505번: 구간 곱 구하기 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 📄 문제개요 수열이 주어지고, 업데이트, 쿼리가 주어졌을때 쿼리를 했을때에 업데이트된 구간 곱을 출력하는 문제이다. 🤔 문제분석 세그먼트 트리를 사용하는 구간곱 문제이고, 기존 구간 합과는 0을 곱해버리면 트리가 다음 업데이트일때 어떠한 수를 곱해도 0이 되기때문에 diff를 사용하지 않는다. update함수는 leaf 노드까지 방문했다가, leaf노드를 해당 값으로 초기..
느리게 갱신되는 세그먼트 트리 (Segment Tree Lazy Propagation)
개념 최대한 늦게 세그먼트 트리를 갱신시키는 방법으로, Lazy Value 값을 노드에 저장시켜놓은뒤, 노드의 방문을 필요때마다, 업데이트를 시켜준다. 쿼리나, 다른 업데이트가 필요할때, 그때 노드를 방문함으로서, 업데이트를 최대한 미루는 방식이다. Lazy Value 대상은 자식노드들이 모두 업데이트가 필요할 경우이다. 모든 자식노드가 업데이트가 필요할경우 해당 부모노드에서 자식노드까지의 방문을 멈추고, 해당 부모노드에 Lazy Value 값을 갱신시킨다. 추후 나중에 필요할때 Lazy Value 값을 적용 자식들에게 가중치를 전파한다. 가령, 원소는 (0, 9)가 존재한다고 하고, (3, 7)구간을 업데이트 한다고 가정한다. 빨간색과, 흰색을 제외한 부분은 다 업데이트를 해야하는 부분이며, 하늘색 부..
