while (!stack.isEmpty() && 자료[stack.peek()] < 자료[i])
스택, 큐, 덱 문제들을 푸는 동안 많은 알고리즘들이 해당 알고리즘을 사용하는 것을 보았다
하나같이 해당 형식을 따르고 있는 것을 보고 뭔가 정형화된 알고리즘이 있나? 생각이 들었는데 스터디를 하면서 해당 알고리즘을 모노톤 스택, 큐, 덱 이라고 한다는 것을 알고 정리해보고자 한다.
monotonic 이란?
영어를 잘 못하는 필자이기에 뜻부터 찾아봤다.
단조롭다라는 뜻이란다 뭐가 단조롭다는 뜻일까?
변수와 결괏값이 **단조**롭다는 뜻이다.
변수와 결괏값이 증가할때는 함께 증가하고 감소할땐 함께 감소한다. 그렇다면 단조로운 거다.
사실 여기에 쓰인 monotonic은 통계 용어인 Monotonic Relationship에서 사용된 단어이다.
해당 단어는 값이 증가/감소할 때 때 다른 값들도 같은 방향으로 증가/감소 관계를 뜻한다.
Linear와 비슷한거 아니냐고? 비슷하지만 Linear는 값이 증가/감소하는 양도 비슷하지만 monotonic은 증가량은 상관 없다. Monotonic 이 조금 더 넓은 개념이라고 생각하면 된다.
monotonic 스택, 큐, 덱좋아 이제 Monotonic이 뭔지 알았다. 근데 스택, 큐, 덱 자료구조가 Monotonic하다는 것은 무슨 의미일까?
그것은 스택, 큐, 덱의 자료구조가 “모노톤”하다는 것을 의미한다.