11강 - 힙 정렬(Heap Sort) [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #11 ] 강의 동영상입니다. 이번 시간에는 시간 복잡도 O(N * log N)의 속도를 자랑하는 힙 정렬의 개념을 이해하고, 직접 C 언어를 이용해 구현해보는 시간을 가집니다.
Пікірлер: 78
@seungjongryu96264 жыл бұрын
자바로 작성하시는 분들 참고하시면 좋을거 같아요 자바의 경우 배열의 인덱스오류가 발생하기 때문에 초기 최대힙을 구성 후 정렬하는 반복문 내에서 if(c
@홍석현-j9p3 жыл бұрын
감사합니다 선생님..
@김명지-u7k5 жыл бұрын
사소하지만 영상 설명란에 블로그 URL이 함께 포함되어 있으면 좋을 거 같아요! 항상 강의 잘 보고 있습니다! 감사해요!
@medalofduty89353 жыл бұрын
교수님 수업 내내 이해 못하던걸 20분만에 이해하다니.. 이건 매직이다...
@FrogDotDev5 жыл бұрын
말도안돼... 책으로 2시간넘게봐도 이해안되던게 이렇게 간단하게 이해되다니...
@llll-h3c1b4 жыл бұрын
완전 다른어느강의보다 쉽게설명하고 수준높은 강의 감사합니다
@shh59226 жыл бұрын
최곱니다 한방에 이해..
@moonstephen11745 жыл бұрын
8:14 힙을 구성할때 시간복잡도가 1/2n*logn 에서 logn이 작기 때문에 그냥 O(n)이 된다고 하셨는데, big-O 연산에서 이렇게 줄여도 되는 건가요??; 그럼 O(nlogn) -> O(n) 이 되는 건데, 이 부분이 이해가 안가네요;;
@dongbinna5 жыл бұрын
그 부분 제가 실수한 거에요~ㅜㅜ O(nlogn)이 맞아요! logn이 상수급으로 작긴 하지만... 사라질 순 없는 건데... 잘못된 정보 죄송합니다!!
@hc-sc9mx3 жыл бұрын
으악...이부분 진짜 이해안되서 여러번 봣는데 역시 이게 맞군요ㅠㅠ
@bnbnac Жыл бұрын
아ㅎㅎ 혹시나해서 댓글 찾아보니 역시.. 나동빈님 영상 잘 보고 있습니다~!!
@Yu-kt6wy2 жыл бұрын
너무 이해가 잘 되네요 감사합니다
@포도-b7r6 жыл бұрын
우와... 블로그만 하시는 줄 알았는데 유튜브까지.. 정말 리스펙합니다🙏🙏 강의 잘 듣고갑니다..!! 번창하세효!!
@procyonq2 жыл бұрын
좋은 강의 감사합니다! 질문이 있는데요, C로 구현하신 첫번째 heapify 코드는 O(n)이 아니라 O(n logn) 아닌가요? .. 답변 부탁드립니다. 감사합니다!
@홍승현-y3m6 жыл бұрын
아 그리고! 초기에 힙 정렬 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; } 이런식으로...!
@yoonchaena6713 жыл бұрын
저도 정말 같은 생각입니다.
@user-rk4hx9xw8p4 жыл бұрын
보신다면 꼭 답변해주셨으면 좋겠습니다. 처음 heapify할때는 하향으로 한것이고 그 다음부터는 상향으로 하신 것인가요? 그리고 15:16에 for(i=number/2; 로 바꾸고18:46에 while(c
@yha65354 жыл бұрын
힙 설명 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-mz9ys6 жыл бұрын
학교에서 배우는것보다 여기서 배우는게 더 쉽고 재밌어요 ㅇㅅㅇ~
@시골닭-s3p Жыл бұрын
고맙습니다
@jeonhwanwon36815 жыл бұрын
힙구조 만드는 부분만 봤을때 [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) 값이 바뀌어있는데, 해당 내용은 오류인가요? 아니면 제가 잘못 테스트 한건지 궁금합니다.
@whatIsHandle7922 жыл бұрын
15:53 영상과는 다른 주제인데 계속 교체하지 않고 미리 어디까지 내려가는지 확인한 후 붙여넣으면 속도가 더 빨라질 것 같아요 A와 B, B와 C, C와 D 교체를 하는 것보단 A를 temp에 들고 있고, A에 B를 넣고, B에 C를 넣고 C에 D를 넣고, D에 temp를 넣는거죠 이런 식으로 자잘자잘하게 시간복잡도(O(N*logN)이 달라지는 건 아니지만 N의 크기)를 줄이는 방법들이 많이 보여요
@whatIsHandle7922 жыл бұрын
그런데 그거 구현하려고 일주일 넘게 작업하다가 포기해버렸죠 ㅠㅠ 코딩실력을 더 키워야겠어요
@whatIsHandle7922 жыл бұрын
총 배열의 크기만 알면 몇번 힙 정렬을 하면 잎노드에 닿는지 일일히 조건검사할 필요없이 바로 알 수 있기도 합니다
@WinLOL-p1v2 жыл бұрын
안녕하세요 동빈나님 항상 좋은강의 시청하고 있습니다. 다름이 아니라, 최대 힙을 만들고 거기서 다시 for문으로 root와 제시된 Leaf를 바꾸는 부분이 이해가 안되어서 댓글 답니다. 혹시 한가지 for문에서 최대힙을 while문으로 만들면서 끝에는 Leaf와 root를 바꾸면서 진행하여 힙정렬을 수행하는 방식도 괜찮을지 여쭤보려 댓글답니다...... 진짜로 항상 너무나도 좋은 강의 잘 보고 있습니다. 책으로만 개념을 익히다 유튜브로 올려주신 강의를 보니 띵하던 개념들이 알차게 머리로 계속 날아들어옵니다. 감사합니다
@haesuun4 жыл бұрын
매우 도움 됐어요. 감사합니다.
@bowrain78804 жыл бұрын
좋은 강의 감사합니다!!
@full_hexagon3 жыл бұрын
15:27 부모노드는 자식노드 / 2 아닌가용?? 예를 들어 인덱스를 봤을 때 1 부모노드 2, 3 자식노드라 하면 /2를 했을 때 몫이 부모노드가 나오고.. (c-1)/2 을 하게되면, 인덱스 3에서는 잘 나오겠지만, 인덱스 2에서는 몫이 0이라 다른 부모노드가 나올텐데.. 이 부분 아시는 분 계신가요ㅠㅠ
@Curry03103 жыл бұрын
스타트지점(즉 루트지점) 인덱스를 1로 잡았을땐 @Hwan K님 말씀대로 부모노드는 자식노드/2 입니다.하지만 동빈나님 소스코드안에서는 스타트지점 인덱스를 0으로 잡고 시작하셨기때문에 (c-1)/2가 맞게되는것 같습니다 :)
@full_hexagon3 жыл бұрын
@@Curry0310 와 그렇구나 감사합니다!!
@user-ul9yy4hd3m5 жыл бұрын
나동빈님, 상향식이든 하향식이든 for문에서 (number)번 반복한다는 것은 힙 구조를 만드는 복잡도가 O(N)이기 때문인 것이 맞나요? (수정) 아, 잘못 생각한 것 같아요. 상향식에는 1~number-1 이고 하향식에는 number-1~0 인 것이면.. 상향식에서는 [1]항 부터 스캔을, 하향식에서는 [number-1]부터 heap[0] 값을 저장하기 위함인 것 같네요..
@가니-d9b3 жыл бұрын
힙을 배열로 사용한 것이 혹시 배열표현법을 사용한 건가요? 모든 이진 트리를 포화 이진 트리라고 가정하는 배열 표현법을 쓸 때 첫 칸을 무조건 비워서 인덱스가 1부터 사용된다고 했는데 이 개념과 혼동되어 여쭤봅니다!
하향식으로 찾아나갈때 의문점이 있는데요. 예를들어 데이터가 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단계 이상의 하위 노드에 있던 큰 값을 어떻게 끌어 올릴 수 있는지를 모르겠습니다...)
@박민상-p9d4 жыл бұрын
11:00 쯤 에서 궁금한게, leaf에 1 6 3 5 9 가 아니라 1 7 3 5 9 가 있으면 n/2 개만 보면 되는게 아니지 않나요? 왼쪽의 제일 작은 트리가 최대힙을 만족하지 않아요 부모노드 : 6 자식 노드 : 1 , 7이 됩니다. 여기서 한 번 더 확인을 해야하지 않을까요??
@박민상-p9d4 жыл бұрын
뒤에 반복하는군욧;
@김정주-z5n5z5 жыл бұрын
이거 원소의 개수가 5개나 9개 11개 일때, 즉 binary search가 완벽한 형태가 아니면 do while문이기 때문에 child 크기가 최대 array 개수보다 커져서 오류나네요.
@민-b7g Жыл бұрын
정말 다 좋은데 값 발음이 너무 신경쓰이네요
@choi971 Жыл бұрын
알고리즘 시험에서는 stl 로 정렬하면 되는거아닌가요? 코딩할줄 알아야돼요?
@J_J944 Жыл бұрын
왼쪽 자식노드가 2*root고 오른쪽 자식노드가 2*root+1 아닌가요?? 왜 2*root+1 이랑, 거기에 1 더한값이랑 비교를 해요??
@hc-sc9mx3 жыл бұрын
처음 heap구성 하실 때는 상향식이지만 힙 크기 줄이면서 할 때는 하향식으로 하신거죠??
@bomul05243 жыл бұрын
그런 것 같네요 좀 헷갈렸습니다
@hc-sc9mx3 жыл бұрын
@@bomul0524 넵 답변 감사드립니다! ㅎㅎ 항상 강의 잘 보고 있습니다.
@자바몽5 жыл бұрын
타자 칠때 통통 하는 소리 조으다
@akira9323 Жыл бұрын
시작 부터 끝 까지 걸리는 시간 출력은 못하나요?
@우와아앙-n6x4 жыл бұрын
do while을 활용하신 이유가 따로 있나요??
@sopdetsirius6 жыл бұрын
your voice is honey
@sopdetsirius6 жыл бұрын
seriously tho
@dongbinna6 жыл бұрын
Thanks dude.
@gritty62743 жыл бұрын
3번의 시도 끝에 혼자 구현 완료 했습니다 ㅠㅠㅠ 어렵네요 힙정렬
@홍승현-y3m6 жыл бұрын
처음 힙을 구성할 때는 1~number까지 자식을 기준으로 부모의 위치를 찾는 방식으로 구성하셨는데 크기를 줄여가며 힙을 구성할 때는 number-1~0까지 부모를 기준으로 자식의 위치를 찾는 방식으로 구성하셨습니다. 처음과 크기를 줄여가며 구성한 힙의 방식에 차이를 둔 이유가 궁금합니다.
@dongbinna6 жыл бұрын
하향식, 상향식 모두 수행시간을 고려했을 때 동일한 시간복잡도를 가집니다. 강좌에서 말씀드렸듯이 자기가 편한 방식을 이용하시면 됩니다. ㅎㅎㅎ
@홍승현-y3m6 жыл бұрын
2개 다 보여주신거군요.. 감사합니다!! 빠른 답변을 받은 김에 하나만 더 여쭤보겠습니다! 이 다음 알고리즘 강좌부터는 c++로 강좌를 하시는데 c++기초 강좌를 다른데서 배운다음에 들어야할까요?
@dongbinna6 жыл бұрын
아니요. 하시면서 C++ 문법 익히셔도 됩니다. C언어 구조체 정도만 이해하셔도 큰 무리 없을 겁니다.
@korkor6721 Жыл бұрын
카카오에나온 문제네요ㅋㅋ
@Hwemanghangook3 жыл бұрын
값을 -> 가플 ???????
@jingonpark12275 жыл бұрын
한번 heapify가 실행되는 시간이 O(logn)이라고 설명하셨는데 왜 그런지 궁금합니다!!
@wldnd26402 жыл бұрын
do while 쓰는 이유가 뭔가요 while 쓰죠 걍
@deeep_sea Жыл бұрын
10:20~15:00
@시간을아끼자-r4r5 жыл бұрын
힙을 이용하는 또 다른 경우는 어떤 경우인가요?
@dongbinna5 жыл бұрын
최단경로 문제부터 시작해서, nlogn을 뽑아야 하는 정말 다양한 문제에 적용할 수 있습니다.
@시간을아끼자-r4r5 жыл бұрын
@@dongbinna 힙 이론을 창안해 낸 사람은 정말 천재인거 같네요 물론 이렇게 쉽게 설명해준 동빈나님도 천재인거같아요~
@dongbinna5 жыл бұрын
전 멍텅구리입니다...
@user-cy6qd6xq7w4 жыл бұрын
배경으로 숨소리가 들리는데 뭔가요...ㄷㄷ... 9:19 9:22
@wldnd26402 жыл бұрын
15:13
@wldnd26402 жыл бұрын
10:08
@wkdsaseum8 ай бұрын
동빈나는 GOD인가
@bansin1753 жыл бұрын
목소리에 비해서 오프닝 소리가 너무 큰 것 같습니다.
@띠용-l3j3r5 жыл бұрын
ㅋㅋ 근데 이 분 가플, 가피 하는거 왜캐 웃기징 ㅋㅋㅋ 컴퓨터로는 거의 국내서 독보적 정점 찍으시는 분인데.. 혹시 닭이 도 달리라고 발음하시나요 .. 값을 자꾸 가플이라고 하시는데.. 댓글에서 자꾸 지적하는데 영상찍은다음에 보신건가.. 자꾸 댓글그거 보고나서 들으니 신경쓰이넹.
@dongbinna5 жыл бұрын
컴퓨터 분야 정점과는 거리가 멀어요 ㅜㅜ 최근 영상에서는 제대로 발음하고 있습니다...ㅎㅎㅎ 저도 영상 찍으면서 배우고 있네요.