11강 - 힙 정렬(Heap Sort) [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #11 ]

11강 - 힙 정렬(Heap Sort) [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #11 ] 강의 동영상입니다. 이번 시간에는 시간 복잡도 O(N * log N)의 속도를 자랑하는 힙 정렬의 개념을 이해하고, 직접 C 언어를 이용해 구현해보는 시간을 가집니다.

[@seungjongryu9626]

자바로 작성하시는 분들 참고하시면 좋을거 같아요 자바의 경우 배열의 인덱스오류가 발생하기 때문에 초기 최대힙을 구성 후 정렬하는 반복문 내에서 if(c

[@홍석현-j9p]

감사합니다 선생님..

[@김명지-u7k]

사소하지만 영상 설명란에 블로그 URL이 함께 포함되어 있으면 좋을 거 같아요! 항상 강의 잘 보고 있습니다! 감사해요!

[@medalofduty8935]

교수님 수업 내내 이해 못하던걸 20분만에 이해하다니.. 이건 매직이다...

[@FrogDotDev]

말도안돼... 책으로 2시간넘게봐도 이해안되던게 이렇게 간단하게 이해되다니...

[@user-sg1en6gr4x]

완전 다른어느강의보다 쉽게설명하고 수준높은 강의 감사합니다

[@shh5922]

최곱니다 한방에 이해..

[@moonstephen1174]

8:14 힙을 구성할때 시간복잡도가 1/2n*logn 에서 logn이 작기 때문에 그냥 O(n)이 된다고 하셨는데, big-O 연산에서 이렇게 줄여도 되는 건가요??; 그럼 O(nlogn) -> O(n) 이 되는 건데, 이 부분이 이해가 안가네요;;

[@dongbinna]

그 부분 제가 실수한 거에요~ㅜㅜ O(nlogn)이 맞아요! logn이 상수급으로 작긴 하지만... 사라질 순 없는 건데... 잘못된 정보 죄송합니다!!

[@hc-sc9mx]

으악...이부분 진짜 이해안되서 여러번 봣는데 역시 이게 맞군요ㅠㅠ

[@bnbnac]

아ㅎㅎ 혹시나해서 댓글 찾아보니 역시.. 나동빈님 영상 잘 보고 있습니다~!!

[@Yu-kt6wy]

너무 이해가 잘 되네요 감사합니다

[@포도-b7r]

우와... 블로그만 하시는 줄 알았는데 유튜브까지.. 정말 리스펙합니다🙏🙏 강의 잘 듣고갑니다..!! 번창하세효!!

[@procyonq]

좋은 강의 감사합니다! 질문이 있는데요, C로 구현하신 첫번째 heapify 코드는 O(n)이 아니라 O(n logn) 아닌가요? .. 답변 부탁드립니다. 감사합니다!

[@홍승현-y3m]

아 그리고! 초기에 힙 정렬 1번 한 '상태' 로! 첫번째와 끝을 바꾸고 데이터를 하나 씩 줄여나가서 반복한다고 말씀하셨는데, 첫 힙정렬과 그 다음 힙정렬을 구분하신 이유가 궁금합니다!! 밑에 예시 처럼 한 반복문에 다 넣어도 되지 않나요?! 잦은 질문 죄송합니다 ㅠㅠㅠ ex) #include int data[7] = { 1,4,7,5,3,8,2 }; int number = 7; int main() { int temp; int i; while (number != 0) { for (i = 1; i < number; i++) { int c = i; while (c != 0) { int root = (c - 1) / 2; if (data[c] > data[root]) { temp = data[c]; data[c] = data[root]; data[root] = temp; } c = root; } } temp = data[0]; data[0] = data[number - 1]; data[number - 1] = temp; number--; //데이터 하나 씩 줄이기 } for (i = 0; i < 7; i++) { printf("%d", data[i]); } return 0; } 이런식으로...!

[@yoonchaena671]

저도 정말 같은 생각입니다.

[@user-rk4hx9xw8p]

보신다면 꼭 답변해주셨으면 좋겠습니다. 처음 heapify할때는 하향으로 한것이고 그 다음부터는 상향으로 하신 것인가요? 그리고 15:16에 for(i=number/2; 로 바꾸고18:46에 while(c

[@yha6535]

힙 설명 3:30 힙 정렬 과정 9:20

[@ducksjc]

30번, 34번 줄은 문제가 있네요. 오버플로 버그가 안나게 하려고 인덱스 크기 검사를 하는데 문제는 그게 우측에 있습니다. 제가 랜덤 배열 크게 만들어서 넣어보니 뻗어요. 그리고 개념상 34번이나 11번 if문의 스왑을 안하게 된다면 그 자리에서 바로 break해도 되지요. 왜냐면 변화가 없다는 것은 이미 힙구조가 맞다는 것이니까요. 정렬의 속도가 빠르다는 것이 주제라고도 할 수 있는데, 제때 break 안해주고 계속 순환문을 돌게 놔두는 것은 문제가 맞지요. 변수명도 문제가 좀 있습니다. root는 최상위부모라는 뜻이지 부모라는 뜻이 아닌데 부모로 사용하네요. 제가 직접 문제들을 수정하여서 전체 소스코드를 작성해봤습니다. #include #include #include #include using namespace std; void heap_sort(vector& v) { //int cnt = 0; size_t size = v.size(); //최대힙구조로 변환. 상->하 for (int i = 1; i < size; i++) { int c = i; do { //c는 자식이고, 부모는 1개 뿐이며, 부모가 자식보다 크도록 변환해줄 것임. //이 부모가 자식을 2개까지 가질 수 있고 2번째 자식이 여전히 부모 보다 클 수 있지만 이는 결국 i가 size까지 순환하면서 해결될 것. //이는 개념상 i라는 요소가 새로 삽입된 것을 상정한 것이기도 하다. int parent = (c - 1) / 2; if (v[parent] < v[c]) { int tmp = v[parent]; v[parent] = v[c]; v[c] = tmp; } else break;//이론상 변경이 없다면 c위로(루트방향) 이미 힙구조인거 c = parent; } while (c != 0); } //출력 for (size_t i = 0; i < size; i++) { std::cout

[@mo-mz9ys]

학교에서 배우는것보다 여기서 배우는게 더 쉽고 재밌어요 ㅇㅅㅇ~

[@시골닭-s3p]

고맙습니다

[@jeonhwanwon3681]

힙구조 만드는 부분만 봤을때 [7, 6, 5, 8, 3, 5, 9, 1, 6] 배열이 [9, 8, 7, 6, 3, 5, 5, 1, 6] 로 표현 해주셨는데. 실제 코드(힙 구조만드는 부분만)를 돌려봤을때는 [9, 7, 8, 6, 3, 5, 5, 1, 6] 으로 나오는데요, 즉 2,3번 인덱스(7,8 -> 8,7) 값이 바뀌어있는데, 해당 내용은 오류인가요? 아니면 제가 잘못 테스트 한건지 궁금합니다.

[@whatIsHandle792]

15:53 영상과는 다른 주제인데 계속 교체하지 않고 미리 어디까지 내려가는지 확인한 후 붙여넣으면 속도가 더 빨라질 것 같아요 A와 B, B와 C, C와 D 교체를 하는 것보단 A를 temp에 들고 있고, A에 B를 넣고, B에 C를 넣고 C에 D를 넣고, D에 temp를 넣는거죠 이런 식으로 자잘자잘하게 시간복잡도(O(N*logN)이 달라지는 건 아니지만 N의 크기)를 줄이는 방법들이 많이 보여요

[@whatIsHandle792]

그런데 그거 구현하려고 일주일 넘게 작업하다가 포기해버렸죠 ㅠㅠ 코딩실력을 더 키워야겠어요

[@whatIsHandle792]

총 배열의 크기만 알면 몇번 힙 정렬을 하면 잎노드에 닿는지 일일히 조건검사할 필요없이 바로 알 수 있기도 합니다

[@WinLOL-p1v]

안녕하세요 동빈나님 항상 좋은강의 시청하고 있습니다. 다름이 아니라, 최대 힙을 만들고 거기서 다시 for문으로 root와 제시된 Leaf를 바꾸는 부분이 이해가 안되어서 댓글 답니다. 혹시 한가지 for문에서 최대힙을 while문으로 만들면서 끝에는 Leaf와 root를 바꾸면서 진행하여 힙정렬을 수행하는 방식도 괜찮을지 여쭤보려 댓글답니다...... 진짜로 항상 너무나도 좋은 강의 잘 보고 있습니다. 책으로만 개념을 익히다 유튜브로 올려주신 강의를 보니 띵하던 개념들이 알차게 머리로 계속 날아들어옵니다. 감사합니다

[@haesuun]

매우 도움 됐어요. 감사합니다.

[@bowrain7880]

좋은 강의 감사합니다!!

[@full_hexagon]

15:27 부모노드는 자식노드 / 2 아닌가용?? 예를 들어 인덱스를 봤을 때 1 부모노드 2, 3 자식노드라 하면 /2를 했을 때 몫이 부모노드가 나오고.. (c-1)/2 을 하게되면, 인덱스 3에서는 잘 나오겠지만, 인덱스 2에서는 몫이 0이라 다른 부모노드가 나올텐데.. 이 부분 아시는 분 계신가요ㅠㅠ

[@Curry0310]

스타트지점(즉 루트지점) 인덱스를 1로 잡았을땐 @Hwan K님 말씀대로 부모노드는 자식노드/2 입니다.하지만 동빈나님 소스코드안에서는 스타트지점 인덱스를 0으로 잡고 시작하셨기때문에 (c-1)/2가 맞게되는것 같습니다 :)

[@full_hexagon]

@@Curry0310 와 그렇구나 감사합니다!!

[@user-ul9yy4hd3m]

나동빈님, 상향식이든 하향식이든 for문에서 (number)번 반복한다는 것은 힙 구조를 만드는 복잡도가 O(N)이기 때문인 것이 맞나요? (수정) 아, 잘못 생각한 것 같아요. 상향식에는 1~number-1 이고 하향식에는 number-1~0 인 것이면.. 상향식에서는 [1]항 부터 스캔을, 하향식에서는 [number-1]부터 heap[0] 값을 저장하기 위함인 것 같네요..

[@가니-d9b]

힙을 배열로 사용한 것이 혹시 배열표현법을 사용한 건가요? 모든 이진 트리를 포화 이진 트리라고 가정하는 배열 표현법을 쓸 때 첫 칸을 무조건 비워서 인덱스가 1부터 사용된다고 했는데 이 개념과 혼동되어 여쭤봅니다!

[@andthensome9277]

c와 root를 구하는공식이 c = 2* root +1 , root = (c-1)/2 인지 이해가 잘안가서요. 알려주실수있으실까요? [출처] 10. 힙 정렬(Heap Sort)|작성자 안경잡이개발자

[@ponix1004]

하향식으로 찾아나갈때 의문점이 있는데요. 예를들어 데이터가 1 3 5 7 4 6 8 이라고 가정하면, 처음 1 ( 3,5)에서 1과 5가 교체되고, 3( 7,4) 에서 3과 7이 교체되며, 마지막으로 1(6,8)에서 1과 8이 교체되면, 5 7 8 3 4 6 1이라는 순서를 이루게 될 것 같은데 이러면 root가 가장 큰 수가 아니게 되지 않나요? 하위 노드부터 상향식으로 올라가는건 맞는 것 같은데, 하향식으로 진행되는게 이해가 안가네요... (정리하자면 하향식에서 2단계 이상의 하위 노드에 있던 큰 값을 어떻게 끌어 올릴 수 있는지를 모르겠습니다...)

[@박민상-p9d]

11:00 쯤 에서 궁금한게, leaf에 1 6 3 5 9 가 아니라 1 7 3 5 9 가 있으면 n/2 개만 보면 되는게 아니지 않나요? 왼쪽의 제일 작은 트리가 최대힙을 만족하지 않아요 부모노드 : 6 자식 노드 : 1 , 7이 됩니다. 여기서 한 번 더 확인을 해야하지 않을까요??

[@박민상-p9d]

뒤에 반복하는군욧;

[@김정주-z5n5z]

이거 원소의 개수가 5개나 9개 11개 일때, 즉 binary search가 완벽한 형태가 아니면 do while문이기 때문에 child 크기가 최대 array 개수보다 커져서 오류나네요.

[@user-fh4ej9ut7q]

정말 다 좋은데 값 발음이 너무 신경쓰이네요

[@choi971]

알고리즘 시험에서는 stl 로 정렬하면 되는거아닌가요? 코딩할줄 알아야돼요?

[@J_J944]

왼쪽 자식노드가 2*root고 오른쪽 자식노드가 2*root+1 아닌가요?? 왜 2*root+1 이랑, 거기에 1 더한값이랑 비교를 해요??

[@hc-sc9mx]

처음 heap구성 하실 때는 상향식이지만 힙 크기 줄이면서 할 때는 하향식으로 하신거죠??

[@bomul0524]

그런 것 같네요 좀 헷갈렸습니다

[@hc-sc9mx]

@@bomul0524 넵 답변 감사드립니다! ㅎㅎ 항상 강의 잘 보고 있습니다.

[@자바몽]

타자 칠때 통통 하는 소리 조으다

[@akira9323]

시작 부터 끝 까지 걸리는 시간 출력은 못하나요?

[@우와아앙-n6x]

do while을 활용하신 이유가 따로 있나요??

[@sopdetsirius]

your voice is honey

[@sopdetsirius]

seriously tho

[@dongbinna]

Thanks dude.

[@gritty6274]

3번의 시도 끝에 혼자 구현 완료 했습니다 ㅠㅠㅠ 어렵네요 힙정렬

[@홍승현-y3m]

처음 힙을 구성할 때는 1~number까지 자식을 기준으로 부모의 위치를 찾는 방식으로 구성하셨는데 크기를 줄여가며 힙을 구성할 때는 number-1~0까지 부모를 기준으로 자식의 위치를 찾는 방식으로 구성하셨습니다. 처음과 크기를 줄여가며 구성한 힙의 방식에 차이를 둔 이유가 궁금합니다.

[@dongbinna]

하향식, 상향식 모두 수행시간을 고려했을 때 동일한 시간복잡도를 가집니다. 강좌에서 말씀드렸듯이 자기가 편한 방식을 이용하시면 됩니다. ㅎㅎㅎ

[@홍승현-y3m]

2개 다 보여주신거군요.. 감사합니다!! 빠른 답변을 받은 김에 하나만 더 여쭤보겠습니다! 이 다음 알고리즘 강좌부터는 c++로 강좌를 하시는데 c++기초 강좌를 다른데서 배운다음에 들어야할까요?

[@dongbinna]

아니요. 하시면서 C++ 문법 익히셔도 됩니다. C언어 구조체 정도만 이해하셔도 큰 무리 없을 겁니다.

[@korkor6721]

카카오에나온 문제네요ㅋㅋ

[@Hwemanghangook]

값을 -> 가플 ???????

[@jingonpark1227]

한번 heapify가 실행되는 시간이 O(logn)이라고 설명하셨는데 왜 그런지 궁금합니다!!

[@wldnd2640]

do while 쓰는 이유가 뭔가요 while 쓰죠 걍

[@deeep_sea]

10:20~15:00

[@user-hf9vt9rg7f]

힙을 이용하는 또 다른 경우는 어떤 경우인가요?

[@dongbinna]

최단경로 문제부터 시작해서, nlogn을 뽑아야 하는 정말 다양한 문제에 적용할 수 있습니다.

[@user-hf9vt9rg7f]

@@dongbinna 힙 이론을 창안해 낸 사람은 정말 천재인거 같네요 물론 이렇게 쉽게 설명해준 동빈나님도 천재인거같아요~

[@dongbinna]

전 멍텅구리입니다...

[@user-cy6qd6xq7w]

배경으로 숨소리가 들리는데 뭔가요...ㄷㄷ... 9:19 9:22

[@wldnd2640]

15:13

[@wldnd2640]

10:08

[@wkdsaseum]

동빈나는 GOD인가

[@bansin175]

목소리에 비해서 오프닝 소리가 너무 큰 것 같습니다.

[@띠용-l3j3r]

ㅋㅋ 근데 이 분 가플, 가피 하는거 왜캐 웃기징 ㅋㅋㅋ 컴퓨터로는 거의 국내서 독보적 정점 찍으시는 분인데.. 혹시 닭이 도 달리라고 발음하시나요 .. 값을 자꾸 가플이라고 하시는데.. 댓글에서 자꾸 지적하는데 영상찍은다음에 보신건가.. 자꾸 댓글그거 보고나서 들으니 신경쓰이넹.

[@dongbinna]

컴퓨터 분야 정점과는 거리가 멀어요 ㅜㅜ 최근 영상에서는 제대로 발음하고 있습니다...ㅎㅎㅎ 저도 영상 찍으면서 배우고 있네요.

[@이성훈-h1i]

교수님보다 설명 100배는 잘하시는듯 ㅋㅋ

[@kgb8594]

광고는 끝까지 시청하기!!

[@wa-ng]

틀렸음. 힙은 궁뎅이를 뜻함

[@user-vp8lj6ch6e]

나만 빡대가린가..

[@wldnd2640]

코드 설명 ㅈㄴ빈약하네 진짜