Samsung Software Membership
    • BLOG
    • ABOUT US
    slah007's profile image

    정윤성

    All Posts by slah007

    • slah007's profile image

      slah007

      January 27, 2025

      Cartesian Tree를 활용한 문제 해결

      Cartesian Tree Cartesian Tree는 대소 관계가 있는 값의 배열으로부터 유도되는 Binary Tree로, 구간의 min/max와 관련된 문제에 사용하면 편리한 자료 구조입니다. 배열의 최솟값 또는 최댓값에 해당하는 인덱스를 루트로 하게 되는데, Min Cartesian Tree의 경우 최솟값에 해당하는 $\mathrm{array}[i] = \min_{l \leq i \leq r}(\mathrm{array}[i])$인 $i$가 루트가 되며, $[l, r]$번째 원소의 최솟값에 대응되는 노드 $i$의 왼쪽 자손은 $[l, i-1]$에서의 최솟값, 오른쪽 자손은 $[i+1, r]$에서의 최솟값에 해당하는 인덱스가 됩니다. 자주 사용하게 되는 성질 몇 가지가 있는데, 각 노드의 subtree가...

    • github
    • facebook
    • instagram
    • youtube
    • S/W Membership

    Copyright © SAMSUNG SOFTWARE MEMBERSHIP. All rights reserved.