반응형 Segment tree18 BOJ 1395 : 스위치 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1395 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 2 with 나중에 업데이트하기 (Top-Down Segment Tree with Lazy Propagation) Si ~ Ti까지 스위치를 반전시켜야 하므로, 구간의 갱신이 매우 많다. 따라서 느리게 갱신되는 세그먼트 트리를 이용해서 문제를 풀 수 있다. 예를 들어서 1 ~ 16까지 스위치가 있고 1, 2, 4, 5번 스위치가 켜져있다고 하자. 이 상태에서 1 ~ 4번 스위치를 반전시키면 아래와 같이 트리가 갱신되어야 한다. 1 ~ 4번의 스위치가 3개 켜져 있는 상태에서 4개의 스위치를 반전시.. 2023. 1. 19. BOJ 14427 : 수열과 쿼리 15 with 세그먼트 트리 삼성 B형 전체 링크 https://www.acmicpc.net/problem/14427 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 10868 : 최솟값 - BOJ 14427 : 수열과 쿼리 15 with 우선순위 큐 BOJ 10868 : 최솟값을 관리할 때, 세그먼트 트리를 이용하였는데, 이 문제에서는 값이 변경되고, index도 같이 관리하면 된다. 따라서 tree는 아래의 구조체로 만들어진다. typedef struct st { int index; int value; }NODE; 같은 값인 경우는 index가 더 작은 값을 출력하기 위해.. 2023. 1. 19. BOJ 1572, 9426 : 중앙값 측정 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1572 https://www.acmicpc.net/problem/9426 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 1655 : 가운데를 말해요 with 세그먼트 트리 BOJ 1655 : 가운데를 말해요 with 세그먼트 트리에서 세그먼트 트리를 이용해 가운데 값을 찾았으므로, 이 방법을 이용해 중앙값을 측정해보자. 주어지는 숫자가 0 ~ 65535이기 때문에 65536 * 2개의 tree가 필요하다. 또한 세그먼트 트리는 index가 1로 시작하도록 구현을 .. 2023. 1. 19. BOJ 1655 : 가운데를 말해요 with 세그먼트 트리 알고리즘 문제 전체 링크삼성 B형 전체 링크삼성 C형 전체 링크 www.acmicpc.net/problem/1655 참고- 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree)- 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree)- 구간 합 구하기 with 다이나믹 세그먼트 트리 (Dynamic Segment Tree)- BOJ 1655 : 가운데를 말해요 with 우선순위 큐- 세그먼트 트리를 이용한 링크드 리스트의 삽입과 삭제 세그먼트 트리를 이용해 가운데 값을 찾아보자. 세그먼트 트리를 이용하면 index를 잘 관리해서 중앙값을 구할 수 있다.설명을 위해 입력되는 숫자의 범위가 1 ~ 16이라고 가정하자.그러면 아래와 .. 2023. 1. 19. BOJ 2357 : 최솟값과 최댓값 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2357 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 10868 : 최솟값 BOJ 10868에서 답을 구한 방법으로 최솟값을 구할 수 있고, 응용하면 최댓값도 구할 수 있다. 따라서 세그먼트 트리를 2개 이용하면 된다. 하지만 구조체로 묶으면 조금 더 간편하다. TREE 라는 구조체를 선언해서 min과 max를 동시에 관리한다. typedef struct st { int min; int max; }TREE; init에는 leftTree와 rightTree에서 각각.. 2023. 1. 16. BOJ 10868 : 최솟값 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/10868 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 2357: 최솟값과 최댓값 세그먼트 트리의 노드에 저장된 값은 아래 두 노드 중 작은 값이어야 한다. isMin 함수를 이용하여 더 작은 값을 판단하여 init을 하면서 tree에 저장한다. int isMin(int a, int b) { return (a < b) ? a : b; } int init(int left, int right, int node) { if (left == right) return tre.. 2023. 1. 16. BOJ 10999 : 구간 합 구하기 2 with 나중에 업데이트하기 (Top-Down Segment Tree with Lazy Propagation) 알고리즘 문제 전체 링크 삼성 B형 전체 링크 삼성 C형 전체 링크 https://www.acmicpc.net/problem/10999 참고 - 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition) - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - 구간 합 구하기 2 with 나중에 업데이트하기 (Top-Down Segment Tree with Lazy Propagation) BOJ 2042 - 구간 합 구하기와 비슷한 문제지만, 배열의 갱신이 연속된 특정 구간에 발생한다. 매 구간마다 하나씩 구간의 값을 바꾸면 느리기 때문에 알고리즘을 .. 2023. 1. 16. BOJ 2042 : 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) 알고리즘 문제 전체 링크 삼성 B형 전체 링크 삼성 C형 전체 링크 https://www.acmicpc.net/problem/2042 참고 - 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition) - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - 구간 합 구하기 2 with 나중에 업데이트하기 (Top-Down Segment Tree with Lazy Propagation) 여러 배열이 있고 구간의 합이 쿼리로 주어지면 합을 구해서 답을 구하는 문제다. 바텀 업 세그먼트 트리를 이용하여 구간 합을 구해보자. 주어진 구간의 합을 구해야할 배.. 2023. 1. 15. BOJ 2042 : 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) 알고리즘 문제 전체 링크 삼성 B형 전체 링크 삼성 C형 전체 링크 https://www.acmicpc.net/problem/2042 참고 - 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition) - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 다이나믹 세그먼트 트리 (Dynamic Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - 구간 합 구하기 2 with 나중에 업데이트하기 (Top-Down Segment Tree with Lazy Propagation) 여러 배열이 있고 구간의 합이 쿼리로 주어지면 합을 구해서 답을 구하는 문.. 2023. 1. 15. 이전 1 2 다음 반응형
