https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 🐹 Description 문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그..
🦕 세그먼트 트리(Segment Tree)란? 세그먼트 트리는 배열에서 특정 구간에 대한 정보를 빠르게 쿼리하거나 수정할 수 있게 해주는 이진 트리 기반의 자료구조입니다. 이 자료구조는 주로 범위 쿼리 문제에 활용되며, 그 중에서도 구간 합을 빠르게 계산하는 데에 자주 사용됩니다. 원리 세그먼트 트리의 각 노드는 배열의 특정 구간을 대표합니다. 리프 노드는 배열의 개별 원소를 나타냅니다. 부모 노드는 자식 노드들의 합을 저장합니다. 이런 방식으로 트리의 루트 노드는 배열 전체의 합을 저장하게 됩니다. 예시 배열 A [1, 3, 5, 7, 9, 11]을 고려해봅시다. 이때 Tree 는 [0, 36, 9, 27, 4, 5, 16, 11, 1, 3, 7, 9] 가 됩니다. 각 노드에는 배열의 구간 합이 저장되..
https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 🐹 Description 문제 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 ..
