스택 (1) 썸네일형 리스트형 [스택] Monotonic Stack 👉 Monotonic Stack 이란? : 스택의 원소들을 오름차순 혹은 내림차순 상태로 유지하도록 하는 알고리즘 단조(monotonic)는 수학 함수에 사용되는 용어이다.함수 y = f(x)가 다음 조건을 따를 때 단조 증가 또는 단조 감소하는 것으로 간주됩니다x가 증가함에 따라 y도 항상 증가 -> 단조 증가 함수 x가 증가함에 따라 y가 항상 감소 -> 단조 감소 함수 ☑️ 2가지 상황에 사용 가능 -> 1) 배열 특정 위치에서 정렬된 숫자들만 보고 싶을 때 -> 2) 배열 특정 위치에서 바로 다음 큰 값(or 작은 값)을 보고 싶을 때 만약 브루트포스로 한다면 O(N^2)이 될 것이다. 하지만 모노토닉 스택을 사용한다면 O(N)으로 시간복잡도를 줄일 수 있다! 👉.. 이전 1 다음