반응형 세그먼트 트리15 BOJ 5397 : 키로거 with 세그먼트 트리, 링크드 리스트 삼성 C형 전체 링크 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/5397 참고 - BAPC 2010 I번 문제 - BOJ 5397 : 키로거 (스택) - 링크드 리스트 Linked List - 링크드 리스트 삭제 - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 1655 : 가운데를 말해요 with 세그먼트 트리 - 세그먼트 트리를 이용한 링크드 리스트의 삽입과 삭제 - BOJ 5397 : 키로거 with 세그먼트 트리, 링크드 리스트 위 문제를 스택을 이용한 방법 대신, 세그먼트 트리와 링크드 리스트로 풀어보자. 다만 이 방법으로는 이 문제의 tc를 시간 내에 통과할 수 없다. 키로거는 커서를 한 칸씩 이동.. 2023. 8. 25. BOJ 12899 : 데이터 구조 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/12899 참고 - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 1655 : 가운데를 말해요 with 우선순위 큐 - BOJ 1168 : 요세푸스 문제 2 BOJ 1168 : 요세푸스 문제 2와 마찬가지로 세그먼트 트리에서 n번째 값을 찾는 방식으로 문제를 해결할 수 있다. 찾은 값은 update를 이용해 다시 삭제하면 된다. #include int N; int tree[4194304]; int start, leafSize; void update(int index, int diff) { index += start; while (index > 1) { tree[ind.. 2023. 3. 4. BOJ 1168 : 요세푸스 문제 2 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1168 참고 - BOJ 11866, 1158 : 요세푸스 문제 0, 요세푸스 문제 - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 1655 : 가운데를 말해요 with 우선순위 큐 큐(Queue)를 사용하는 BOJ 11866, 1158 : 요세푸스 문제 0, 요세푸스 문제보다 N이 매우 큰 경우다. 세그먼트 트리에서 n번째 값을 찾는 방식으로 문제를 해결할 수 있다. N이 100,000이고, 100,000보다 2배 이상 큰 2의 배수는 262,144이다. 따라서 tree의 사이즈는 다음과 같다. int tree[262144]; 이제 N보다 큰 2의 배수를 구해보자.. 2023. 3. 4. BOJ 2042 : 구간 합 구하기 with 다이나믹 세그먼트 트리 (Dynamic Segment Tree) 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2042 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 메모리 풀 Memory Pool - 메모리 풀 vs malloc 속도 비교 - 링크드 리스트 Linked List 이전 글에서는 tree의 크기를 넉넉하게 잡았다. 구간의 길이가 100만이기 때문에 실제로는 2배 정도의 크기만 있으면 된다. 여기서는 필요한 만큼만 적절히 잡아서 다이나믹하게 트리를 만들어보자. 배열의 index를 이용하는 방법 원래 update 코드는 아래와 같다. void update(int left, int right, int node, int index, ll value) { if (inde.. 2023. 2. 8. BOJ 6549 : 히스토그램에서 가장 큰 직사각형 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/6549 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 10868 : 최솟값 문제의 예시대로 사각형을 그려보자. 전체 구간 [1 ~ 7]을 포함하는 가장 큰 직사각형의 넓이는 7이다. 예를 들어 구간 [6 ~ 7]만 포함하는 가장 큰 직사각형의 넓이는 6이 된다. 이 넓이는 어떻게 구할 수 있을까? 구간 [a ~ b]에서 가장 작은 높이와 (b - a + 1)을 곱하면 된다. 그리고 구간 [a ~ b]에서 가장 작은 높이의 index가 c라면 구간 [a ~ c - .. 2023. 1. 20. BOJ 3653 : 영화 수집 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/3653 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) 6개의 영화가 있고 최대 M = 10번 영화를 본다고 가정하자. 그러면 세그먼트 트리를 아래와 같이 만들 수 있다. 마지막 leaf에서 10개는 비워두고, 6개의 영화를 순서대로 노드에 넣고 값을 1씩 증가시킨다. 영화를 10번 보기 때문에 앞의 노드를 그만큼 비워둔다. 영화가 순서대로 1, 2, 3, 4, 5, 6이 쌓여있는 상태다. 예를 들어 3번 영화를 본다고 가정하면, 3번 앞에는 1번과 2번 영화가 있기 때문에 .. 2023. 1. 20. 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. 이전 1 2 다음 반응형
