목록2024/04 (1)

알고리즘 모음(C++)

백준 10868 - 최솟값(C++)

문제 링크입니다. https://www.acmicpc.net/problem/10868 10868번: 최솟값N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는www.acmicpc.net세그먼트 트리를 이용한 문제입니다.주어진 범위 안에서 가장 작은 값을 찾는 문제입니다. 일반적인 방법으로는, 배열을 for문으로 탐색 후 범위 안에 속한 값을 전부 비교해주게 됩니다. 하지만, 배열의 크기가 10^5이며, 주어지는 정수 쌍이 10^5이기에 시간 초과가 됩니다. 따라서, 세그먼트 트리를 이용해 일정 범위에서의 최솟값을 저장해주는 방법을..
백준 2024. 4. 2. 22:51
이전 Prev 1 Next 다음