LRU는 Least Recently Used: 가장 오래 전에 사용된 놈을 찾는 방식이다
이걸 큐로 구현 가능하다는데... 시벌 어떻게 하는건데?
난 모르겠다.
인터넷에 보면 나오겠지만 그러면 왠지 지는 거 같아서...
LRU는 그냥.. 사람이 적은 수의 무언가를 가지고 하면 쉽다
그래서 그냥 사람이 하는 방식을 알고리즘 비슷한 걸로 옮긴게 내 방식인데
무슨 듣도못한... 중복없는 큐를 써야 한다.
이게 뭐지 시벌...
일단 큐가 아닌 건 알겠다...
분명히 인터넷에 정답이 있겠지
이렇게 고민하는 게 맞는 방법인가? 성취감은 있는데 말이야
고민하면 더 좋겟죠? - AubeCiel 새벽하늘
알고리즘은 해결하면 쾌감에 바지가 흥건해지긴 함
O(1)이냐 O(lg n)이냐??
아 몰라요 그런 거
넣고 빼는 건 O(1)이겠고 검색해서 중복 삭제해야 되니까 O(n)일 듯
중복 삭제를 O(lg n)에 가능하니 O(1)도 되는지 물어본것임 ㅎ
엥 중복삭제를 어케 O(log n)만에 하죵
큐에서는 lazy하게 중복 삭제하는걸로 하고 중복검사는 c++로 치면 std::map같은걸로 원소개수 세면 될듯
??? 자세히 좀 설명해주세요 저 알알못이라;
큐가 CDAB 가지고 있고 원소 개수 세는 O(lg n) 자료구조로 cnt[C]=1 cnt[D]=1 cnt[A]=1 cnt[B]=1 가지고 있고 여기 D가 푸쉬되면 큐는 CDABD가 되고 cnt[D]=2로 업데이트 하고 예를들어 연속으로 팝 두번한다고 치면 DABD에 cnt[C]=0으로 업데이트하고 D 팝할차례지? cnt[D]를 살펴보니 2야 이미 D가 푸쉬됐다는 얘기지 그러니까 D 버리면서 팝하고 cnt[D]=1 하면 중복없는큐 똑같이 시뮬레이션 가능
아항 다른 걸 쓰는 거군요
머학원생//푸쉬->푸시 (sh는 시로 표기함. 스킨십 멤버십 플래그십 플래시 등등...) [리듬 맞춤법 봇♬]