Algorithm problem-31

1. 문제

• 배열과 특정 구간을 입력받아, 구간의 최소값을 담은 배열을 리턴
• 구간 트리(segment tree)를 학습하고 풀어볼 것
• 개발냥발 - 구간트리

2. 시도

• 처음 시도는 단순하게 해보았다
• 구간이 여러개 주어질 수 있으므로 반복문으로 작성
• 배열의 특정 구간을 얕은 복사로 저장하고
• 스프레드 문법으로 구간의 최소값을 리턴
• 리턴한 최소값을 결과 배열에 저장하고 마지막에 리턴
• 기초문제야 수월하게 통과하였지만, 결과적으로는 구간트리를 학습하고 풀어야 할 것
• 처음 시도는 O(N)의 시간복잡도를 가지고, 구간이 여러개 주어질때마다 +의 형태로 늘어날 것
• 구간트리를 통해 O(logN)의 시간복잡도를 갖게 하는 것이 문제의 최종 목적일 것
• 각 구간의 최소값, 혹은 최대값, 혹은 합을 구간별로 저장해두고
• 필요한 구간이 생기면 미리 저장해둔 값을 가지고 비교하여 산출해낸다
• 즉, 단순 구간 탐색을 M번 시도할 경우, O(NM)의 시간복잡도를 가진다면
• 구간트리를 이용한 탐색의 경우, O(MlogN)의 시간복잡도가 되므로 반복할 수록 유리하다

3. 수도코드

const rangeMinimum = function (arr, ranges) {
  // 결과를 담을 배열 선언
  let result = [];
  // 범위만큼 잘라서 얕은 복사로 저장, 범위가 여러개일 수 있으니 반복문 사용
  for (let i = 0; i < ranges.length; i++) {
    let str = ranges[i][0];
    let end = ranges[i][1];
    let cur = arr.slice(str, end + 1);
    result.push(Math.min(...cur));
  }
  return result;
};

4. 레퍼런스