공부하자

https://www.acmicpc.net/problem/2268세그먼트 트리의 가장 대표격이라 할 수 있는 구간합 구하기 문제이다.하지만 이 문제에서 유의해야 할 부분이 두가지가 있는데,1. (i > j일 경우에는 A[j] + A[j+1] + ... + A[i]) A가 주어졌을 때, Sum(i, j)를 구하는 것은 매우 쉬운 문제이다. 라고 나와있듯, 이 문제에서는 i > j 인 경우 말고도 i 2. 최대가 1,000,000인 경우까지 다루다 보니, 자료형을 신경써야한다. 물론 이는 세그먼트 트리 문제를 풀다보면 어지간해선 다 long long형을 쓰기 마련이지만, 필자는 그냥 아무생각 없이 int로 처음에 풀었다가 틀렸다...이 두 부분만 주의해서 풀면 나머지는 세그먼트 트리를 이용해 부분합을 구하는..

https://www.acmicpc.net/problem/2357시간초과가 나지 않게 세그먼트 트리를 사용해서 푸는 것이 핵심인 문제이다. 필자 또한 처음 풀때 별 생각없이 그냥 벡터 인덱스 접근해서 풀었다가 시간초과가 났다. 생각해보니, 입력값의 최대크기가 100,000이고 애초에 그렇게 해서 풀렸다면 골드1일 이유가 없다. 따라서 시간초과가 나지 않게 하기 위해서는 세그먼트 트리를 이용해서 풀어야한다.보통 세그먼트 트리를 이용해서 푸는 문제들은 보통 구간 합을 구하거나 구성된 트리를 업데이트 하는 그런 문제들이 많은데 (BOJ #2042같은 문제가 대표적) 이 문제는 꼭 구간합을 구하는 문제가 아니더라도 세그먼트 트리를 활용하여 트리를 탐색해야 하는 문제이다.필자는 최솟값을 저장하는 트리와 최댓값을 ..