[질문] 질문있어요 단조 스택이 왜 O(n)이에요?

[투투♡(grw8vvf5izqn)]

최악에 O(n) 이 될수 없을거 같은데

자꾸 미궁에 빠짐여

단조 스택 글보면 n만큼 pop push가 이뤄져서 그렇다는데 이해가안되여

[익명(119.206)]

단조의 이자나기에 빠져버렸군...

[익명(211.234)]

Amortized analysis를 조금 더 공부해보셈

[투투♡(grw8vvf5izqn)]

와 이런게 있군요 감사합니다..

[익명(223.38)]

조건문 1회 check 당 반드시 스택에 원소가 삽입/삭제 되는데, 각 원소는 최대 1번씩만 삽입, 삭제될수 있어서 조건문을 최대 2N번 보게 됨

[투투♡(grw8vvf5izqn)]

조건문 최대 2N이라는 키워드를 이해하지 못했어용..

[투투♡(grw8vvf5izqn)]

아 다른글 보고 이해했어요 중첩루프를 느슨하게 볼수있군요

[투투♡(grw8vvf5izqn)]

와 댓글들을 이해하기 위해서 노력해볼게.. 어렵따 고마워