오늘도 잘 봤습니다! 원래는 다 아는 자료구조라고 생각해서 볼 필요는 없다고 생각했는데, 한 발자국 넘어서 어떤 경우에 사용되는지 설명해 주시니까 정말 좋네요 :D Heap은 PriorityQueue의 대표적인 구현체 힙의 대표적인 예시는 주로 프로세스 스케줄링!. CPU가 사용하지 않는 프로세스는 ready queue에서 대기한다. ready queue에선 FIFO가 아니라 우선순위 순서대로 값을 꺼내어 준다. (아마 starvation이나 IO 대기 효율 등 여러 요소가 관련되어 있을 것 같네요) 힙 메모리의 힙은 오늘 배운 힙과는 관련 없음.
오 엄밀히 말하면 트리와 그래프는 다른 개념이라서 구분해서 이해하시는게 더 좋다고 생각합니다~ 왜냐하면 그래프는 부모 자식 개념이 없지만, 트리는 부모 자식 개념으로 구조화 되기 때문이죠 예를 들어서, 그래프 세계관에서는 트리 세계관에서 존재하는 왼쪽 서브트리나 오른쪽 서브트리 같은 개념 자체가 성립할 수가 없습니다 그렇기 때문에 트리를 그래프의 한 종류로 이해하기 보다는, 트리와 그래프는 다른 것으로 이해하는 것이 정확하다고 생각해용 :)
일단 저는 우선순위큐 구현체는 힙만 알고 있는데요 힙에 삽입이 이미 된 상태에서 key가 변경되는 건 안될 것 같고.. 우선순위 부스팅이 필요하다면 큐에서 나오지도 못하는 상황이라는 것인데.. 별도의 자료구조에서 삽입된 시간 순으로 관리를 한다고 해도 부스팅 시점에 큐의 앞에 있는 스레드를 전부 꺼내봐야 하는 것도 비용이 큰 것 같고.. 고민해보다가 처리 방법이 상상이 가지 않아서 공룡책을 펼쳐봤습니다 책에서 윈도우즈는 우선순위 클래스마다 큐가 있다는 표현을 봤는데요(정확히 어떤 큐인지는 모르겠어요) 이 경우라면 오랜시간 참조되지 않은 저순위의 큐를 디큐해주는 방법이 가능할 것 같아요 리눅스의 경우는 RBT를 사용한다는 내용이었는데 key로 쓰이는 값이 cpu 점유시간을 추상화한 느낌인가보다 하고 정확한 동작은 이해가 잘 안가서 넘어갔네요..
오 자세히 적어주셔서 감사합니다~! 흥미로운 주제라 저도 고민을 좀 해봤는데요, (혼자만의 생각이라 실제 OS에서는 어떻게 했을지는 저도 추가로 확인해봐야 해요) 일단 예를 들어 맥스힙(우선순위가 높을수록 큰 값을 가지는 힙)으로 구현한다면, 가장 간단한 방법은 그 스레드를 힙에서 찾아서 제거해주고 바뀐 우선순위로 새로 넣어주는 방법이 있을 것 같고요, 조금 변형을 해서 쓴다면 이미 힙에 삽입된 상태라도 특정 스레드의 우선 순위를 올려주려는 것이니까, 바뀐 우선순위보다 큰 부모를 만날 때까지 부모와 계속 위치를 바꿔주며 올라가면 되지 않을까 싶어요 두 경우 모두 추가적인 문제는 조정하려는 그 스레드의 위치가 힙의 배열에서 어디인지를 찾아야 한다는 건데요, 이건 여러 방법이 있지 않을까 싶습니다 (단순히 힙 전체 서치를 할 수도 있고, 맵을 활용해서 스레드의 힙에서 위치 정보를 관리할 수도 있고요, 등등) --- 리눅스의 레드블랙트리 경우는 CFS(Completely Fair Scheduler)라는 스케줄러가 레드블랙트리로 구현이 되는데요, 이때 (스레드가 CPU에서 얼마나 실행됐는지를 나타내는) 가상런타임을 키로 사용하기 때문에, CPU에서 적게 실행된 스레드들부터 CPU에 실행될 수 있도록 해서 (트리에서는 가장 왼쪽에 있는 스레드겠죠) 최대한 균등하게 스케줄링하는 방식이라고 보시면 될 것 같아요~
![교과서 대신 '교육자료' 될 운명된 AI 디지털 교과서... 정부 '1년 유예안' 제시에도 야당은 "거부" [모잇슈] / EBS뉴스](http://i.ytimg.com/vi/g0c9RbLoHKw/mqdefault.jpg)
![Blox Fruits Dragon Rework Update [Full Stream]](http://i.ytimg.com/vi/EqDAp8udhm0/mqdefault.jpg)
인터넷 구글링해서 어렵게 이해했던 내용을 이렇게 간단하고 쉽게 정리해 주셔서 감사합니다. 정독 하고 갑니다.!
헿 칭찬의 말씀 감사합니다 :) 뿌듯하네요 ✌
딴거봐도 이해가 잘 안됐는데 이 영상으로 이해! 100점🎉
좋은 강의 감사합니다~~
항상 좋은 영상 감사합니다ㅎㅎ 알고리즘 공부하는데 많은 도움을 받고 있어요!! 오래오래 만들어 주세요!
헤헤 항상 애청해 주셔서 감사합니다 👍
꾸준히 좋은 영상으로 인사드릴게요!!
자주 들러주세용 ㅎㅎ
우선순위 큐 관련으론 더 찾아볼 필요 없겠군요 바로 알고리즘 풀러갑니닷
우왕~!! 알고리즘 고고씽!!! 🥳
좋은 강의 항상 감사합니다! 허프만 압축알고리즘을 구현할 떄, 힙과 우선순위 큐 차이가 뭘까 궁금했는데 잘 알고갑니다!
무슨차이인가 했는데 ADT와 구현체의 차이였군요, 유익한 영상 잘봤습니다.
맞아요ㅎㅎ ADT와 구현체(자료구조)의 차이에요 ㅎㅎ 댓글 정말 감사합니다 ㅠㅠ
개념 딱 잡고 갑니다!
오늘도 잘 봤습니다! 원래는 다 아는 자료구조라고 생각해서 볼 필요는 없다고 생각했는데, 한 발자국 넘어서 어떤 경우에 사용되는지 설명해 주시니까 정말 좋네요 :D
Heap은 PriorityQueue의 대표적인 구현체
힙의 대표적인 예시는 주로 프로세스 스케줄링!. CPU가 사용하지 않는 프로세스는 ready queue에서 대기한다. ready queue에선 FIFO가 아니라 우선순위 순서대로 값을 꺼내어 준다.
(아마 starvation이나 IO 대기 효율 등 여러 요소가 관련되어 있을 것 같네요)
힙 메모리의 힙은 오늘 배운 힙과는 관련 없음.
플러스 알파를 드릴 수 있어서 다행이에용~ :)
늘 영상을 유익하게 봐주셔서 정말 감사합니다 크흡 ㅠㅠ 👍
설명 너무 이해 잘되요!! 감사합니다 !!
크~~ 피드백이 큰 힘이 됩니다!! 귀한 댓글 감사합니당!ㅎㅎ
교수님 강의듣고 이해안되던게 한번에 됐어요! 좋은 강의 넘 감사해요!ㅠㅠ❤
2:39 트리의 정의에는 여러 가지가 있는 것으로 알고 있는데, 저는 개인적으로 트리를 "Cycle이 존재하지 않는 [그래프]"라고 정의를 하는데 , 이렇게 정의를 해도 문제가 없을까요?
오 엄밀히 말하면 트리와 그래프는 다른 개념이라서 구분해서 이해하시는게 더 좋다고 생각합니다~
왜냐하면 그래프는 부모 자식 개념이 없지만, 트리는 부모 자식 개념으로 구조화 되기 때문이죠
예를 들어서, 그래프 세계관에서는 트리 세계관에서 존재하는 왼쪽 서브트리나 오른쪽 서브트리 같은 개념 자체가 성립할 수가 없습니다
그렇기 때문에 트리를 그래프의 한 종류로 이해하기 보다는, 트리와 그래프는 다른 것으로 이해하는 것이 정확하다고 생각해용 :)
좋은 영상 고맙습니다:)
귀한 댓글 고맙습니다 :)
감사합니다!
저도 댓글 감사해요 :)
감사합니다.
저도 댓글 감사합니다 👍
면접 앞두고 벼락치기중입니다 ㅋㅋ 감사합니다 끼얏호우
급할 땐 토르가 돼야져ㅋㅋㅋ 화이티잉!!!!
안녕하세요. 메모리 구조에 있는 힙이 설명해주신 힙 자료구조와 동일한 방식인건가요?
안녕하세요~ 이름만 같은 뿐 전혀 상관 없다고 보시면 되세요
좀 더 자세한 설명은 16:46을 참고해 주세요~
레디 큐가 우선순위 큐로 구현되어 있다면 우선순위 부스팅은 어떻게 처리가 될까요??
오 재밌는 질문이에요~! 저도 생각을 조금 해봤는데요,
답변드리기에 앞서서 이미 생각해 보신 방법이 있을 것 같은데요, 생각해 보신 방법이 무엇인지 먼저 여쭤봐도 될까요?
혹은 생각해 보다가 막히신 부분이 있다면 어떤 부분이 막히셨는지 궁금해요 ~
일단 저는 우선순위큐 구현체는 힙만 알고 있는데요 힙에 삽입이 이미 된 상태에서 key가 변경되는 건 안될 것 같고..
우선순위 부스팅이 필요하다면 큐에서 나오지도 못하는 상황이라는 것인데..
별도의 자료구조에서 삽입된 시간 순으로 관리를 한다고 해도 부스팅 시점에 큐의 앞에 있는 스레드를 전부 꺼내봐야 하는 것도 비용이 큰 것 같고..
고민해보다가 처리 방법이 상상이 가지 않아서 공룡책을 펼쳐봤습니다
책에서 윈도우즈는 우선순위 클래스마다 큐가 있다는 표현을 봤는데요(정확히 어떤 큐인지는 모르겠어요)
이 경우라면 오랜시간 참조되지 않은 저순위의 큐를 디큐해주는 방법이 가능할 것 같아요
리눅스의 경우는 RBT를 사용한다는 내용이었는데 key로 쓰이는 값이 cpu 점유시간을 추상화한 느낌인가보다 하고 정확한 동작은 이해가 잘 안가서 넘어갔네요..
아 리눅스 쪽은 이미 수행된 스레드의 점유시간이 많았다는 정보를 정렬값에 포함시켜서 삽입하는데
비슷한 방법을 쓰면 우선순위큐로 구현이 될 것 같네요
그런데 또 한편으론 가변적인 데이터로 시스템을 관리하는게 괜찮은가 싶기도 하네요..!
오 자세히 적어주셔서 감사합니다~! 흥미로운 주제라 저도 고민을 좀 해봤는데요, (혼자만의 생각이라 실제 OS에서는 어떻게 했을지는 저도 추가로 확인해봐야 해요)
일단 예를 들어 맥스힙(우선순위가 높을수록 큰 값을 가지는 힙)으로 구현한다면, 가장 간단한 방법은 그 스레드를 힙에서 찾아서 제거해주고 바뀐 우선순위로 새로 넣어주는 방법이 있을 것 같고요,
조금 변형을 해서 쓴다면 이미 힙에 삽입된 상태라도 특정 스레드의 우선 순위를 올려주려는 것이니까, 바뀐 우선순위보다 큰 부모를 만날 때까지 부모와 계속 위치를 바꿔주며 올라가면 되지 않을까 싶어요
두 경우 모두 추가적인 문제는 조정하려는 그 스레드의 위치가 힙의 배열에서 어디인지를 찾아야 한다는 건데요, 이건 여러 방법이 있지 않을까 싶습니다 (단순히 힙 전체 서치를 할 수도 있고, 맵을 활용해서 스레드의 힙에서 위치 정보를 관리할 수도 있고요, 등등)
---
리눅스의 레드블랙트리 경우는 CFS(Completely Fair Scheduler)라는 스케줄러가 레드블랙트리로 구현이 되는데요, 이때 (스레드가 CPU에서 얼마나 실행됐는지를 나타내는) 가상런타임을 키로 사용하기 때문에, CPU에서 적게 실행된 스레드들부터 CPU에 실행될 수 있도록 해서 (트리에서는 가장 왼쪽에 있는 스레드겠죠) 최대한 균등하게 스케줄링하는 방식이라고 보시면 될 것 같아요~
그럼 스택은 adt이고 배열이 ds인건가요??
앗, 그렇진 않고요
이름이 똑같이 스택이라도 내부 구현 설명 없이 동작 스펙만 있다면 ADT이고요,
내부 구현까지 설명하고 있다면 DS라고 보시면 되겠습니다~
자바로 비유해서 설명하자면 클래스가 DS고 인터페이스가 ADT라고 비유할 수 있을 것 같아요~