세그먼트5 [백준 10999번] 구간 합 구하기 2 난이도: 플래티넘 IV 문제 링크: https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 그냥 접근하면 시간 초과에 걸리고, 세그먼트 트리를 이용해도 시간 초과에 걸리는 문제입니다. 이 문제를 풀려면 '느리게 갱신되는 세그먼트 트리' 알고리즘을 알아야 합니다. 해당 알고리즘에 대한 자세한 설명은 여기에 있으니 참고해 주세요. 문제를 풀 때 유의할 점은, 문제에서 숫자 배열의 인덱스는 .. 2021. 9. 26. 느리게 갱신되는 세그먼트 트리 세그먼트 트리에 대한 글을 먼저 읽고 와 주시기 바랍니다. 앞서 주어진 배열 arr에 대해, 특정 구간의 합을 O(log N)의 시간 복잡도로 구할 수 있는 알고리즘인 segment tree에 대해 알아보았습니다. 주어진 배열 arr에 대해 미리 구간을 나누어 합을 구한 세그먼트 트리 tree를 만들고, 질의가 들어온 구간에 대해 대표 노드를 선별하여 그 값을 참조하는 방식입니다. 세그먼트 트리는 생성에 O(N log N), 구간 합 구하기에 O(log N), 특정 인덱스의 값 수정에 O(log N)의 시간 복잡도를 가집니다. 그렇다면 다음과 같은 경우를 생각해 봅시다. "특정 구간의 값"을 변경하는 경우가 존재할 수 있습니다. 배열 arr에 대해 구간 [1, 3]의 값에 3씩 더하고, [2, 4]의 구.. 2021. 9. 26. [백준 2042번] 구간 합 구하기 난이도: 골드 I 문제 링크: https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 이 문제는 세그먼트 트리라는 알고리즘을 알아야 풀 수 있는 문제입니다. 기본적인 설명은 여기를 참고해 주세요. 세그먼트 트리의 기본적인 문제입니다. 한 가지 유의할 점이 있다면, 값을 수정할 때입니다. b의 값을 c만큼 수정하는 것이 아니라, b의 값을 c로 수정하는 것입니다. 따라서 차이값 differenc.. 2021. 9. 25. 세그먼트 트리 다음과 같은 문제를 생각해 봅시다. 배열 arr에는 수많은 int형 정수가 들어 있다. arr의 크기 n은 최대 10만이며, 각 정수는 1000 이하의 크기를 가진다. 배열이므로, 당연히 arr의 모든 원소는 인덱스가 정해져 있다. 인덱스는 0부터 시작한다. 총 m줄에 걸쳐 구간이 주어질 때, 주어진 구간합을 출력하는 코드를 작성하시오. (n 2021. 9. 25. [백준 2357번] 최솟값과 최댓값 난이도: 골드 1 문제 링크:www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 기말고사 전에 공부해서 풀었던 문제이지만... 블로그에 글로 정리하기에는 바빠서 지금에서야 정리해서 올립니다. 언뜻 보면 쉬워 보이는 최솟값, 최댓값 찾기 문제입니다. 처음엔 별 생각 없이 배열에 정렬해서 넣고 주어진 구간을 전부 탐색하여 최솟값, 최댓값을 찾아왔으나... 시간 초과가 걸렸습니다. 숫자의 크기가 크고, 갯수가 최대 10만 개가 되.. 2020. 12. 23. 이전 1 다음
