반응형 세그먼트 트리6 [C/C++] 백준 #2357 최솟값과 최댓값(세그먼트 트리) 세그먼트 트리를 구현해서 푸는 문제가 참 많습니다. 옛날에는 세그먼트 트리가 Platinum 등급에 있었는데, 이제는 모두 Gold 등급으로 떨어졌습니다. https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 최소값과 최대값을 주어진 범위안에서 찾는 알고리즘은 모두 \(O(N)\) 입니다. 미리 테이블을 만들어서 하는 것도 어렵죠. 세그먼트 트리만이 올바른 방법이라고 볼 수는 없습니다. 데이터를 \(\sqrt{N.. 2023. 4. 27. [C/C++] 백준 #2268 수들의 합 7(세그먼트 트리) 백준에 유달리 세그먼트 트리를 이용한 문제가 많습니다. 한동안 난이도는 플래티넘 등급이었는데, 이제는 골드 등급으로 설정되어 있습니다. 그만큼 보편화된 알고리즘이라고 생각하시면 될 듯 합니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2268 2268번: 수들의 합 7 첫째 줄에는 N(1 ≤ N ≤ 1,000,000), M(1 ≤ M ≤ 1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는 www.acmicpc.net 세그먼트 트리는 쿼리가 2종류(읽기 쿼리, 쓰기 쿼리) 이상이 존재하며, 쿼리의 수가 많을 때 사용합니다. 읽기 쿼리와 쓰기 쿼리는 서로 반대되는 개.. 2023. 4. 19. [C/C++] 백준 #2243 사탕상자(세그먼트 트리) #2243 문제는 백준 사이트에서 자주 나오는 고급 문제인 세그먼트 트리 문제입니다. 세그먼트 트리가 이미 많이 알려져서, 사실 이제는 그렇게 어려운 알고리즘이라고 할 수도 없습니다. 문제 링크입니다. https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 세그먼트 트리는 쿼리의 종류가 두가지인 경우에 사용할 수 있습니다. 저는 읽는 쿼리와 쓰는 쿼리라고 이야기를 합니다. 읽는 쿼리만 있는 경우에는 전체의 개수가 N, 쿼리의.. 2023. 4. 18. [C/C++] 백준 #2042 구간 합 구하기(세그먼트 트리) 구간 합 구하기 문제는 전형적인 세그먼트 트리를 이용하여 푸는 문제입니다. 세그먼트 트리 이외에도 비슷한 방식들이 존재합니다. 세그먼트 트리를 이용하는 문제는, 1. 많은 수의 쿼리를 진행해야 하고, 2. 미리 연산한 결과를 사용할 수 있어야 하고, 3. 미리 연산한 결과를 수정해야할 경우가 많은 경우 형태일겁니다. 위의 조건이 만족하지 않는다면, 다른 방식으로 계산하는 것이 더 좋을 수 있습니다. 세그먼트 트리와 관련한 문제들은 다음과 같습니다. https://sdev.tistory.com/958 백준 #1849 순열(세그먼트 트리) 이번 문제는 N개의 배열에 1부터 N까지 한번씩만 숫자가 써져있는 a[i] 수열이 있을경우, A[i] 란 수열은 원래의 수열에서 i번째 수의 앞에 있는 수 중 i보다 큰 .. 2023. 3. 21. 백준 #1849 순열(세그먼트 트리) 이번 문제는 N개의 배열에 1부터 N까지 한번씩만 숫자가 써져있는 a[i] 수열이 있을경우, A[i] 란 수열은 원래의 수열에서 i번째 수의 앞에 있는 수 중 i보다 큰 값이 있는 개수가 됩니다. 예를 들어서 원래의 수열이 2 7 3 5 4 1 8 6 이라고 한다면, 1 앞에 있는 숫자 중 1보다 큰 숫자는 5개가 있다, 2 앞에 있는 숫자는 없으므로 0이 됩니다. 그래서 만들어진 A[i] 수열은 5 0 1 2 1 2 0 0 이 됩니다. 문제는 A[i] 수열로부터 원래의 수열을 찾는 것입니다. i 값이 1인 경우는 간단하게 6번째 칸에 1이 존재한다는 것을 알 수 있습니다. 1 다음에는 2의 숫자의 위치입니다. 2의 숫자는 0이므로 가장 앞에 존재하겠죠. 2 1 다음은 3인데, 이 값은 1입니다. 이미 .. 2022. 10. 25. #1395 스위치(Segment Tree) 이번 문제는 Platinum III 난이도로 매겨진 좀 난이도가 있는 문제입니다. 기본적으로 이용하는 자료구조는 세그먼트 트리입니다. 세그먼트 트리 자료구조는 제가 나중에 한번 알고리즘적 적용 방법에 대해서 이야기하고자 합니다. 백준 사이트에서 세그먼트 트리와 관련된 문제가 꽤 여러개가 보입니다. 다 난이도가 높게 책정된 문제들입니다. 그런데 세그먼트 트리는 하나의 데이터를 업데이트할 때, \(O(\log N)\) 의 데이터 효율을 가집니다. 그리고 범위에 대해서 연산결과를 내는 것도 역시 \(O(\log N)\)의 효율을 보입니다. 그런데, 범위로 데이터를 업데이트한다고 할 때에는 이게 쉽지 않습니다. 해당 범위내의 것을 모두 업데이트를 일일이 한다고 하면, 세그먼트 트리를 쓰지 않고 배열 자료구조가 .. 2020. 2. 14. 이전 1 다음 728x90
