트리

    Union-Find, Disjoint Set (유니온-파인드, 상호 배타적 집합)

    ☞ Union-Find 란? 상호 배타적인 부분 집합(Disjoint Set)들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조 Union-Find에는 자료 구조에 명칭에 맞게 연산이 초기화(init), 합치기(union) 그리고 찾기(find)로 이루어져 있습니다. 초기화 : n개의 원소가 각각의 집합에 포함되어 있도록 초기화 합치기 연산 : 두 원소가 주어질 때 이들이 속한 두 집합을 하나로 합치는 연산 찾기 연산 : 어떤 원소가 주어질 때 이 원소가 속한 집합을 반환하는 연산 ☞ 상호 배타적 집합을 표현하는 방법은 2가지가 있는데, 첫번째는 배열입니다. 하지만 배열로 표현을 하면 합치기 연산에 드는 시간이 많이 걸리기 때문에 Union-Find 자료 구조 특성 상 효율적이지 못합니다. 그..

    세그먼트 트리 (구간 트리, Segment Tree)

    ☞ 세그먼트 트리란 이름 그대로 저장된 자료를 적절히 구간별로 전처리해 그들에 대한 질의들을 빠르게 대답할 수 있도록 해주는 트리입니다. 예를 들어 A={1,2,3,4,5}에서 [2,4] 구간의 최소치를 알고 싶다면 해당 배열을 순회하며 찾는 방법도 있지만, 해당 배열을 전처리해 세그먼트 트리를 생성해 더욱 더 빠르게 구현 할 수 있습니다. A배열을 세그먼트 트리로 바꾼 후 -> 아래처럼 구간별로 나눠 세그먼트 트리를 만들 수 있다. ☞ 이렇게 이론적으로만 설명했지만, 코드 구현에 많은 어려움이 있을 수 있습니다. 그래서 세그먼트 트리 문제의 한 유형인 구간 최소 쿼리(range minimum query,RMQ)를 구현해보겠습니다. ※ 여기서 중요한 점은 세그먼트 트리에 초기 크기를 설정해줘야하는데 가장..